Tecniche basate su B-Tree

La parte superiore contiene i valori della chiave di ricerca, la parte inferiore contiene il puntatore

all'area dati che contiene la tupla con chiave espressa nella chiave superiore. Le barrette laterali

contengono puntatori a nodi figli, a sinistra c'è un sottoalbero con chiavi di valore minore mentre

a destra c'è un sottoalbero con chiavi di valore maggiore. Non tutte le caselle sono riempite. I

nodi foglia non hanno figli come in un tipico albero, quindi le loro barre laterali punteranno al

nulla. Quest'albero è detto n-ario, cioè ogni nodo può avere più figli.

Date x chiavi si avranno x+1 figli.

Da notare che per dei nodi non terminali un sottoalbero è figlio destro di un nodo e figlio sinistro

di un altro. Un B-Tree di grado 4 ha nodi che contengono 3 chiavi. Il grado di un B-Tree è dato

dal numero di figli che si possono avere oppure il numero massimo di figli in un nodo. Il grado di

un B-Tree si sceglie a priori e dipende da quanto è grande la chiave e quanto è grande la pagina.

Solitamente i puntatori sono da 32/64 bit. le chiavi sono grandi rispetto l'attributo al quale creo il

B-Tree. Ogni nodo, che corrisponde ad una pagina determina la dimensione totale che le chiavi

ed i puntatori devono avere. Ad esempio se la pagina è 4KB, bisogna determinare il grado del B-

2 / 6

Tecniche basate su B-Tree

Tree sulla base di quante chiavi e puntatori si possono mettere per arrivare a 4KB.

Nota la dimensione della pagina e la dimensione dei puntatori che dipendono dal sistema, presa

una chiave di ricerca si può stabilire il numero di caselle massime per pagina. Questo numero è il

grado.

La ricerca avviene come in un albero normale, accedendo ad ogni passo ad un nodo del livello

corrente. Un B-Tree è messo di default sulla chiave primaria perchè coinvolta con i vincoli di

chiavi esterne. Il costo d'accesso di un B-Tree nel caso peggiore è pari all'altezza del B-Tree. Il

B-Tree ha garantito un bilanciamento molto forte ossia, tutte le foglie stanno alla stessa altezza,

questo fa si che l'altezza diventi logaritmica rispetto al grado del B-Tree ed essendo di solito la

base del logaritmo molto larga questo fa si che i B-Tree abbiano un altezza molto bassa.

Nel B-Tree bisogna stare attenti ad avere nodi sufficientemente pieni, evitando quindi una

struttura sparsa che ha prestazioni scadenti.

Proprietà di un B-Tree di grado m

Ogni nodo ha la struttura descritta in precedenza dove i nodi sono ordinati ed il

K , . . . K

1 m

sottoalbero puntato da , contiene chiavi di se e minori di se

p K + 1 i > 1 K i < m

i i i

Se un nodo ha x chiavi e non è foglia allora ha x+1 figli.

Se un nodo ha x figli ha x-1 chiavi

Tutte le foglie sono alla stessa altezza

Ogni nodo non radice possiede almeno chiavi, ossia 50%. Questa proprietà è una

m

⌈ ⌉ − 1

2

proprietà minima, nella pratica si raggiunge una percentuale di riempimento anche del 80%.

Un B-Tree è molto efficiente se garantisce le proprietà elencate.

Inserimento e rimozione in un B-Tree

Vediamo adesso la logica dietro l'inserimento in un B-Tree.

3 / 6

Tecniche basate su B-Tree

Quando voglio inserire 30, il nodo risulta pieno perciò si spezza la radice e si creano nodi pieni

secondo la proprietà di riempimento ossia . Ogni inserimento quindi si fa nell'ultimo

m

⌈ ⌉ − 1

2

livello, l'albero perciò cresce verso l'alto non verso il basso come accadeva per gli alberi binari.

Ogni volta che si deve inserire un valore bisogna scandire dalla radice alla foglia, quindi si fanno

accessi con altezza del B-Tree. Nel caso peggiore si deve splittare una foglia quindi il costo è

h h

di letture e scritture. Il numero di nodi foglia, in B-Tree di grado m è dato da:

h 2h + 1 h−1

m − 1 se B-Tree è pieno, dove sono i nodi

2 3 h−2 h−1

1 + m + m + m +. . . +m + m = m − 1

m − 1

prima dell'ultimo livello e, è il numero di nodi all'ultimo livello. Di queste scritture

h−1

m 2h + 1

in memoria secondaria ne faccio solo 2 e delle letture ne faccio solo 1.

h

Se il grado è 100, i nodi all'ultimo livello sono 100 volte di più di quelli di tutto il resto

dell'albero.

La rimozione deve sempre garantire le proprietà. Nel rimuovere un nodo possiamo ricondurci al

caso in cui il nodo sia nella foglia spostando, il nodo alla foglia più a destra del sottoalbero

4 / 6

Tecniche basate su B-Tree

sinistro.

supponiamo di trovarci in questa situazione e di voler rimuovere 20. Adesso il nodo che lo

conteneva è sceso sotto la soglia di riempimento minimo, a questo punto prendo tutti i valori

dell'insieme non riempito al minimo, in questo caso solo 10, il valore del nodo padre, 30 in

questo caso e i valori del sottoalbero destro/sinistro, 40, 50 e 60 in questo caso. Faccio così una

rotazione a seconda del caso e verifico che la condizione di riempimento minimo sia mantenuta.

Supponiamo poi di voler rimuovere il valore 30, fatte tutte le operazioni necessari si avrà come

situazione finale la seguente:

Il costo della rimozione di una foglia con un albero con altezza è definito in 2 casi:

h

1. La chiave da eliminare non rende necessario né una rotazione né un accorpamento quindi il

costo è dato da letture, in quanto scendo fino alle foglie per trovare la chiave da eliminare

h

ed 1 scrittura, che sarebbe la cancellazione. 5 / 6