B+ Tree è un'estensione di B Tree che consente efficienti operazioni di inserimento, cancellazione e ricerca.
In B Tree, le chiavi e i record possono essere archiviati sia nei nodi interni che in quelli foglia. Mentre, nell'albero B+, i record (dati) possono essere archiviati solo sui nodi foglia mentre i nodi interni possono archiviare solo i valori chiave.
I nodi foglia di un albero B+ sono collegati insieme sotto forma di elenchi collegati singolarmente per rendere le query di ricerca più efficienti.
I B+ Tree vengono utilizzati per archiviare la grande quantità di dati che non possono essere archiviati nella memoria principale. Dato che la dimensione della memoria principale è sempre limitata, i nodi interni (chiavi per accedere ai record) dell'albero B+ sono archiviati nella memoria principale mentre i nodi foglia sono archiviati nella memoria secondaria.
I nodi interni dell'albero B+ sono spesso chiamati nodi indice. Nella figura seguente è mostrato un albero B+ di ordine 3.
Vantaggi di B+ Tree
- I record possono essere recuperati in un numero uguale di accessi al disco.
- L'altezza dell'albero rimane equilibrata e inferiore rispetto all'albero B.
- Possiamo accedere ai dati memorizzati in un albero B+ sia in sequenza che direttamente.
- Le chiavi vengono utilizzate per l'indicizzazione.
- Query di ricerca più veloci poiché i dati vengono archiviati solo sui nodi foglia.
Albero B VS Albero B+
| SN | B Albero | B+ Albero |
|---|---|---|
| 1 | Le chiavi di ricerca non possono essere memorizzate ripetutamente. | Possono essere presenti chiavi di ricerca ridondanti. |
| 2 | I dati possono essere archiviati nei nodi foglia così come nei nodi interni | I dati possono essere archiviati solo sui nodi foglia. |
| 3 | La ricerca di alcuni dati è un processo più lento poiché i dati possono essere trovati sia sui nodi interni che sui nodi foglia. | La ricerca è relativamente più veloce poiché i dati possono essere trovati solo sui nodi foglia. |
| 4 | La cancellazione dei nodi interni è così complicata e richiede molto tempo. | L'eliminazione non sarà mai un processo complesso poiché l'elemento verrà sempre eliminato dai nodi foglia. |
| 5 | I nodi foglia non possono essere collegati tra loro. | I nodi foglia sono collegati tra loro per rendere più efficienti le operazioni di ricerca. |
Inserimento nel B+ Tree
Passo 1: Inserisci il nuovo nodo come nodo foglia
generici Java
Passo 2: Se la foglia non ha spazio richiesto, dividi il nodo e copia il nodo centrale nel nodo indice successivo.
Passaggio 3: Se il nodo indice non ha spazio richiesto, dividi il nodo e copia l'elemento centrale nella pagina indice successiva.
Esempio :
Inserire il valore 195 nell'albero B+ di ordine 5 mostrato nella figura seguente.
195 verrà inserito nel sottoalbero destro di 120 dopo 190. Inseriscilo nella posizione desiderata.
Il nodo contiene un numero di elementi superiore al massimo, ovvero 4, quindi dividerlo e posizionare il nodo mediano fino al genitore.
Ora, il nodo indice contiene 6 figli e 5 chiavi che violano le proprietà dell'albero B+, quindi dobbiamo dividerlo, come mostrato di seguito.
Cancellazione in B+ Tree
Passo 1: Elimina la chiave e i dati dalle foglie.
Passo 2: se il nodo foglia contiene meno del numero minimo di elementi, unisci il nodo con il suo fratello ed elimina la chiave tra di loro.
Passaggio 3: se il nodo indice contiene meno del numero minimo di elementi, unisci il nodo con il fratello e sposta verso il basso la chiave tra di loro.
Esempio
Eliminare la chiave 200 dal B+ Tree mostrato nella figura seguente.
200 è presente nel sottoalbero destro di 190, dopo 195. cancellalo.
Unisci i due nodi utilizzando 195, 190, 154 e 129.
Ora, l'elemento 120 è il singolo elemento presente nel nodo che sta violando le proprietà del B+ Tree. Pertanto, dobbiamo unirlo utilizzando 60, 78, 108 e 120.
Ora l'altezza dell'albero B+ verrà ridotta di 1.
