In alcune situazioni, è necessario un indice per cercare informazioni in modo efficiente, ma l'utilizzo di un indice B-tree può risultare eccessivamente complesso e ridondante. In questi casi, un hash index può rappresentare un'alternativa più adatta.

Un hash index è un tipo di indice di database che utilizza una funzione di hash per mappare i valori indicizzati alle posizioni in una tabella hash.
In questo tipo di indice, i valori della colonna di destinazione vengono hashati, ovvero trasformati in un valore di dimensione fissa o codice hash, che viene poi utilizzato come indice per recuperare le righe dei dati.

Come funziona?

In un hash index, il processo di hashing consiste nel trasformare un valore chiave dell'indice in un codice hash tramite una funzione di hash. Questo codice hash viene poi utilizzato per determinare la posizione, o bucket, in cui sono memorizzati i dati corrispondenti nell'indice.

Puoi trovare ulteriori informazioni sull'hashing nel corso Panoramica su Algoritmi e Strutture Dati.

Consideriamo un hash index per un sistema di catalogo di una biblioteca in cui ogni titolo di libro è indicizzato tramite il suo ISBN (International Standard Book Number).

In questo esempio, utilizziamo una funzione di hash per convertire l'ISBN di un libro in un codice hash esadecimale, come 0x7FA4, tramite una serie di operazioni matematiche sulle cifre dell'ISBN.
Questo codice hash funge da identificatore univoco, determinando lo slot all'interno della tabella hash dove si trova un collegamento alla riga corrispondente nella tabella, contenente tutte le informazioni su quel particolare libro.

Caratteristiche principali

1. Ricerca veloce: Gli indici hash offrono ricerche rapide per confronti di uguaglianza. Quando si cerca un valore specifico, PostgreSQL calcola l'hash del valore e accede direttamente alla posizione corrispondente nell'indice, rendendo il recupero molto efficiente;

2. Supporto limitato agli operatori: A differenza degli indici B-tree, gli indici hash supportano solo confronti di uguaglianza (=), non query di intervallo (<, >, <=, >=) o ordinamenti. Questa limitazione rende gli indici hash meno versatili rispetto agli indici B-tree;

3. Maggiore velocità in alcuni casi d'uso: In scenari in cui il carico di lavoro prevede un alto volume di ricerche per uguaglianza, come l'applicazione di chiavi primarie o vincoli di unicità, gli indici hash possono superare in prestazioni gli indici B-tree. Tuttavia, il loro vantaggio prestazionale diminuisce per query di intervallo o dati che non si adattano bene all'algoritmo di hashing.

Implementazione

Possiamo implementare un indice hash in SQL utilizzando la seguente istruzione:

CREATE INDEX hash_index_name ON table_name USING HASH (column_name1, column_name2,... );

Di conseguenza, i valori di column_name1, column_name2,... verranno sottoposti a hashing e verrà creata la tabella hash. Questo consentirà un recupero più rapido delle righe di dati richieste.