B TREE: esempio di operazione di ricerca, inserimento, eliminazione

Cos’è un albero B?

B Tree è una struttura di dati autobilanciata basata su un insieme specifico di regole per la ricerca, l’inserimento e l’eliminazione dei dati in modo più rapido ed efficiente in termini di memoria. Per raggiungere questo obiettivo, vengono seguite le seguenti regole per creare un albero B.

Un B-Tree è un tipo speciale di albero in una struttura di dati. Nel 1972, questo metodo fu introdotto per la prima volta da McCreight e Bayer lo chiamò Height Balanced m-way Search Tree. Ti aiuta a preservare i dati ordinati e ha consentito varie operazioni come l’inserimento, la ricerca e l’eliminazione in meno tempo,

Regole per B-Tree

Qui, ci sono regole importanti per la creazione di B_Tree

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

Ogni nodo, ad eccezione di root, deve contenere chiavi minime di[m/2]-1Per esempio:m = 4 min keys: 4/2-1 = 1
Il numero massimo di nodi figlio che un nodo può avere è uguale al suo grado, che èm
I figli minimi che un nodo può avere sono la metà dell’ordine, che è m/2 (il valore del massimale è preso).
Tutte le chiavi in un nodo sono ordinate in ordine crescente.

Perché usare B-Tree

Ecco, ci sono i motivi per usare B-Tree

Riduce il numero di letture effettuate sul disco
B Trees può essere facilmente ottimizzato per regolarne le dimensioni (ovvero il numero di nodi figlio) in base alle dimensioni del disco
È una tecnica appositamente progettata per gestire una quantità ingombrante di dati.
È un algoritmo utile per database e file system.
Una buona scelta per optare quando si tratta di leggere e scrivere grandi blocchi di dati

Storia di B Tree

I dati sono memorizzati sul disco in blocchi, questi dati, quando portati nella memoria principale (o RAM) sono chiamati struttura dei dati.
In caso di dati enormi, 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 delle dimensioni dei dati.
Per ovviare a questo problema, vengono create tabelle di indice che salvano il riferimento al 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 di indici 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 che la chiave (il valore) venga cercata da “k”.
Inizia a cercare dalla radice e attraversa 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 la k trovata, è sufficiente restituire il nodo.
Se la k non viene trovata nel nodo, attraversare il figlio con una chiave maggiore.
Se k non viene trovato nell’albero, restituiamo NULL.

Operazione di inserimento

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 luogo di inserimento appropriato.
Inserire 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, si dividerà dall’elemento centrale.
L’elemento centrale diventerà il padre per gli altri due nodi figlio.
I nodi devono riorganizzare le chiavi in ordine crescente.

Mancia

Quanto segue non è vero per l’algoritmo di inserimento:Poiché il nodo è pieno, quindi si dividerà e quindi verrà inserito un nuovo valore

Nell’esempio precedente:

Cercare la chiave nella posizione appropriata nel nodo
Inserire la chiave nel nodo di destinazione e verificare la presenza di 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 precedente:

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 da bias sinistro o bias destro.

Nell’esempio precedente:

Il nodo ha meno di chiavi max
1 viene inserito accanto a 3, ma la regola dell’ordine crescente viene violata
Per risolvere questo problema, le chiavi sono ordinate

Allo stesso modo, 13 e 2 possono essere inseriti facilmente nel nodo in quanto soddisfano la regola delle chiavi meno di max per i nodi.

Nell’esempio precedente:

Il nodo ha chiavi uguali a chiavi max.
La chiave viene inserita nel nodo di destinazione, ma viola la regola delle chiavi max.
Il nodo di destinazione è diviso e la chiave centrale per distorsione sinistra è ora il padre 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 inserito facilmente nell’albero B.

Operazione Elimina

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

Si applica il seguente algoritmo:

