B TREE nella struttura dati: esempio di operazione di ricerca, inserimento, eliminazione

Cos'è un albero B?

B Tree è una struttura dati autobilanciata basata su un insieme specifico di regole per la ricerca, l'inserimento e l'eliminazione dei dati in modo più veloce ed efficiente in termini di memoria. Per ottenere ciò, vengono seguite le seguenti regole per creare un albero B.

Un B-Tree è un tipo speciale di albero in una struttura dati. Nel 1972, questo metodo fu introdotto per la prima volta da McCreight e Bayer lo chiamò Albero di ricerca m-way bilanciato in altezza. Ti aiuta a conservare i dati ordinati e consente varie operazioni come l'inserimento, la ricerca e l'eliminazione in meno tempo.

In questo tutorial B-Tree imparerai:

Cos'è un albero B?
Perché usare B-Tree
Storia di B Tree
Operazione di ricerca
Inserisci operazione
Elimina operazione

Regole per B-Tree

Qui ci sono regole importanti per creare B_Tree

Tutte le foglie verranno create allo stesso livello.
B-Tree è determinato da un numero di gradi, chiamato anche "ordine" (specificato da un attore esterno, come un programmatore), indicato come
```
m
```
in poi. Il valore di
```
m
```
dipende dalla dimensione del blocco sul disco su cui si trovano principalmente i dati.
La sottostruttura sinistra del nodo avrà valori inferiori rispetto al lato destro della sottostruttura. Ciò significa che anche i nodi vengono ordinati in ordine crescente da sinistra a destra.
Il numero massimo di nodi figlio, un nodo radice e i suoi nodi figlio possono contenere sono calcolati da questa formula:
```
m - 1
```
Per esempio:
```
m = 4max keys: 4 - 1 = 3
```

Ogni nodo, eccetto root, deve contenere un minimo di chiavi di
```
[m/2]-1
```
Per esempio:
```
m = 4min keys: 4/2-1 = 1
```
Il numero massimo di nodi figlio che un nodo può avere è uguale al suo grado, che è
```
m
```
Il numero minimo di figli che un nodo può avere è la metà dell'ordine, che è m / 2 (viene preso il valore del soffitto).
Tutte le chiavi in un nodo vengono ordinate in ordine crescente.

Perché usare B-Tree

Ecco i motivi per utilizzare B-Tree

Riduce il numero di letture effettuate sul disco
B Gli alberi possono essere facilmente ottimizzati per regolarne le dimensioni (ovvero il numero di nodi figli) in base alle dimensioni del disco
È una tecnica appositamente progettata per gestire una quantità ingente di dati.
È un algoritmo utile per database e file system.
Una buona scelta da scegliere quando si tratta di leggere e scrivere grandi blocchi di dati

Storia di B Tree

I dati vengono memorizzati sul disco in blocchi, questi dati, quando vengono portati nella memoria principale (o RAM), vengono chiamati struttura dati.
In caso di dati di grandi dimensioni, la ricerca di un record nel disco richiede la lettura dell'intero disco; ciò aumenta il tempo e il consumo di memoria principale a causa dell'elevata frequenza di accesso al disco e della dimensione dei dati.
Per ovviare a questo, vengono create tabelle indice che salvano il riferimento record dei record in base ai blocchi in cui risiedono. Ciò riduce drasticamente il tempo e il consumo di memoria.
Poiché disponiamo di dati enormi, possiamo creare tabelle indice multilivello.
L'indice multilivello può essere progettato utilizzando B Tree per mantenere i dati ordinati in modo autobilanciato.

Operazione di ricerca

L'operazione di ricerca è l'operazione più semplice su B Tree.

Viene applicato il seguente algoritmo:

Lascia la chiave (il valore) da cercare con "k".
Inizia la ricerca dalla radice e prosegui ricorsivamente verso il basso.
Se k è minore del valore radice, cerca nel sottoalbero sinistro, se k è maggiore del valore radice, cerca nel sottoalbero destro.
Se il nodo ha trovato k, restituisci semplicemente il nodo.
Se la k non viene trovata nel nodo, spostati verso il basso fino al figlio con una chiave maggiore.
Se k non viene trovato nell'albero, restituiamo NULL.

Inserisci operazione

Poiché B Tree è un albero autobilanciato, non è possibile forzare l'inserimento di una chiave in un nodo qualsiasi.

Si applica il seguente algoritmo:

Eseguire l'operazione di ricerca e trovare il punto di inserimento appropriato.
Inserisci la nuova chiave nella posizione corretta, ma se il nodo ha già un numero massimo di chiavi:
Il nodo, insieme a una chiave appena inserita, verrà diviso dall'elemento centrale.
L'elemento centrale diventerà il genitore per gli altri due nodi figli.
I nodi devono riorganizzare le chiavi in ordine crescente.

MANCIA

Quanto segue non è vero per l'algoritmo di inserimento:

Poiché il nodo è pieno, quindi verrà diviso e quindi verrà inserito un nuovo valore

Nell'esempio sopra:

Cerca la posizione appropriata nel nodo per la chiave
Inserisci la chiave nel nodo di destinazione e controlla le regole
Dopo l'inserimento, il nodo ha più che uguale a un numero minimo di chiavi, che è 1? In questo caso, sì, lo fa. Controlla la regola successiva.
Dopo l'inserimento, il nodo ha più di un numero massimo di chiavi, che è 3? In questo caso no, non lo fa. Ciò significa che l'albero B non viola alcuna regola e l'inserimento è completo.

Nell'esempio sopra:

Il nodo ha raggiunto il numero massimo di chiavi
Il nodo si dividerà e la chiave centrale diventerà il nodo radice degli altri due nodi.
In caso di numero pari di chiavi, il nodo centrale verrà selezionato con polarizzazione sinistra o polarizzazione destra.

Nell'esempio sopra:

Il nodo ha meno del numero massimo di chiavi
1 viene inserito accanto a 3, ma la regola dell'ordine crescente viene violata
Per risolvere questo problema, le chiavi vengono ordinate

Allo stesso modo, 13 e 2 possono essere inseriti facilmente nel nodo poiché soddisfano la regola del numero massimo di chiavi per i nodi.

Nell'esempio sopra:

Il nodo ha chiavi pari al numero massimo di chiavi.
La chiave viene inserita nel nodo di destinazione, ma viola la regola del numero massimo di chiavi.
Il nodo di destinazione è diviso e la chiave centrale per il bias sinistro è ora il genitore dei nuovi nodi figlio.
I nuovi nodi sono disposti in ordine crescente.

Allo stesso modo, in base alle regole e ai casi di cui sopra, il resto dei valori può essere facilmente inserito nell'albero B.

Elimina operazione

L'operazione di eliminazione ha più regole rispetto alle operazioni di inserimento e ricerca.

Si applica il seguente algoritmo:

Esegui l'operazione di ricerca e trova la chiave di destinazione nei nodi
Tre condizioni applicate in base alla posizione della chiave di destinazione, come spiegato nelle sezioni seguenti

Se la chiave di destinazione si trova nel nodo foglia

La destinazione è nel nodo foglia, più di chiavi min.
- L'eliminazione non violerà la proprietà di B Tree
La destinazione è nel nodo foglia, ha nodi chiave min
- L'eliminazione di questo violerà la proprietà di B Tree
- Il nodo di destinazione può prendere in prestito la chiave dal nodo sinistro immediato o dal nodo destro immediato (fratello)
- Il fratello dirà di sì se ha più del numero minimo di chiavi
- La chiave verrà presa in prestito dal nodo padre, il valore massimo verrà trasferito a un nodo padre, il valore massimo del nodo padre verrà trasferito al nodo di destinazione e rimuoverà il valore di destinazione
La destinazione si trova nel nodo foglia, ma nessun fratello ha un numero di chiavi superiore al minimo
- Cerca la chiave
- Unisci con i fratelli e il minimo di nodi padre
- Le chiavi totali saranno ora più di min
- La chiave di destinazione verrà sostituita con il minimo di un nodo padre

Se la chiave di destinazione si trova in un nodo interno

Scegli, predecessore in ordine o successore in ordine
Nel caso del predecessore in ordine, verrà selezionata la chiave massima dalla sua sottostruttura sinistra
In caso di successore in ordine, verrà selezionata la chiave minima dalla sua sottostruttura destra
Se il predecessore in ordine della chiave di destinazione ha più delle chiavi min, solo allora può sostituire la chiave di destinazione con il massimo del predecessore in ordine
Se il predecessore in ordine della chiave di destinazione non ha più di chiavi min, cercare la chiave minima del successore in ordine.
Se il predecessore in ordine e il successore della chiave di destinazione hanno entrambi un numero di chiavi inferiore a min, unire il predecessore e il successore.

Se la chiave di destinazione si trova in un nodo radice

Sostituisci con l'elemento massimo della sottostruttura del predecessore in ordine
Se, dopo l'eliminazione, la destinazione ha meno di chiavi min, il nodo di destinazione prenderà in prestito il valore massimo dal fratello tramite il genitore del fratello.
Il valore massimo del genitore sarà preso da un target, ma con i nodi del valore massimo del fratello.

Ora, comprendiamo l'operazione di cancellazione con un esempio.

Il diagramma sopra mostra diversi casi di operazione di cancellazione in un B-Tree. Questo B-Tree è di ordine 5, il che significa che il numero minimo di nodi figli che ogni nodo può avere è 3, e il numero massimo di nodi figli che ogni nodo può avere è 5. Considerando che il numero minimo e massimo di chiavi per ogni nodo possono avere rispettivamente 2 e 4.

Nell'esempio sopra:

Il nodo di destinazione ha la chiave di destinazione da eliminare
Il nodo di destinazione ha più chiavi del numero minimo di chiavi
Elimina semplicemente la chiave

Nell'esempio sopra:

Il nodo di destinazione ha chiavi uguali alle chiavi minime, quindi non è possibile eliminarlo direttamente poiché violerà le condizioni

Ora, il diagramma seguente spiega come eliminare questa chiave:

Il nodo di destinazione prenderà in prestito una chiave dal fratello immediato, in questo caso, il predecessore in ordine (fratello sinistro) perché non ha alcun successore in ordine (fratello destro)
Il valore massimo del predecessore inordine verrà trasferito al genitore e il genitore trasferirà il valore massimo al nodo di destinazione (vedere il diagramma sotto)

L'esempio seguente illustra come eliminare una chiave che necessita di un valore dal suo successore in ordine.

Il nodo di destinazione prenderà in prestito una chiave dal fratello immediato, in questo caso, il successore in ordine (fratello destro) perché il suo predecessore in ordine (fratello sinistro) ha chiavi uguali alle chiavi minime.
Il valore minimo del successore in ordine verrà trasferito al genitore e il genitore trasferirà il valore massimo al nodo di destinazione.

Nell'esempio seguente, il nodo di destinazione non ha alcun fratello che può fornire la sua chiave al nodo di destinazione. Pertanto, è necessaria la fusione.

Vedere la procedura per eliminare tale chiave:

Unisci il nodo di destinazione con uno qualsiasi dei suoi fratelli immediati insieme alla chiave genitore
- La chiave dal nodo padre è selezionata che i fratelli si trovano tra i due nodi di fusione
Elimina la chiave di destinazione dal nodo unito

Elimina lo pseudo codice dell'operazione

private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {answer = subset[childCount-1].removeBiggestElement()if (subset[childCount-1].dataCount < MINIMUM)fixShort (childCount-1)return answer}}

Uscita :

L'elemento più grande viene eliminato dal B-Tree.

Sommario:

B Tree è una struttura dati autobilanciata per una migliore ricerca, inserimento ed eliminazione dei dati dal disco.
B Tree è regolato dal grado specificato
B Le chiavi e i nodi dell'albero sono disposti in ordine crescente.
L'operazione di ricerca di B Tree è la più semplice, che parte sempre dalla radice e inizia a verificare se la chiave di destinazione è maggiore o minore del valore del nodo.
Piuttosto dettagliata è l'operazione di inserimento di B Tree, che prima trova una posizione di inserimento appropriata per la chiave di destinazione, la inserisce, valuta la validità di B Tree rispetto a casi diversi, quindi ristruttura di conseguenza i nodi B Tree.
L'operazione di eliminazione di B Tree cerca prima la chiave di destinazione da eliminare, la elimina, valuta la validità in base a diversi casi come le chiavi minima e massima del nodo di destinazione, dei fratelli e del padre.