B-albero

Rappresentazione di un B-albero

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 $root[T]$) che soddisfa le seguenti proprietà:

1. Ogni nodo $x$ ha i seguenti attributi:
   • $n[x]$, il numero di chiavi memorizzate in $x$
   • indicando con $key_{i}[x]$ l'i-esima chiave del nodo $x$ si ha $key_{1}[x]\leq key_{2}[x]\leq ...\leq key_{n[x]}[x]$
   • $leaf[x]$ è un valore booleano che può assumere valore ${\mbox{true}}$ se il nodo $x$ è una foglia, ${\mbox{false}}$ altrimenti.
2. Ogni nodo interno ha $n[x]+1$ puntatori $c_{1}[x],c_{2}[x],...,c_{n[x]+1}[x]$ ai suoi figli.
3. Vale $c_{1}[x]\leq key_{1}[x]\leq c_{2}[x]\leq key_{2}[x]\leq ...\leq key_{n[x]}[x]\leq c_{n[x]+1}[x]$
4. Tutte le foglie hanno la stessa profondità (l'albero è completamente bilanciato)
5. Il numero di chiavi per nodo è limitato superiormente ed inferiormente. $t\geq 2$ è il grado minimo dell'albero
   • Ogni nodo contiene almeno $t-1$ chiavi
   • Ogni nodo contiene al massimo $2t-1$ 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 $R$ 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 $n$ e il suo grado minimo sia $t\geq 2$, l'altezza $h$, nel caso peggiore, sarà

$h\leq \log _{t}{n+1 \over 2}$

Del resto, se un B-Albero ha altezza $h$, risulta evidente che il numero dei suoi nodi è minimo se la radice contiene una chiave e tutti gli altri nodi contengono $t-1$ chiavi: si avranno, così, $2$ nodi a profondità 1, $2t$ nodi a profondità 2, $2t^{2}$ a profondità 3 e così via. Fissata $h$ l'altezza del B-Albero si avrà che alla profondità h vi saranno $2t^{h}-1$ nodi. Quindi il numero di chiavi sarà

$n\geq 1+2(t-1)\sum _{i=1}^{h}t^{i-1}=2t^{h}-1$

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 $n[x]$ il numero di chiavi di un generico nodo $x$ del B-Albero, avremo che ad ogni nodo interno $x$ si presenteranno $n[x]+1$ scelte alternative.

Ricerca di una chiave

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 $k$ del B-Albero a partire da un nodo $x$.

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 $\Omega (h)=\Omega (\log _{t}n)$. Inoltre $n[x]<2t$, quindi il tempo di esecuzione dell'algoritmo è, banalmente, $O(th)=O(t\log _{t}n)$.

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 $2t-1$ 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 $key_{t}[y]$ del nodo $y$ pieno. Successivamente alla divisione, il nodo pieno $y$ viene suddiviso in due nodi differenti ciascuno con $t-1$ chiavi. In concreto, la chiave mediana del nodo $y$ viene spostata nel padre del nodo $y$ (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 $k$ in un B-Albero $T$.

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 $k$ in un nodo $x$ 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 $h$ la procedura B-Tree-Insert effettua $O(h)$ accessi al disco. Il tempo di esecuzione è pari a $O(th)=O(t\log _{t}n)$.

Cancellazione

Il procedimento relativo alla cancellazione di una chiave è inverso rispetto a quello per l'inserimento. Si supponga di dover eliminare una chiave $k$ da un sottoalbero con radice $x$: in questo caso una procedura di cancellazione viene chiamata ricorsivamente sul nodo $x$ solo se il numero di chiavi di $x$ è pari al grado minimo del B-Albero $t$. I casi che si possono riscontrare quando si vuole cancellare una chiave da un B-Albero sono svariati.

• Se la chiave $k$ si trova nel nodo $x$ ed $x$ è una foglia allora è sufficiente eliminare la chiave $k$ senza ulteriori operazioni (caso banale).
• Se la chiave $k$ si trova in un nodo interno $x$ allora la procedura è più complessa. Si presentano tre sottocasi differenti (di cui due simmetrici).
  • Sia $y$ il figlio di $x$ che precede $k$; se $y$ ha almeno $t$ chiavi è necessario trovare il predecessore di $k$ nel sottoalbero che ha come radice $y$; trovato quest'ultimo e indicato con $k^{'}$ esso si cancella e successivamente si sostituisce $k$ con $k'$ in $x$.
  • Caso simmetrico al precedente. Sia $z$ il figlio di $x$ che segue $k$; se $z$ ha almeno $t$ chiavi è necessario trovare il successore di $k$ nel sottoalbero che ha come radice $z$; trovato quest'ultimo e indicato con $k^{'}$ esso si cancella e successivamente si sostituisce $k$ con $k'$ in $x$.
  • Siano $y$ e $z$ rispettivamente i figli che precedono e succedono $k$ e si supponga che abbiano $t-1$ chiavi. Allora si devono inserire nel nodo $y$ sia la chiave $k$ che tutte le chiavi di $z$; in questo caso i figli di $z$ divengono figli di $y$. Tuttavia il nodo $x$ perde $k$ e il puntatore a $z$ e il nodo $y$ diviene pieno. Quindi si deve necessariamente procedere ricorsivamente ad eliminare $k$ da $y$.
• Se $k$ non è presente in $x$ allora si determina la radice $c_{i}[x]$ del sottoalbero che contiene $k$. Si presentano due sottocasi.
  • Se $c_{i}[x]$ ha $t-1$ chiavi ed un nodo fratello con $t$ chiavi allora a $c_{i}[x]$ una chiave del padre di $x$ e poi si prende una chiave o del fratello di destra o del fratello di sinistra di $c_{i}[x]$. Successivamente si sposta il figlio opportuno dal fratello e si inserisce in $c_{i}[x]$.
  • Se $c_{i}[x]$ e i suoi fratelli hanno $t-1$ si fonde $c_{i}$ con uno dei suoi fratelli. Una chiave di $x$ scenderà nel nuovo nodo divenendone mediana.

La complessità dell'algoritmo di cancellazione in termini di accesso al disco è pari a $O(h)$ mentre la complessità temporale è $O(th)=O(t\log _{t}n)$.

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 è $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.

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.

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.