BTREE e le sue varianti

La mia tesi - BTREE

(clicca per ingrandire)
I Btree sono alberi bilanciati di ricerca progettati per le operazioni sui dispositivi di memoria ad accesso diretto.
Grazie all'uso della struttura dati ad albero e la caratteristica di poter memorizzare piu' chiavi in un nodo, il Btree (Bilanced Tree) e' la struttura dati migliore per la gestione delle memorie esterne.
Come accennato per ogni nodo dell'albero possono essere memorizzate al massimo 2*t-1 chiavi, con t grado di ramificazione.
Per ogni nodo poi ci saranno al massimo 2*t figli... ricapitolando:

Tipo di nodoLimite InferioreLimite Superiore
Radice12*t-1
Altri nodit-12*t-1

Nel caso in cui il numero di elementi in un nodo e' uguale al limite inferiore/superiore il nodo stesso si dice magro/pieno.
I nodi a profondita' massima vengono chiamati foglie, tutte le foglie sono alla stessa profondita' (che coincide con l'altezza dell'albero).
I Btree sono alberi bilanciati, e il bilanciamento e' gestito dalle funzioni di gestione dei nodi magri (merge) e pieni (split).

Le operazioni effettuate in un Btree rispecchiano quelle di un qualunque albero binario, con in aggiunta la gestione dei nodi magri e pieni.


Costo delle operazioni
Poiche' la visita di un nodo in un Btree richiede un accesso alla memoria secondaria, il numero di nodi visitati durante un'operazione forniscono una misura dei costi che e' quasi sempre proporzionale all'altezza.

Altezza di un Btree
Ad eccezione della radice, ogni nodo in un Btree ha al piu' t-1 discendenti diretti, mentre la radice ne ha almeno 2.
Cosi' che il numero di nodi e' in relazione con l'altezza nel seguente modo:

Altezza hNodi n
01
12*t^0
22*t^1
......
h2*t^h-1
Dove t e' il fattore di ramificazione

Da cui:






Da cio' possiamo dedurre che in un Btree con t=50 e circa 1.000.000 di record, una chiave puo' essere cercata con al piu' 4 accessi al disco!

Operazioni di base
Si possono schematizzare nel seguente modo:
    1. Creazione di un BTree
    2. Inserimento di una chiave (Gestione dei nodi pieni)
    3. Eliminazione di una chiave (Gestione dei nodi magri)
    4. Ricerca di una chiave
    5. Vista del BTree


Gestione dei nodi pieni (SplitChild)
La procedura divide un nodo x pieno all'altezza della mediana, in due nodi magri.
La chiave mediana viene spostata nel padre del nodo x, che naturalmente non deve essere pieno, in modo tale si possa identificare il punto di divisione dei nuovi sotto-alberi.
Se il nodo x e' la radice, l'altezza dell'albero aumenta di una unita'.

L'operazione di Split e' un'operazione di crescita degli alberi.


Inserimento
Quando si vuole inserire una chiave in un BTree il concetto e' semplice. Se durante lo scorrimento dell'albero per trovare il nodo interessato, viene incontrato un nodo pieno avviene uno split (divisione).


Gestione dei nodi magri (Merge)
La fusione tra due nodi avviene quando i nodi interessati sono magri, cosi' che il nodo ottenuto dalla fusione risulti pieno.

Cancellazione
Analogamente all'operazione di inserimento, quando viene incontrato un nodo magro si cerca di effettuare un merge con il fratello oppure una donazione dal fratello.
Naturalmente la donazione tra fratelli nodi interni avviene coinvolgendo anche i sottoalberi interessati.












Ultimo aggiornamento: Luglio 2010
FabryProg Site e' online dal 2000
FabryProg Site è interamente realizzato in HTML, PHP e MySQL