Gli alberi B+, una variante dei B-Tree

I dati di un albero B+ sono contenuti soltanto nelle foglie

Gli alberi B+ sono una variante degli alberi B, in particolare un albero B viene definito albero B+ se i riferimenti ai dati contenuti nell’albero sono presenti soltanto nelle foglie (e non in un qualsiasi nodo). Inoltre, ogni foglia dell’albero B+ deve contenere un ulteriore campo puntatore che consente di spostarsi tra le foglie come in una lista doppiamente collegata (linked list).

In genere, le foglie di un albero B+ non contengono i dati ma solo indici. Di conseguenza la struttura dei nodi foglia differisce da quella dei nodi interni che contengono i dati da memorizzare. Anche per gli alberi B+, per motivi di efficienza, la radice dell’albero deve essere tenuta costantemente in memoria centrale.

Gli alberi B+ sono una struttura dati molto utile per le operazioni di ricerca, i nodi dell’albero hanno una entry ed un puntatore da un record per tutti i campi chiave contenuti nell’albero. Per i campi dell’albero che non hanno chiave, i puntatori indirizzano un blocco che contiene i puntatori ai record del file dei dati (costringendo però ad un passo aggiuntivo per l’accesso ai dati).
Per migliorare la ricerca, alcuni valori del campo di ricerca presenti nei nodi foglia sono ripetuti nei nodi interni per guidare la ricerca.

Di seguito è mostrato un esempio di albero B+ con le foglie doppiamente puntate:

Gli alberi B+, una variante dei B-Tree

Photo Credit: Wiki Commons

Pubblicato in Sistemi Informativi Taggato con: ,

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

*