B-albero
![Niente fonti!](http://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Question_book-4.svg/45px-Question_book-4.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/92/B-tree-definition.png/510px-B-tree-definition.png)
Un B-albero (in inglese B-tree) è una struttura dati che permette la rapida localizzazione dei file (record o chiavi), specie nelle basi di dati, riducendo il numero di volte che un utente necessita per accedere alla memoria in cui il dato è salvato. Essi derivano dagli alberi binari 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; inoltre, la loro struttura ne garantisce il bilanciamento: per ogni nodo, le altezze dei sottoalberi destro e sinistro differiscono al più di una unità. Questo è il vantaggio principale del B-albero, e permette di compiere operazioni di inserimento, cancellazione e ricerca in tempi ammortizzati logaritmicamente.
Sono utilizzati spesso nell'ambito delle basi di dati, in quanto permettono di accedere ai nodi in maniera efficiente sia nel caso essi siano disponibili in memoria centrale (tramite una cache), sia qualora essi siano presenti solo sulla memoria di massa.
Definizione
Un B-Albero è un albero radicato (la cui radice può essere indicata come ) che soddisfa le seguenti proprietà:
- Ogni nodo ha i seguenti attributi:
- , il numero di chiavi memorizzate in
- indicando con l'i-esima chiave del nodo si ha
- è un valore booleano che può assumere valore se il nodo è una foglia, altrimenti.
- Ogni nodo interno ha puntatori ai suoi figli.
- Vale
- Tutte le foglie hanno la stessa profondità (l'albero è completamente bilanciato)
- Il numero di chiavi per nodo è limitato superiormente ed inferiormente. è il grado minimo dell'albero
- Ogni nodo contiene almeno chiavi
- Ogni nodo contiene al massimo chiavi
Vantaggi dei B-Alberi
I B-Alberi portano forti vantaggi in termini di velocità ed efficienza rispetto ad implementazioni alternative quando la maggior parte dei nodi si trovano 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. Offrono ottime prestazioni per quanto riguarda sia le operazioni di ricerca che quelle di aggiornamento, poiché entrambe possono avvenire con complessità logaritmica e attraverso l'utilizzo di procedure alquanto semplici. Su di essi è anche possibile effettuare elaborazioni di tipo sequenziale dell'archivio primario senza alcuna necessità di sottoporlo a riorganizzazione.
Struttura del nodo
Si indica con l'ordine dell'albero. È qui esposta una semplificazione della struttura nodo per un albero B-Tree implementata in C++.
struct bNode { int nChiavi; //livello di riempimento del nodo bNode* 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 };
Altezza di un B-Albero
Supponendo che il numero di chiavi di un B-Albero sia pari ad e il suo grado minimo sia , l'altezza , nel caso peggiore, sarà
Del resto, se un B-Albero ha altezza , risulta evidente che il numero dei suoi nodi è minimo se la radice contiene una chiave e tutti gli altri nodi contengono chiavi: si avranno, così, nodi a profondità 1, nodi a profondità 2, a profondità 3 e così via. Fissata l'altezza del B-Albero si avrà che alla profondità h vi saranno nodi. Quindi il numero di chiavi sarà
Creazione di un B-Albero
L'operazione di creazione di un B-Albero (inizialmente senza chiavi) richiede solo la creazione di un nodo radice.
B-Tree-Create(T) alloca un nuovo nodo x n[x] ← 0 leaf[x] ← TRUE scrivi su disco il nodo x root[T] ← x
Operazioni principali
Sono qui di seguito trattate le tre operazioni fondamentali eseguibili su un B-Tree:
- Ricerca di una chiave
- Inserimento di una chiave (necessita dell'operazione di splitting del nodo)
- Cancellazione (necessita dell'operazione di merging dei nodi)
Ricerca
La ricerca di un record di chiave k è svolta in modo analogo all'albero binario, con l'unica differenza che, ad ogni passo, le possibili scelte non sono due ma coincidono con il numero di chiavi di ciascun nodo. Posto il numero di chiavi di un generico nodo del B-Albero, avremo che ad ogni nodo interno si presenteranno scelte alternative.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e2/B-tree-search.png/510px-B-tree-search.png)
La procedura di ricerca si suddivide nei seguenti passi:
- 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.
La procedura B-Tree-Search(x,k) effettua la ricerca di una chiave del B-Albero a partire da un nodo .
B-Tree-Search(x,k)
i ← 1
while i <= n[x] && k > keyi[x] do
i ← i+1
if i <= n[x] && k = keyi[x] then
return (x,i)
if leaf[x] then
return NIL
else
leggi dal disco il nodo ci[x]
return B-Tree-Search(ci[x],k)
Poiché nella procedura di ricerca il B-Albero viene percorso lungo un cammino dalla radice ad una foglia, il numero di accessi al disco è pari a . Inoltre , quindi il tempo di esecuzione dell'algoritmo è, banalmente, .
Inserimento
L'inserimento di una nuova chiave può presentare più difficoltà rispetto alla medesima procedura per un albero binario in quanto è fondamentale mantenere l'albero bilanciato. Operazione preliminare, che deve essere opportunamente implementata, per poter realizzare una funzione per l'inserimento di una chiave in un B-Albero è l'operazione di divisione di un nodo pieno. Un nodo di un B-Albero si definisce pieno se contiene esattamente chiavi: essendo pieno, in fase di inserimento di una chiave, essa non può, per la definizione stessa di B-Albero, essere eventualmente inserita all'interno di esso. L'operazione di divisione viene effettuata in corrispondenza della chiave mediana del nodo pieno. Successivamente alla divisione, il nodo pieno viene suddiviso in due nodi differenti ciascuno con chiavi. In concreto, la chiave mediana del nodo viene spostata nel padre del nodo (non pieno). L'operazione di divisione di un nodo, chiaramente, aumenta l'altezza dell'albero.
B-Tree-Split-Child(x,i,y) alloca il nodo z leaf[z] ← leaf[y] n[z] ← t-1 for j ← 1 to t-1 do keyj[z] ← keyj+t[y] if not leaf[y] then for j ← 1 to t do c_j[z] ← cj+t[y] n[y] ← t-1 for j ← n[x]+1 downto i+1 do cj+1[x] ← cj[x] ci+1[x] ← z for j ← n[x] downto i do keyj+1[x] ← keyj[x] keyi[x] ← keyt[y] n[x] ← n[x]+1 scrivi su disco i nodi y,z,x
L'operazione di inserimento di una chiave viene realizzata grazie ad una visita dell'albero che, sfruttando la procedura di splitting del nodo, evita che essa venga inserita in un nodo già pieno. Al primo passo della procedura di inserimento si verifica se la radice del B-Albero sia piena: in tal caso essa viene divisa all'altezza della chiave mediana; quest'ultima diverrà l'unica chiave di un nuovo nodo radice; a questo punto si può effettuare la procedura vera e propria di inserimento mediante un'apposita funzione ricorsiva che si occupa di inserire la chiave nella posizione corretta. Nel caso in cui la radice dell'albero, invece, non sia piena si può procedere direttamente con l'inserimento. A tal scopo si possono implementare due procedure: B-Tree-Insert che si occupa di verificare se la radice sia piena o meno e B-Tree-Insert-Nonfull che si occupa di effettuare la visita ricorsiva dell'albero per inserire la chiave nella corretta corrispondenza. Quest'ultima procedura viene invocata comunque dalla prima procedura, ma se la radice è piena viene preliminarmente effettuato il suo split. Si supponga di voler inserire una chiave in un B-Albero .
B-Tree-Insert(T,k) //se la radice è piena if n[r] = 2t-1 then alloca un nodo s root[t] ← s //il nodo s sarà la nuova radice leaf[s] ← FALSE n[s] ← 0 c1[s] ← r //splitting del nodo r (precedentemente era la radice) B-Tree-Split-Child(s,1,r) //chiamata alla procedura ricorsiva di inserimento a partire da s B-Tree-Insert-Nonfull(s,k) //se la radice non è piena else //chiamata alla procedura ricorsiva di inserimento a partire da r B-Tree-Insert-Nonfull(r,k)
La procedura B-Tree-Insert-Nonfull inserisce la chiave in un nodo non pieno del B-Albero.
B-Tree-Insert-Nonfull(x,k) //se il nodo x è una foglia if leaf[x] then //si scorrono le chiavi di x per trovare la posizione corretta per k while i >= 1 && k < keyi[x] do keyi+1[x] ← keyi[x] i ← i-1 //inserimento della chiave keyi+1[x] ← k //aggiornamento del campo n[x] n[x] ← n[x]+1 scrivi su disco il nodo x //se il nodo x non è una foglia occorre determinare in quale //sottoalbero procedere ricorsivamente a seconda del valore di k else while i >= 1 && k < keyi[x] do i ← i-1 i ← i+1 //il nodo è stato trovato leggi dal disco il nodo ci[x] //se il nodo è pieno if n[ci[x]] = 2t-1 //splitting del nodo then B-Tree-Split-Child(x,i,ci[x]) if k > keyi[x] then i ← i+1 //se il nodo non è pieno o è già stato diviso si può //procedere ricorsivamente con la visita B-Tree-Insert-Nonfull(ci[x],k)
La complessità dell'algoritmo di inserimento in un B-Albero va valutata in funzione del numero di accessi al disco sia per la lettura dei nodi che per la scrittura. Supponendo che l'altezza del B-Albero sia la procedura B-Tree-Insert effettua accessi al disco. Il tempo di esecuzione è pari a .
Cancellazione
Il procedimento relativo alla cancellazione di una chiave è inverso rispetto a quello per l'inserimento. Si supponga di dover eliminare una chiave da un sottoalbero con radice : in questo caso una procedura di cancellazione viene chiamata ricorsivamente sul nodo solo se il numero di chiavi di è pari al grado minimo del B-Albero . I casi che si possono riscontrare quando si vuole cancellare una chiave da un B-Albero sono svariati.
- Se la chiave si trova nel nodo ed è una foglia allora è sufficiente eliminare la chiave senza ulteriori operazioni (caso banale).
- Se la chiave si trova in un nodo interno allora la procedura è più complessa. Si presentano tre sottocasi differenti (di cui due simmetrici).
- Sia il figlio di che precede ; se ha almeno chiavi è necessario trovare il predecessore di nel sottoalbero che ha come radice ; trovato quest'ultimo e indicato con esso si cancella e successivamente si sostituisce con in .
- Caso simmetrico al precedente. Sia il figlio di che segue ; se ha almeno chiavi è necessario trovare il successore di nel sottoalbero che ha come radice ; trovato quest'ultimo e indicato con esso si cancella e successivamente si sostituisce con in .
- Siano e rispettivamente i figli che precedono e succedono e si supponga che abbiano chiavi. Allora si devono inserire nel nodo sia la chiave che tutte le chiavi di ; in questo caso i figli di divengono figli di . Tuttavia il nodo perde e il puntatore a e il nodo diviene pieno. Quindi si deve necessariamente procedere ricorsivamente ad eliminare da .
- Se non è presente in allora si determina la radice del sottoalbero che contiene . Si presentano due sottocasi.
- Se ha chiavi ed un nodo fratello con chiavi allora a una chiave del padre di e poi si prende una chiave o del fratello di destra o del fratello di sinistra di . Successivamente si sposta il figlio opportuno dal fratello e si inserisce in .
- Se e i suoi fratelli hanno si fonde con uno dei suoi fratelli. Una chiave di scenderà nel nuovo nodo divenendone mediana.
La complessità dell'algoritmo di cancellazione in termini di accesso al disco è pari a mentre la complessità temporale è .
Varianti del B-tree
Esistono diverse varianti al B-tree. Le tre più diffuse sono:
- Il B+tree
- Il B*tree
- Il prefix B-tree
- Il predictive B+tree
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. Tale collegamento consente di svolgere in maniera efficiente anche interrogazioni su un intervallo di valori ammissibili. 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 è
- Il minimo numero di chiavi è
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.
Questo tipo di struttura trova applicazione nei file system Journaled File System, HPFS, Be File System, ReFS, ReiserFS e XFS.
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.
Questo tipo di struttura trova applicazione nei file system Reiser4, HFS, HFS Plus e Btrfs.
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.
Predictive B+ tree
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/87/Magnifying_glass_icon_mgx2.svg/18px-Magnifying_glass_icon_mgx2.svg.png)
Bibliografia
- Renato Conte, Il Mondo Degli Oggetti Vol. 2
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduzione agli algoritmi. Jackson Libri, 2003, ISBN 88-256-1421-7.
Voci correlate
- Albero (informatica)
- RB-Albero
Altri progetti
Altri progetti
- Wikimedia Commons
Wikimedia Commons contiene immagini o altri file sul B-albero
Collegamenti esterni
- (EN) Eric W. Weisstein, B-Tree, su MathWorld, Wolfram Research.
- Semaphore Corporation - B-tree algorithms, su semaphorecorp.com. URL consultato il 18 marzo 2006 (archiviato dall'url originale il 15 marzo 2006).
- Peter Neubauer - Balanced Tree Data Structures, su bluerwhite.org. URL consultato il 18 marzo 2006 (archiviato dall'url originale il 5 marzo 2010).
V · D · M | |
---|---|
Tipi | Collezione · Container |
Astratte | Array associativo (Multimap) · Lista · Pila · Coda (Deque) · Coda di priorità · Set (Multiset · Mfset) |
Array | Bit array · Buffer circolare · Array dinamico · Hash table · Array sparso |
Collegate | Lista di associazioni · Lista concatenata · Skip list · Unrolled linked list · Lista concatenata tramite XOR |
Alberi | B-albero · Albero binario di ricerca (Albero AA · Albero AVL · RB-Albero · Albero binario di ricerca bilanciato · Albero splay) · Heap (Heap binario · Heap binomiale · Heap di Fibonacci) · Albero di Merkle · Albero SPQR · Albero PQ · Albero indicizzato binario |
Grafi | Diagramma binario di decisione · Digrafo aciclico · Automa a stati finiti deterministico aciclico |
Alberi di partizionamento dei dati spaziali | Albero quadramentale · M-tree · R-tree (R* tree · R+ tree) · X-tree |
Lista di strutture dati |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/24px-Computer_n_screen.svg.png)