B-albero

I B-Alberi (comunemente noti come B-Tree cioè Balanced-Tree) sono strutture dati ad albero, vengono comunemente utilizzati nell'ambito di database e dispositivi di memoria secondaria e ad accesso diretto. 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.

Struttura del B-tree

Definizione

Un B-Albero è un albero radicato (la cui radice può essere indicata come ${\displaystyle root[T]}$ ) che soddisfa le seguenti proprietà:

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

Struttura del nodo

Si indica con ${\displaystyle 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
 
  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
 
};

Altezza di un B-Albero

Supponendo che il numero di chiavi di un B-Albero sia pari ad ${\displaystyle n}$  e il suo grado minimo sia ${\displaystyle t\geq 2}$ , l'altezza ${\displaystyle h}$ , nel caso peggiore, sarà

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

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

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

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 (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 figli di ciascun nodo. Posto ${\displaystyle n[x]}$  il numero di figli di un generico nodo ${\displaystyle x}$  del B-Albero, avremo che ad ogni nodo interno ${\displaystyle x}$  si presenteranno ${\displaystyle n[x]+1}$  scelte alternative.

 

Ricerca di una chiave

La procedura di ricerca si suddivie 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 ${\displaystyle k}$  del B-Albero a partire da un nodo ${\displaystyle x}$ .

 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 percoeso lungo un cammino dalla radice ad una foglia, il numero di accessi al disco è pari a ${\displaystyle \Omega (h)=\Omega (\log _{t}n).Inoltre<math>n[x]<2t}$ , quindi il tempo di esecuzione dell'algoritmo è, banalmente, ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle key_{t}[y]}$  del nodo ${\displaystyle y}$  pieno. Successivamente alla divisione, il nodo pieno ${\displaystyle y}$  viene suddiviso in due nodi differenti ciascuno con ${\displaystyle t-1}$  chiavi. In concreto, la chiave mediana del nodo ${\displaystyle y}$  viene spostata nel padre del nodo ${\displaystyle 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 effettuata effettuando una visita dell'albero e, sfruttando la procedura di splitting del nodo, evitando 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à unica chiave di un nuovo nodo radice; a questo punto si può procedere alla 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 proecdure: 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 ${\displaystyle k}$  in un B-Albero ${\displaystyle 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 ${\displaystyle k}$  in un nodo ${\displaystyle 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 ${\displaystyle h}$  la procedura B-Tree-Insert effettua ${\displaystyle O(h)}$  accessi al disco. Il tempo di esecuzione è pari a ${\displaystyle 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 ${\displaystyle k}$  da un sottoalbero con radice ${\displaystyle x}$ : in questo caso una procedura di cancellazione viene chiamata ricorsivamente sul nodo ${\displaystyle x}$  solo se il numero di chiavi di ${\displaystyle x}$  è pari al grado minimo del B-Albero ${\displaystyle t}$ . I casi che si possono riscontrare quando si vuole cancellare una chiave da un B-Albero sono svariati.

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

La complessità dell'algoritmo di cancellazione in termini di accesso al disco è pari a ${\displaystyle O(h)}$  mentre la complessità temporale è ${\displaystyle 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

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 è: ${\displaystyle n^{h}}$ 
• Il minimo numero di chiavi è: ${\displaystyle 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.

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 e HFS Plus.

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.

Collegamenti esterni

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

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica