Il Btree + (B+Tree o Btree plus) e' una variante del BTree molto sfruttata nello sviluppo di FS (RaiserFS, XFS....).
La caratteristica principale e' l'utilizzo di un puntatore aggiuntivo tra le foglie dell'albero.
In questa maniera possiamo benissimo sfruttare sia la ricerca dell'albero (O(Logh)) che l'accesso in una lista (O(k)).
Anche nel BTree+ valgono le seguenti regole:
| Tipo di nodo | Limite Inferiore | Limite Superiore |
| Radice | 1 | 2*t-1 |
| Altri nodi | t-1 | 2*t-1 |
Altezza di un Btree+
Un UpperBound sull'altezza di un BTree+ avente n foglie puo' essere calcolato nel modo seguente:
dove t e' il grado minimo del BTree+.
Ed il numero di nodi interni m sara' al piu':
Operazioni di base
Si possono schematizzare nel seguente modo:
1. Creazione di un BTree
2. Inserimento di una chiave
2a. Gestione dei nodi pieni
2b. Gestione dei nodi foglia pieni
3. Eliminazione di una chiave
3a. Gestione dei nodi magri
3b. Gestione dei nodi foglia magri
4. Ricerca di una chiave
5. Vista del BTree
Divisione dei nodi (SplitChild & SplitChildLeaf)
L'operazione di SplitChild prevede la divisione di un nodo interno pieno in due nodi interni magro. E' ereditata da BTree
L'operazione di SplitChildLeaf prevede la divisione di un nodo foglia pieno in due nodi foglia. Utilizza SplitChild e poi copia la chiave "mediana" nel figlio di sx.
N.B. L'operazione di SplitChildLeaf puo' non produrre due figli magri.
Inserimento
Dato che tutte le chiavi devono essere inserite in foglia, viene percorso l'albero dalla radice fino alla foglia.
Se durante lo scorrimento dell'albero troviamo:
1. Un nodo interno pieno, viene eseguito lo SplitChild
2. Se invece il nodo pieno e' anche la radice dell'albero, viene eseguito lo SplitChild con un nuovo nodo (vuoto), questa operazione aumenta l'altezza dell'albero.
Alla fine dello scorrimento arriviamo certamente ad un nodo foglia.
Se la foglia non e' piena la chiave viene inserita, altrimenti:
Se il nodo foglia e' radice, viene eseguito lo SplitChildLeaf con un nuovo nodo (aumentando anche qui l'altezza dell'albero);
Altrimenti viene eseguito lo SplitChildLeaf tra il genitore del nodo foglia e la foglia stessa.
La chiave viene inserita quando si giunge al nodo foglia corrispondente.
Fusione dei nodi (Merge & MergeLeaf)
La procedura di fusione dei nodi interni (Merge) e' ereditata dal Btree.
La fusione dei nodi foglia (MergeLeaf) consiste nel comprimere gli elementi inseriti nei due nodi foglia magri in una foglia.
Cancellazione
Come nell'inserimento viene percorso l'albero fino a trovare la foglia che dovrebbe contenere la chiave.
Durante lo scorrimento dell'albero possiamo trovare un nodo interno magro:
1. Se uno dei fratelli del nodo non e' magro allora viene donato un elemento (con i corrispettivi sottoalberi).
2. Se entrambi i fratelli del nodo sono magri avviene una fusione (Merge).
Quando viene raggiunto il nodo foglia, se e' magro e:
1. Se e' la radice si elimina la chiave (albero vuoto!).
2. Se il nodo foglia fratello dx non e' magro, viene donata una chiave alla foglia rendendola cosi' non magra e poter quindi effettuare la cancellazione della chiave.
3. Lo stesso comportamento avviene se il nodo foglia fratello dx e' magro ma il nodo foglia sx non lo e'.
4. Se sia il fratello sx che quello dx sono magri avviene una fusione tra le foglie (MergeLeaf).
(ultima modifica il 13 Novembre 2005)
|
