Prima di capire Albero B E Albero B+ differenze, dovremmo conoscere l’albero B e l’albero B+ separatamente.
Cos'è l'albero B?
Albero B è un albero autobilanciante ed è un albero a m vie dove m definisce l'ordine dell'albero. Btree è una generalizzazione di Albero di ricerca binaria in cui un nodo può avere più di una chiave e più di due figli a seconda del valore di M . Nell'albero B, i dati vengono specificati in un ordine ordinato con valori più bassi nel sottoalbero di sinistra e valori più alti nel sottoalbero di destra.
nozioni di base sul selenio
Proprietà dell'albero B
Le seguenti sono le proprietà dell'albero B:
- Nell'albero B tutti i nodi foglia devono essere allo stesso livello, mentre nel caso di un albero binario i nodi foglia possono trovarsi a livelli diversi.
Capiamo questa proprietà attraverso un esempio.
Nell'albero sopra, tutti i nodi foglia non sono allo stesso livello, ma hanno al massimo due figli. Pertanto, possiamo dire che l'albero sopra è a albero binario ma non un albero B.
- Se il Btree ha un ordine di m, allora ogni nodo può avere un massimo di M Nel caso di figli minimi, i nodi foglia hanno zero figli, il nodo radice ha due figli e i nodi interni hanno un tetto di m/2.
- Ogni nodo può avere un massimo di chiavi (m-1). Ad esempio, se il valore di m è 5, il valore massimo delle chiavi è 4.
- Il nodo radice ha almeno una chiave, mentre tutti gli altri nodi tranne il nodo radice hanno chiavi minime (tetto di m/2 meno - 1).
- Se eseguiamo l'inserimento nell'albero B, allora il nodo viene sempre inserito nel nodo foglia.
Supponiamo di voler creare un albero B di ordine 3 inserendo valori da 1 a 10.
Passo 1: Innanzitutto, creiamo un nodo con 1 valore come mostrato di seguito:
Passo 2: L'elemento successivo è 2, che viene dopo 1 come mostrato di seguito:
Passaggio 3: L'elemento successivo è 3 e viene inserito dopo 2 come mostrato di seguito:
Poiché sappiamo che ogni nodo può avere 2 chiavi massime, divideremo questo nodo tramite l'elemento centrale. L'elemento centrale è 2, quindi si sposta sul genitore. Il nodo 2 non ha alcun genitore, quindi diventerà il nodo radice come mostrato di seguito:
Passaggio 4: L'elemento successivo è 4. Poiché 4 è maggiore di 2 e 3, verrà aggiunto dopo il 3 come mostrato di seguito:
Passaggio 5: L'elemento successivo è 5. Poiché 5 è maggiore di 2, 3 e 4, verrà aggiunto dopo 4 come mostrato di seguito:
Poiché sappiamo che ogni nodo può avere 2 chiavi massime, divideremo questo nodo tramite l'elemento centrale. L'elemento centrale è 4, quindi si sposta sul genitore. Il genitore è il nodo 2; pertanto, 4 verrà aggiunto dopo 2 come mostrato di seguito:
Passaggio 6: L'elemento successivo è 6. Poiché 6 è maggiore di 2, 4 e 5, quindi 6 verrà dopo 5 come mostrato di seguito:
Passaggio 7: L'elemento successivo è 7. Poiché 7 è maggiore di 2, 4, 5 e 6, quindi 7 verrà dopo 6 come mostrato di seguito:
Poiché sappiamo che ogni nodo può avere 2 chiavi massime, divideremo questo nodo tramite l'elemento centrale. L'elemento centrale è 6, quindi si sposta sul genitore come mostrato di seguito:
Ma non è possibile aggiungere 6 dopo 4 perché il nodo può avere un massimo di 2 chiavi, quindi divideremo questo nodo tramite l'elemento centrale. L'elemento centrale è 4, quindi si sposta sul genitore. Poiché il nodo 4 non ha alcun genitore, il nodo 4 diventerà un nodo radice come mostrato di seguito:
Cos'è un albero B+?
IL Albero B+ è anche conosciuto come un albero avanzato autobilanciato perché ogni percorso dalla radice dell'albero alla foglia ha la stessa lunghezza. Qui, la stessa lunghezza significa che tutti i nodi foglia si trovano allo stesso livello. Non accadrà che alcuni nodi foglia si trovino al terzo livello e altri al secondo livello.
Un indice ad albero B+ è considerato un indice a più livelli, ma la struttura ad albero B+ non è simile ai file sequenziali dell'indice a più livelli.
Perché viene utilizzato l'albero B+?
Un albero B+ viene utilizzato per archiviare i record in modo molto efficiente archiviando i record in modo indicizzato utilizzando la struttura indicizzata dell'albero B+. Grazie all'indicizzazione multilivello, l'accesso ai dati diventa più rapido e semplice.
Struttura dei nodi dell'albero B+
La struttura dei nodi dell'albero B+ contiene puntatori e valori chiave mostrati nella figura seguente:
Come possiamo osservare nella struttura del nodo ad albero B+ sopra, contiene n-1 valori chiave (k1a kn-1) e n puntatori (p1superioreN).
I valori delle chiavi di ricerca inseriti nel nodo vengono mantenuti in ordine. Quindi, se i
Vincolo su varie tipologie di nodi
Sia 'b' l'ordine dell'albero B+.
Nodo non foglia
Sia 'm' rappresenta il numero di figli di un nodo, quindi la relazione tra l'ordine dell'albero e il numero di figli può essere rappresentata come:
Sia k rappresenta i valori della chiave di ricerca. La relazione tra l'ordine dell'albero e la chiave di ricerca può essere rappresentata come:
Poiché sappiamo che il numero di puntatori è uguale ai valori della chiave di ricerca più 1, quindi matematicamente può essere scritto come:
Numero di puntatori (o figli) = Numero di chiavi di ricerca + 1
Pertanto, il numero massimo di puntatori sarebbe 'b' e il numero minimo di puntatori sarebbe la funzione tetto di b/2.
Nodo fogliare
polimorfismo in Java
Un nodo foglia è un nodo che si trova all'ultimo livello dell'albero B+ e ciascun nodo foglia utilizza solo un puntatore per connettersi tra loro per fornire l'accesso sequenziale al livello foglia.
Nel nodo foglia, il numero massimo di figli è:
Il numero massimo di chiavi di ricerca è:
Nodo radice
Il numero massimo di figli nel caso del nodo radice è: b
Il numero minimo di bambini è: 2
Casi speciali nell'albero B+
Caso 1: Se il nodo radice è l'unico nodo nell'albero. In questo caso il nodo radice diventa il nodo foglia.
In questo caso, il numero massimo di figli è 1, cioè il nodo radice stesso, mentre il numero minimo di figli è b-1, che è lo stesso di un nodo foglia.
Rappresentazione di un nodo foglia nell'albero B+
Nella figura sopra, '.' rappresenta il puntatore, mentre 10, 20 e 30 sono i valori chiave. Il puntatore contiene l'indirizzo in cui è memorizzato il valore della chiave, come mostrato nella figura precedente.
Esempio di albero B+
Nella figura sopra, il nodo contiene tre valori chiave, ovvero 9, 16 e 25. Il puntatore che appare prima di 9 contiene i valori chiave inferiori a 9 rappresentati da kio. Il puntatore visualizzato prima di 16 contiene i valori chiave maggiori o uguali a 9 ma inferiori a 16 rappresentati da kj. Il puntatore che appare prima di 25 contiene i valori chiave maggiori o uguali a 16 ma minori di 25 rappresentati da kN.
Differenze tra albero B e albero B+
Di seguito sono riportate le differenze tra l'albero B e l'albero B+:
| Albero B | Albero B+ |
|---|---|
| Nell'albero B, tutte le chiavi e i record sono archiviati sia nei nodi interni che in quelli foglia. | Nell'albero B+, le chiavi sono gli indici archiviati nei nodi interni e i record sono archiviati nei nodi foglia. |
| Nell'albero B, le chiavi non possono essere memorizzate ripetutamente, il che significa che non vi è alcuna duplicazione di chiavi o record. | Nell'albero B+ può esserci ridondanza nell'occorrenza delle chiavi. In questo caso, i record sono archiviati nei nodi foglia, mentre le chiavi sono archiviate nei nodi interni, quindi nei nodi interni possono essere presenti chiavi ridondanti. |
| Nel Btree i nodi foglia non sono collegati tra loro. | Nell'albero B+, i nodi foglia sono collegati tra loro per fornire l'accesso sequenziale. |
| In Btree, la ricerca non è molto efficiente perché i record sono archiviati in nodi foglia o interni. | Nell'albero B+, la ricerca è molto efficiente o più rapida perché tutti i record sono archiviati nei nodi foglia. |
| L'eliminazione dei nodi interni è molto lenta e richiede molto tempo poiché dobbiamo considerare anche il figlio della chiave eliminata. | La cancellazione nell'albero B+ è molto veloce perché tutti i record sono archiviati nei nodi foglia, quindi non dobbiamo considerare il figlio del nodo. |
| In Btree non è possibile l'accesso sequenziale. | Nell'albero B+, tutti i nodi foglia sono collegati tra loro tramite un puntatore, quindi è possibile l'accesso sequenziale. |
| In Btree, maggiore è il numero di operazioni di frazionamento per cui l'altezza aumenta rispetto alla larghezza, | L'albero B+ ha maggiore larghezza rispetto all'altezza. |
| In Btree, ogni nodo ha almeno due rami e ogni nodo contiene alcuni record, quindi non è necessario attraversare i nodi foglia per ottenere i dati. | Nell'albero B+, i nodi interni contengono solo puntatori e i nodi foglia contengono record. Tutti i nodi foglia sono allo stesso livello, quindi dobbiamo attraversare fino ai nodi foglia per ottenere i dati. |
| Il nodo radice contiene almeno da 2 a m figli dove m è l'ordine dell'albero. | Il nodo radice contiene almeno da 2 a m figli dove m è l'ordine dell'albero. |