Un indice B-tree è una struttura dati ad albero bilanciato comunemente utilizzata nei database per organizzare e ricercare in modo efficiente grandi volumi di dati.
I B-tree sono molto simili ai binary search trees (BST), ma i nodi in un B-tree possono avere più di due figli. Puoi approfondire i BST nel corso Panoramica su Algoritmi e Strutture Dati.

Il B-tree memorizza le chiavi in ordine ordinato all'interno dei nodi, consentendo un recupero rapido dei dati tramite una traversata gerarchica dalla radice ai nodi foglia. L'indicizzazione B-tree è particolarmente adatta per query di intervallo e ricerche di uguaglianza, rendendola una scelta popolare per ottimizzare le prestazioni dei database.

Come funziona?

L'indice B-tree organizza i dati in modo gerarchico, con ciascun nodo che contiene un numero fisso di chiavi e puntatori ai nodi figli.
I B-tree mantengono l'equilibrio assicurando che tutti i nodi foglia siano allo stesso livello, ottimizzando così le operazioni di ricerca.
Durante la ricerca di una chiave specifica, l'algoritmo B-tree attraversa l'albero dal nodo radice fino ai nodi foglia, utilizzando la ricerca binaria per individuare in modo efficiente la chiave desiderata.

Ricerca tramite indice implica l'attraversamento dell'albero fino a raggiungere i nodi foglia, seguendo la catena dei nodi foglia per trovare i record corrispondenti e recuperare i dati effettivi dal disco.

Nella figura, è illustrata la ricerca della chiave 302:

1. Una struttura ad albero di ricerca è un tipo di albero in cui ogni nodo ha due puntatori: il puntatore sinistro indica i nodi figli con valori inferiori rispetto al nodo genitore, mentre il puntatore destro indica i nodi figli con valori superiori rispetto al nodo genitore;

2. In un B-tree, il nodo radice può contenere più valori di indice. Ad esempio, se la radice contiene tre valori distinti, avrà tre puntatori, ciascuno dei quali indica l'intervallo di valori compreso tra quei valori chiave;

3. Per cercare una chiave, come 302, la ricerca inizia dal nodo radice e segue i puntatori appropriati fino ai nodi foglia. La ricerca si conclude dopo aver attraversato tre blocchi dell'albero, come mostrato nel diagramma evidenziato in rosso;

4. Per cercare un intervallo di valori a partire da 302, è possibile utilizzare i puntatori orizzontali tra i nodi foglia. Ad esempio, il recupero dei valori da 302 a 502 avviene seguendo sequenzialmente i nodi foglia.

Nota

La chiave utilizzata per la ricerca in un indice B-tree deriva dai valori memorizzati nelle colonne indicizzate della tabella del database. Ad esempio, se l'indice è su una colonna come "client_id", la chiave di ricerca sarà costituita dai valori effettivi di "client_id". Ogni valore numerico univoco nella colonna indicizzata funge da chiave nell'indice B-tree, facilitando la ricerca e il recupero delle relative righe nella tabella del database.

Vantaggi e svantaggi

A differenza della struttura dati standard dell'albero di ricerca binaria, i nodi di un B-tree possono contenere più di 2 figli. Il numero massimo predefinito di figli per nodo è solitamente impostato a 16.

Implementazione dell'indice

Per creare un indice B-tree su una colonna in PostgreSQL, è possibile utilizzare il seguente comando SQL:

CREATE INDEX index_name ON table_name USING BTREE (column_name1, column_name2,...);

Poiché l'indice B-tree è un indice predefinito in SQL, è possibile utilizzare anche la seguente istruzione per crearlo:

CREATE INDEX index_name ON table_name(column_name1, column_name2,..);

Nota

In SQL, quando si crea una tabella con un vincolo di chiave primaria, la maggior parte dei sistemi di gestione di database crea automaticamente un indice sulle colonne specificate nella chiave primaria. Questo indice aiuta a far rispettare il vincolo di unicità della chiave primaria e migliora anche le prestazioni delle query che coinvolgono la ricerca o la join basata sulle colonne della chiave primaria.