B-Tree

I B-Tree sono alberi bilanciati di ricerca adatti per essere usati su memoria secondaria. Hanno un fattore di ramificazione molto alto. 

Ciò consente ai B-Tree di avere un’altezza più bassa rispetto ad altri tipi di alberi bilanciati, a parità di numero di record.   

Esempio B-Tree

Definizione di B-Tree

Un B-Tree T è un albero con radice root[T] che gode delle seguenti proprietà:

1. Ciascun Nodo x ha i seguenti campi:

• , numero delle chiavi in
• Le chiavi in ordine non decrescente:
• , campo booleano tale che:

2. Ciascun Nodo interno contiene puntatori ai figli
3. Se denota una chiave del sottoalbero di radice , per , vale:

• Da cui segue che il B-Tree è un albero di ricerca.

4. Tutte le foglie hanno la stessa profondità (uguale quindi all’altezza dell’albero)
5. Il B-Tree è caratterizzato da una quantità , detta , tale che:

• tutti i nodi, eccezion fatta per la radice, devono contenere ALMENO chiavi.
• tutti i nodi devono contenere al più chiavi.
• Un nodo che contiene chiavi si dice PIENO
• Cioè deve valere:

Teorema: Altezza B-Tree

L'Altezza h di un B-Tree T di grado minimo t contenente n chiavi, con n \geq 1, soddisfa:

livello	# nodi	# chiavi
0	1	1
1	2
2
3
…	…	…
i
…	…	…
h

Dimostrazione

Risolviamo per h:

Questa dimostrazione risponde alla domanda:

“Si fornisca (con dimostrazione) un limite superiore per l’altezza di un B-tree di grado minimo t con n chiavi.”

Con nodi pieni:

livello	# nodi	# chiavi
0	1	2t-1
1	2t
2
3
…	…	…
h

Si procede come prima. 

Risolviamo nuovamente per h: 

Il -1 entra nel logaritmo dividendo per 2t. 

Perciò, infine, otteniamo: 

 

Operazioni di Base sui B-Tree

Search

x punta alla radice, k è la chiave cercata. 

Create

…

Inserimento Key

Procedura naturale: Due possibili passate. 

• Si effettua la ricerca per trovare la foglia in cui inserire k;
• Se tale foglia non è piena, si inserisce k nel posto opportuno.
• Altrimenti, si spezza la foglia piena:

Si spezzano i nodi durante la discesa. 

Esempio

BTree di grado minimo: t = 3, max: 2t-1 = 5

Cancellazione Key

Procedura naturale: due possibili passate sempre. 

• Si effettua la ricerca per trovare il nodo che contiene la chiave k;
• Se tale nodo è una foglia con almeno t chiavi (cioè non è magro), si cancella direttamente.
• Se invece la foglia è magra, si farà cedere una chiave da una foglia sorella (se possibile).
  • Se non è possibile, dal nodo padre, contestualmente unendosi a una foglia sorella.
  • Tale processo potrebbe propagarsi fino alla radice.
• Se il nodo che contiene k è invece un nodo interno, si sostituisce k con la chiave immediatamente più piccola (o più grande) di k, e si cancella il predecessore (o il successore) di k, che risiederà sicuramente su una foglia.
• Per evitare la possibile risalita si farà in modo che i nodi sul cammino dalla radice al nodo contenente k NON siano magri (eccezion fatta per la radice);
• Pertanto, supponiamo che il nodo x in esame non sia magro.
• Inoltre, supponiamo anche che se la radice rimane senza alcune chiave, viene deallocata.

Schematizziamo la procedura:

Application

1. Se è nel nodo ed è una foglia, si cancelli da .
2. Se è nel nodo ed è un nodo interno:
3. Se il figlio di che precede ha almeno chiavi, si determini il predecessore di nel sottoalbero radicato in y. Si cancelli ricorsivamente e si sostituisca con
4. Situazione simmetrica di 2.1, per il figlio di che segue
5. Altrimenti, se sia che hanno (magri), si uniscono e il nodo a , si cancella da , si dealloca e si cancella ricorsivamente da
6. Se k non è presente nel nodo interno , si determina la radice del sottoalbero di che contiene :

• Se è magro, si esegue il passo 3.1 o 3.2 e quindi ricorsivamente si rimuove la chiave k dal sottoalbero che la contiene

1. Se ha un fratello immediato non magro:
2. Se entrambi i fratelli immediati di sono magri

• Altrimenti, se non è magro, si proceda ricorsivamente a cancellare la chiave k a partire dal nodo