Indicizzazione B-Tree
Scorri per mostrare il menu
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.
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.
Una query di intervallo è un'operazione di database che recupera dati all'interno di un intervallo specificato di valori per un determinato attributo o colonna. Permette di recuperare i record che rientrano in un intervallo definito, come valori compresi tra due date o all'interno di un intervallo numerico. I seguenti operatori sono utilizzati nelle ricerche di intervallo: >, <, >=, <=.
Una ricerca di uguaglianza è un'operazione di database che recupera dati in base a una corrispondenza esatta di un valore specificato per un determinato attributo o colonna. Consente di trovare i record che corrispondono esattamente a un determinato criterio, come trovare tutti i clienti con un indirizzo email specifico o un particolare user ID. Queste query includono gli operatori = e <>.
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 che prevede l'attraversamento dell'albero fino a raggiungere i nodi foglia, il percorso lungo la catena dei nodi foglia per trovare i record corrispondenti e il recupero dei dati effettivi dal disco.
Nella figura è illustrata la ricerca della chiave 302:
-
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;
-
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;
-
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 evidenziato nel diagramma in rosso; -
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 da302a502avviene seguendo sequenzialmente i nodi foglia.
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 righe corrispondenti nella tabella del database.
Pro e contro
A differenza della struttura dati standard Binary Search Tree, i nodi 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,..);
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 sulla/le colonna/e specificata/e 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.
Grazie per i tuoi commenti!
Chieda ad AI
Chieda ad AI
Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione
