Gli alberi B, struttura con sottoalberi variabili

Alberi bilanciati simili agli alberi Rosso-Nero ma con n+1 figli

Gli alberi B sono una struttura dati avanzata che consente una rapida localizzazione dei file all’interno di un sistema, in modo particolare con i file contenuti nei database. I B-Alberi, o B-Tree, vengono spesso rappresentati come degli alberi bilanciati e sono molto simili agli alberi Rosso-Neri (Red-Black), ma rispetto a questi ultimi riducono in modo drastico il numero di accessi alla memoria.

La struttura interna degli alberi B deriva dagli alberi di ricerca: dato un nodo, tutti i suoi figli contenuti nel suo sottoalbero sinistro sono inferiori (numericamente) dei nodi contenuti nei sottoalberi alla sua destra. Gli alberi B garantiscono il bilanciamento dei nodi dell’albero e riscono a mantenere la differenza d’altezza dei sottoalberi destro e sinistro al massimo di uno.
La principale differenza tra gli alberi B e gli alberi Rosso-Nero è che i nodi dei B-Alberi contengono un numero di chiavi con n = 1 ed n+1 figli. Ricordiamo che gli alberi Rosso-Nero hanno una sola chiave e (solo) due figli, quindi a differenza dei B-Alberi hanno un numero prefissato di sottoalberi.

Vediamo un esempio:

Gli alberi B, struttura efficiente con sottoalberi variabili

Si può notare che in questa struttura dati, tutti i figli di qualsiasi nodo sono inferiori numericamente ai nodo contenuti nei loro sottoalberi destri. Ad esempio, possiamo vedere che nella radice, tutte le chiavi contenute nel suo sottoalbero sinistro sono inferiori a 15, abbiamo 3, 7 e 11; mente nel sottoalbero destro abbiamo 22 e 30. Se si hanno più chiavi all’interno di un nodo, il sottoalbero tra le due chiavi conterrà solo chiavi non inferiori alla chiave minore e non superiori alla chiave maggiore (ad esempio tra 7 e 11, il sottoalbero contiene le chiavi 8 e 10).

Un B-Albero offre operazioni molto efficienti come l’inserimento, la cancellazione e la ricerca che avvengono in tempi logaritmici. Le operazioni elementari che si effettuano sugli alberi B avvengono in tempi ragionevoli in quanto:

  • La radice del B-albero è sempre in memoria;
  • I nodi passati come parametri alle procedure sono preventivamente caricati in memoria.

Le operazioni di inserimento e cancellazione in un albero B

Inserimento. L’aggiunta di una nuova chiave ad un albero B non può essere fatta ad un nodo interno in quanto si dovrebbe aggiungere anche un nuovo sottoalbero, l’aggiunta di un nodo può avvenire soltanto in una foglia.
Cancellazione. Eliminare una chiave da un albero B risulta molto efficiente in quanto è possibile eliminare una chiave solo se si tratta di una foglia oppure solo se la chiave non ha il minimo numero di chiavi o è radice del B-Albero.

Gli alberi B vengono spesso utilizzati con i database in quanto offrono un efficiente accesso ai nodi presenti nell’albero sia nel caso in cui i dati sono disponibili in memoria centrale (con una cache), sia nel caso in cui si trovino su una memoria secondaria. In particolare, un albero B avendo la radice stabilmente in memoria, con due accessi al disco è possibile accedere a qualsiasi chiave nella struttura.

Una variante degli alberi B è rappresentata dagli alberi B+ e dagli alberi R.

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 *

*