Indicizzazione del database in breve con B+tree e Hash a confronto

Si dice spesso che l'indicizzazione sia una tecnica di riferimento per elaborare in modo efficiente le query nel caso in cui il database sia sufficientemente grande. Questo post è per riassumere cos'è l'indice del database e rivisitare hash e B+Tree.

L'indice è una struttura di dati che organizza i record per ottimizzare determinati tipi di operazioni di recupero. Possiamo creare un indice su un campo della tabella, quindi recuperare tutti i record che soddisfano le condizioni di ricerca su search-key campo. Senza l'indice, la nostra query finirebbe per scansionare in modo lineare l'intero contenuto della tabella per recuperare solo uno o pochi record.

In questo post, vorrei riassumere le prestazioni e i casi d'uso di due tecniche di indicizzazione comuni:Indice hash e B+albero

Indice hash

Questa tecnica è ampiamente utilizzata per creare indici nella memoria principale perché il suo rapido recupero per natura. Ha una complessità operativa media O(1) e una complessità di archiviazione O(n).
In molti libri, le persone usano il termine bucket per denotare un'unità di archiviazione che memorizza uno o più record
Ci sono due cose di cui discutere quando si tratta di hashing:

• Funzione hash:mappa le chiavi di ricerca (come input) su un numero intero che rappresenta quella chiave nel bucket.
• Schema di hashing:come gestire la collisione di chiavi dopo l'hashing.

Alcune persone chiedono:perché collisione? Esiste mai una funzione hash perfetta? In effetti, supponiamo che le tue chiavi siano un insieme infinito, è impossibile mapparle in un insieme di interi a 32 bit senza avere collisioni. Dovrebbe esserci un compromesso tra calcolo e tasso di collisione.

Ci sono alcuni schemi di hashing degni di nota:probing lineare, hashing concatenato e hashing estensibile. Gli algoritmi di ricerca/inserimento/eliminazione variano in base allo schema di hash, ad esempio, l'hashing concatenato si occupa di collisioni di chiavi posizionando elementi che hanno lo stesso valore hash nello stesso bucket.

Pro

• L'indice hash è adatto per l'uguaglianza o la ricerca della chiave primaria. Le query possono trarre vantaggio dall'indice hash per ottenere il costo di ricerca O(1) ammortizzato. Ad esempio:SELECT name, id FROM student WHERE id = '1315';

Contro

La tabella hash presenta alcune limitazioni:

• Le query sull'intervallo non sono efficienti. La tabella hash si basa su una distribuzione uniforme. In altre parole, non hai il controllo su dove verrà posizionata una voce di indice.
• Bassa scalabilità:le prestazioni dell'operazione di ricerca possono peggiorare in presenza di molte collisioni e richiede il ridimensionamento della tabella hash, quindi il rehashing delle voci di indice esistenti.

B+Albero

Si tratta di una struttura di dati ad albero autobilanciante che mantiene i dati in ordine e consente una ricerca rapida all'interno di ciascun nodo, in genere utilizzando la ricerca binaria.
B+Tree è un'implementazione di indice standard in quasi tutti i sistemi di database relazionali.

B+Tree è fondamentalmente un albero di ricerca M-way che ha la seguente struttura:

• Perfettamente bilanciato:i nodi foglia hanno sempre la stessa altezza.
• ogni nodo interno diverso dalla radice è almeno mezzo pieno (M/2 − 1 <=num di chiavi <=M − 1).
• ogni nodo interno con k chiavi ha k+1 figli non nulli.

Ogni nodo dell'albero ha una matrice di coppie chiave-valore ordinate. La coppia chiave-valore è costruita da (valore chiave di ricerca, puntatore) per i nodi radice e interni. I valori dei nodi foglia possono essere 2 possibilità:

• il record effettivo
• il puntatore al record effettivo

Cerca un valore v

• Inizia con il nodo radice
• Anche se node non è un nodo foglia, lo facciamo:
  • Trova il Ki più piccolo dove Ki>=v
  • If Ki ==v:imposta il nodo corrente sul nodo puntato da Pi+1
  • Altrimenti, imposta il nodo corrente sul nodo puntato da Pi

Chiavi duplicate

In generale, la chiave di ricerca può essere duplicata, per risolvere questo problema, la maggior parte delle implementazioni di database fornisce una chiave di ricerca composita. Ad esempio, vogliamo creare un indice su student_name quindi la nostra chiave di ricerca composita dovrebbe essere (student_name, Ap) dove Ap è la chiave primaria della tabella.

Pro

Ci sono due caratteristiche principali offerte da B+tree:

• Ridurre al minimo le operazioni di I/O
  • Altezza ridotta:B+Tree ha un fattore di ramificazione piuttosto ampio (valore spesso utilizzato tra 50 e 2000) che rende l'albero grasso e basso. La figura seguente illustra un B+Albero con altezza di 2. Come possiamo vedere i nodi sono sparsi, ci vogliono meno nodi per attraversare una foglia. Il costo della ricerca di un singolo valore è l'altezza dell'albero + 1 per l'accesso casuale alla tabella.
• Scalabilità:
  • Hai prestazioni prevedibili per tutti i casi, O(log(n)) in particolare. Per i database, in genere è più importante che avere prestazioni migliori o medie dei casi migliori.
  • L'albero rimane sempre bilanciato dalla sua implementazione. Un B+Albero con n chiavi ha sempre una profondità di O(log(n)). Pertanto, le prestazioni non diminuiranno se il database aumenta di dimensioni. Un albero a quattro livelli con un fattore di ramificazione di 500 può memorizzare fino a 256 TB a condizione che una pagina abbia una dimensione di 4 KB.

• B+Tree è più adatto per le query sull'intervallo, ad esempio "SELECT * FROM student WHERE age > 20 AND age < 22"

Conclusione

Sebbene l'indice hash funzioni meglio in termini di query di corrispondenza esatta, B+Tree è probabilmente la struttura dell'indice più utilizzata in RDBMS grazie alle sue prestazioni coerenti in termini di scalabilità generale e elevata.

Recentemente, l'albero di unione strutturato in log (LSM-tree) ha attirato un notevole interesse come concorrente di B+-tree, perché la sua struttura dei dati potrebbe consentire una migliore efficienza nell'utilizzo dello spazio di archiviazione. Indagherò ulteriormente e pubblicherò un post al riguardo nel prossimo futuro.