B-albero

albero di ricerca bilanciato

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.

Rappresentazione di un B-albero

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

modifica

Un B-Albero è un albero radicato (la cui radice può essere indicata come  ) che soddisfa le seguenti proprietà:

  1. 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.
  2. Ogni nodo interno ha   puntatori   ai suoi figli.
  3. Vale  
  4. Tutte le foglie hanno la stessa profondità (l'albero è completamente bilanciato)
  5. 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

modifica

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

modifica

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

modifica

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

modifica

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

modifica

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

modifica

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.

 
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   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

modifica

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

modifica

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

modifica

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

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.

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

modifica

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

modifica
  Lo stesso argomento in dettaglio: Predictive B+ tree.

Bibliografia

modifica
  • 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

modifica

Altri progetti

modifica

Collegamenti esterni

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