B-Albero

Da Wikipedia, l'enciclopedia libera.

I B-Alberi (o B-Tree) sono strutture dati ad albero, vengono comunemente utilizzati nell’ambito di database e filesystem. Essi derivano dagli alberi di ricerca, in quanto ogni chiave appartenente al sottoalbero sinistro di un nodo è di valore inferiore rispetto a ogni chiave appartenente ai sottoalberi alla sua destra; derivano anche dagli alberi bilanciati perché tutte le foglie si trovano alla stessa distanza rispetto alla radice. Il vantaggio principale dei B-Tree è che essi mantengono automaticamente i nodi bilanciati permettendo operazioni di inserimento, cancellazione e ricerca in tempi ammortizzati logaritmicamente.

Indice 1 Caratteristiche principali 2 Vantaggi dei B-Tree 3 Struttura del nodo: implementazione in C++ 4 Tecniche principali 4.1 Ricerca 4.2 Inserimento 4.3 Inserimento (splitting) 4.4 Cancellazione (merging) 5 Varianti del B-tree 5.1 B+Tree 5.2 B*Tree 5.3 Prefix B-Tree 6 Collegamenti esterni 7 Bibliografia

[modifica] Caratteristiche principali

• Assegnare ad un B-tree un ordine n significa dire che i nodi interni conterranno da n/2 (approssimato per difetto) a n-1 chiavi [dif(n/2), n-1].
• Una corrispondente lista di puntatori è situata tra le chiavi per indicare dove cercare una chiave se non è nel nodo corrente. Un nodo contenente k chiavi contiene sempre k+1 puntatori. Il numero di puntatori è detto fattore di ramificazione.
• La radice contiene almeno una chiave
• In un nodo le chiavi sono ordinate secondo ordine crescente.
• Ad ogni chiave è associato un puntatore ad una informazione.

[modifica] Vantaggi dei B-Tree

I B-Tree portano forti vantaggi in termini di velocità ed efficienza rispetto ad implementazioni alternative quando la maggior parte dei nodi si trova in una memoria secondaria, ad esempio in un disco fisso. Massimizzando il numero di nodi figli per ogni nodo, l’altezza dell’albero si riduce, l’operazione di bilanciamento è necessaria meno spesso e quindi l'efficienza aumenta. Generalmente questo numero è impostato in modo tale che ogni nodo occupi per intero un gruppo di settori: così, dato che le operazioni di basso livello accedono al disco per cluster, si minimizza il numero di accessi ad esso.

[modifica] Struttura del nodo: implementazione in C++

Si ricorda che R è l'ordine dell’albero. È qui esposta una semplificazione della struttura nodo per un albero B-Tree.

struct bNode
  
{
  int nChiavi;    //livello di riempimento del nodo
 
  long RifPagina [2*R+1];  //vettore di puntatori ai nodi figli
 
  tipoChiave K [2*R];   //vettore ordinato di 2*R chiavi;
 
  long RifInfo [2*R];    //vettore di puntatori a informazioni su archivio
 
};

[modifica] Tecniche principali

Sono qui di seguito trattate tre tecniche fondamentali per l’utilizzo e la comprensione del funzionamento del B-Tree:

• Ricerca di una chiave
• Inserimento di una chiave - splitting
• Cancellazione - merging

[modifica] Ricerca

La ricerca di un record di chiave k è svolta in modo analogo all'albero binario:

• Trasferimento in memoria della radice
• Ricerca di K nella pagina trasferita: se è presente, la ricerca è terminata.
• Altrimenti, se K è minore della chiave più a sinistra del nodo, allora trasferimento della pagina puntata dal puntatore di sinistra (se non è nullo); se K è maggiore della chiave più a destra allora trasferimento della pagina puntata dal puntatore più a destra (se non è nullo); se è compreso tra due chiavi del nodo allora trasferimento della pagina puntata dal puntatore compreso tra le due chiavi (se non è nullo). Ritorno al punto 2.
• Se il puntatore in questione è nullo, la chiave non è presente.

In questo modo, il numero massimo di pagine da leggere per la ricerca coincide con l’altezza dell’albero. Poiché è possibile dimostrare che l’altezza dell’albero dipende dal logaritmo del numero di record del file, la lunghezza (o costo) della ricerca è una funzione logaritmica del numero di record del file. Il B-tree è inoltre tanto più conveniente quanto più il file è grande e la ricerca è più veloce tanto più sono piene le singole pagine.

NB: R è l’ordine dell’albero ed N il numero di record presenti nell’archivio.

[modifica] Inserimento

L’inserimento di una nuova chiave all’interno di un B-Tree può presentare più difficoltà rispetto a come visto per il Binary Tree, in quanto è fondamentale mantenere il bilanciamento dei nodi.

• Effettuare la ricerca della chiave da inserire sul B-Tree. Se essa non è presente, abbiamo ottenuto la posizione del nodo dove va effettuato l’inserimento.
• Se nel nodo corrente il numero di chiavi inserite è inferiore a 2R, la chiave può essere inserita senza bisogno di bilanciamenti.
• Se il nodo è invece pieno, si da luogo allo splitting, ovvero esso viene sdoppiato in due nodi.

[modifica] Inserimento (splitting)

• Si individua la chiave centrale tra quelle che dovrebbero stare nel nodo: si ottiene così una suddivisione del nodo in 3 sottocategorie, per comodità si considera la chiave da inserire come parte del nodo, anche se fisicamente non è ancora stata inserita:
• Chiavi precedenti (minori di quella centrale)
• Chiave centrale
• Chiavi successive (maggiori di quella centrale)
• Le R chiavi della prima sottocategoria restano nella stessa posizione, le R chiavi della 3’ categoria vengono spostate in un nuovo nodo appartenente allo stesso livello di quello d’origine, mentre la chiave centrale viene mossa in su verso il nodo padre.

Se la pagina padre non esiste, viene creata una nuova pagina radice; se esiste e non è piena riceve la chiave e la inserisce nella giusta posizione; se la pagina padre è piena si sdoppia e si verifica nuovamente lo splitting. Nella peggiore delle ipotesi, gli split si propagano fino alla radice e l’altezza aumenta di 1. L’albero resta comunque perfettamente bilanciato. Rimane bilanciato poiché nello splitting i nodi che non sono la radice vengono divisi in due creando un fratello (quindi alla stessa altezza), mentre solo una volta giunti alla radice potrà avvenire l'effettivo aumento di altezza, dividendo la "vecchia" radice e creandone una nuova ad una chiave.

[modifica] Cancellazione (merging)

Il procedimento relativo alla cancellazione di una chiave è inverso rispetto a quello per l’inserimento. Se la cancellazione va eseguita per una chiave di una foglia, essa viene eliminata e si compatta il vettore di chiavi. Se la chiave non si trova su una foglia, essa deve essere sostituita da una delle due chiavi adiacenti che si trovano in una foglia (generalmente si tratta della chiave successiva nell’ordinamento). Se nel rimuovere una chiave si hanno meno di R chiavi all’interno del nodo, le chiavi vengono distribuite presso nodi vicini, ma se questa operazione di ribilanciamento non fosse ancora sufficiente a mantenere R chiavi in una pagina, si procede alla tecnica del merging, ovvero alla fusione di due pagine. Se la somma del numero delle chiavi delle due pagine è minore di 2R, il merging fa sì che gli elementi delle due pagine ed il loro separatore confluiscano in un’unica pagina.

Se il merging si propaga fino al nodo radice, l’altezza dell’albero diminuisce di 1.

[modifica] Varianti del B-tree

Esistono diverse varianti al B-Tree che abbiamo appena preso in considerazione, le tre più diffuse sono:

• Il B+Tree
• Il B-*Tree
• Il prefix B-Tree

[modifica] B+Tree

A differenza del B-Tree, nel B+Tree tutti i dati sono salvati nelle foglie. I nodi interni contengono solamente chiavi e puntatori. Tutte le foglie sono allo stesso livello. I nodi foglia sono inoltre collegati assieme come una lista per rendere il recupero di informazioni più semplici. Il numero massimo di chiavi in un record è detto ordine R del B+Tree. Il numero minimo di chiavi per record è R/2. Il numero di chiavi che può essere indicizzato utilizzando un B+Tree è in funzione di R e dell’altezza dell’albero. Per un B+Tree di ordine n-esimo e di altezza h:

• Il massimo numero di chiavi è: n^h
• Il minimo numero di chiavi è: 2(n / 2)^{h − 1}

Di tutte le varianti del B-Tree, questa è la più usata, perché tutti i primi nodi interni che la memoria centrale può contenere vengono mantenuti su di essa mentre il resto dei nodi e le foglie vengono lasciate su memoria di massa. Ciò permette una maggior velocità di ricerca.

[modifica] B*Tree

Un B*Tree è una struttura dati sviluppata per la gestione di grandi quantità di informazioni, è composta da 2 parti: il direttorio e l’archivio.

• L’archivio è costituito di record, ognuno dei quali può essere visto come una coppia chiave-informazione.
• Il direttorio è organizzato ad albero: le foglie contengono gli indici, cioè le coppie chiave-puntatore che consentono di individuare i record nell’archivio, mentre la parte superiore dell’albero ha il solo compito di condurre alla rapida individuazione dell’indice contenente la chiave cercata.

La variante principale sta però nelle foglie dell'albero, le quali sono collegate tra loro tramite una catena di puntatori, in modo da consentire una scansione sequenziale dell’archivio.

[modifica] Prefix B-Tree

Il prefix B-Tree è un'evoluzione del B*Tree. Nei prefix B-Tree i nodi del direttorio non contengono necessariamente chiavi intere, ma generici separatori, cioè chiavi che possono essere state private della loro parte iniziale (il prefisso); l’intera chiave può essere ricostruita a partire dal separatore corrispondente, conoscendo la posizione nell'albero del nodo in cui esso è contenuto. Le foglie dell'albero contengono invece chiavi intere, al fine di rendere più efficace la ricerca sequenziale.

[modifica] Collegamenti esterni

• Semaphore Corporation - B-tree algorithms
• Peter Neubauer - Balanced Tree Data Structures
• Spataro Fabrizio e Todaro Michelangelo - Emulatore Java BTree - BTree Java Emulator

[modifica] Bibliografia

• Renato Conte; Il Mondo Degli Oggetti Vol.2