Eseguire l’operazione di ricerca e trovare 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ù delle chiavi min.
L’eliminazione di questo 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 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 più di un numero minimo di chiavi
Cerca chiave
Unisci con gli elementi di pari livello 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 in cui il predecessore in ordine, verrà selezionata la chiave massima dal suo sottoalbero sinistro
In caso di successore in ordine, verrà selezionata la chiave minima dal suo sottoalbero destro
Se il predecessore in ordine della chiave di destinazione ha più dei tasti min, solo allora può sostituire il tasto di destinazione con il massimo del predecessore in ordine
Se il predecessore in ordine della chiave di destinazione non dispone di più di chiavi min, cercare la chiave minima del successore in ordine.
Se il predecessore e il successore in ordine della chiave di destinazione hanno entrambi chiavi inferiori a min, unire il predecessore e il successore.

Se la chiave di destinazione si trova in un nodo radice

Sostituisci con l’elemento massimo del sottoalbero predecessore in ordine
Se, dopo l’eliminazione, la destinazione ha meno di chiavi minime, il nodo di destinazione prenderà in prestito il valore massimo dal fratello tramite il padre del fratello.
Il valore massimo del padre verrà preso da una destinazione, ma con i nodi del valore massimo del fratello.

Ora, comprendiamo l’operazione di eliminazione con un esempio.

Il diagramma precedente mostra diversi casi di operazione di eliminazione in un B-Tree. Questo B-Tree è di ordine 5, il che significa che il numero minimo di nodi figlio che ogni nodo può avere è 3 e il numero massimo di nodi figlio che ogni nodo può avere è 5. Mentre il numero minimo e massimo di chiavi che ogni nodo può avere sono rispettivamente 2 e 4.

Nell’esempio precedente:

Il nodo di destinazione ha la chiave di destinazione da eliminare
Il nodo di destinazione ha chiavi più delle chiavi minime
Basta eliminare la chiave

Nell’esempio precedente:

Il nodo di destinazione ha chiavi uguali a chiavi minime, quindi non può eliminarlo direttamente in quanto 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, predecessore in ordine (fratello sinistro) perché non ha alcun successore in ordine (fratello destro)
Il valore massimo del predecessore dell’inorder verrà trasferito al padre e il padre trasferirà il valore massimo al nodo di destinazione (vedere il diagramma seguente)

Nell’esempio seguente viene illustrato come eliminare una chiave che richiede 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 predecessore in ordine (fratello sinistro) ha chiavi uguali alle chiavi minime.
Il valore minimo del successore in ordine verrà trasferito al padre e il padre trasferirà il valore massimo al nodo di destinazione.

Nell’esempio seguente, il nodo di destinazione non dispone di alcun elemento di pari livello in grado di fornire la chiave al nodo di destinazione. Pertanto, è necessaria la fusione.

Vedere la procedura di eliminazione di tale chiave:

Unire il nodo di destinazione con uno qualsiasi dei suoi fratelli immediati insieme alla chiave padre
La chiave del nodo padre viene selezionata che gli elementi di associazione tra i due nodi di unione
Eliminare la chiave di destinazione dal nodo unito

Elimina operazione pseudo codice

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        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 di dati autobilanciata per una migliore ricerca, inserimento ed eliminazione dei dati dal disco.
L’albero B è regolato dal grado specificato
Le chiavi e i nodi dell’albero B sono disposti in ordine crescente.
L’operazione di ricerca di B Tree è la più semplice, che parte sempre dalla root e inizia a verificare se la chiave di destinazione è maggiore o minore del valore del nodo.
L’operazione di inserimento di B Tree è piuttosto dettagliata, che prima trova una posizione di inserimento appropriata per la chiave di destinazione, la inserisce, valuta la validità di B Tree rispetto a diversi casi e quindi ristruttura di conseguenza i nodi B Tree.
L’operazione di eliminazione di B Tree cerca innanzitutto la chiave di destinazione da eliminare, la elimina, valuta la validità in base a diversi casi come chiavi minime e massime del nodo di destinazione, fratelli e padre.

fonte: https://www.guru99.com/