B ALBERO nella struttura dati: Cerca, Inserisci, Elimina Operazione Esempio

Regole per B-Tree

Ecco le regole importanti per creare B_Tree

• Tutte le foglie verranno create allo stesso livello.
• Il B-Tree è determinato da un numero di grado, chiamato anche “ordine” (specificato da un attore esterno, come un programmatore), denominato

  m

  in poi. Il valore di

  m

  dipende 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 vengono ordinati in ordine crescente da sinistra a destra.
• Il numero massimo di nodi figli che un nodo radice e i suoi nodi figli possono contenere vengono calcolati con questa formula:

  m – 1

  Per esempio:

  m = 4
  max keys: 4 – 1 = 3
  

• Ogni nodo, eccetto root, deve contenere chiavi minime di

  [m/2]-1

  Per esempio:

  m = 4
  min keys: 4/2-1 = 1
  

• Il numero massimo di nodi figli che un nodo può avere è uguale al suo grado, ovvero

  m

• Il numero minimo di figli che un nodo può avere è la metà dell'ordine, ovvero m/2 (viene preso il valore massimo).
• Tutte le chiavi in ​​un nodo sono ordinate in ordine crescente.

Perché utilizzare B-Tree

Ecco i motivi per utilizzare B-Tree

• Riduce il numero di letture effettuate sul disco
• I B Tree possono essere facilmente ottimizzati per adattarne la dimensione (ovvero il numero di nodi figli) in base alla dimensione del disco
• Si tratta di una tecnica appositamente progettata per gestire una grande quantità di dati.
• È un algoritmo utile per database e file system.
• Una buona scelta da optare 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 sul 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 vengono create delle tabelle indice che salvano il riferimento 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.
• È possibile progettare un indice multilivello utilizzando B Tree per mantenere i dati ordinati in modo autobilanciante.

Cerca Operaproduzione

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

Viene applicato il seguente algoritmo:

• Lascia che la chiave (il valore) venga cercata con "k".
• Inizia la ricerca dalla radice e procedi ricorsivamente verso il basso.
• Se k è inferiore al valore della radice, cerca nel sottoalbero di sinistra, se k è maggiore del valore della radice, cerca nel sottoalbero di destra.
• Se il nodo ha il k trovato, restituisci semplicemente il nodo.
• Se la k non si trova nel nodo, attraversa fino al bambino con una chiave maggiore.
• Se k non si trova nell'albero, restituiamo NULL.

inserire Operaproduzione

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

Si applica il seguente algoritmo:

• Esegui l'operazione di ricerca e trova il luogo di inserimento appropriato.
• Inserisci la nuova chiave nella posizione corretta, ma se il nodo ha già un numero massimo di chiavi:
• Il nodo, insieme alla chiave appena inserita, si dividerà dall'elemento centrale.
• L'elemento centrale diventerà il genitore per gli altri due nodi figli.
• I nodi devono riorganizzare le chiavi in ​​ordine crescente.

Consiglio

Quanto segue non è vero per quanto riguarda l'algoritmo di inserimento: Poiché il nodo è pieno, verrà diviso e quindi verrà inserito un nuovo valore

Nell'esempio sopra:

• Cerca la chiave nella posizione appropriata nel nodo
• Inserisci la chiave nel nodo di destinazione e controlla le regole
• Dopo l'inserimento, il nodo ha più del numero minimo di chiavi pari a 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 è così. Ciò significa che il B Tree non sta violando alcuna regola e l'inserimento è completo.

Nell'esempio sopra:

• Il nodo ha raggiunto il numero massimo di chiavi
• Il nodo verrà diviso e la chiave centrale diventerà il nodo radice degli altri due nodi.
• In caso di numero pari di chiavi, il nodo centrale verrà selezionato tramite bias sinistro o bias destro.

Nell'esempio sopra:

• Il nodo ha meno di max chiavi
• Viene inserito 1 accanto a 3, ma la regola dell'ordine crescente è 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 delle chiavi inferiori al massimo per i nodi.

Nell'esempio sopra:

• Il nodo ha chiavi uguali a max keys.
• La chiave viene inserita nel nodo di destinazione, ma viola la regola delle chiavi massime.
• Il nodo di destinazione è diviso e la chiave centrale per polarizzazione a sinistra è ora il genitore dei nuovi nodi figli.
• I nuovi nodi sono disposti in ordine crescente.

Allo stesso modo, in base alle regole e ai casi sopra indicati, il resto dei valori può essere inserito facilmente nel B Tree.

Elimina Operaproduzione

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

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

Se la chiave di destinazione si trova in un nodo interno

• Scegli tra predecessore in ordine o successore in ordine
• Nel caso del 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ù 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 minime, cerca la chiave minima del successore in ordine.
• Se il predecessore e il successore in ordine della chiave di destinazione hanno entrambi meno di chiavi minime, unire il predecessore e il successore.

Se la chiave di destinazione si trova in un nodo radice

• Sostituisci con l'elemento massimo del sottoalbero precedente in ordine
• Se, dopo l'eliminazione, il target ha meno di chiavi minime, il nodo target prenderà in prestito il valore massimo dal fratello tramite il genitore del fratello.
• Il valore massimo del genitore verrà preso da un target, ma con i nodi del valore massimo del fratello.

Ora comprendiamo l'operazione di eliminazione con un esempio.

Il diagramma sopra 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 figli che ogni nodo può avere è 3, e il numero massimo di nodi figli che ogni nodo può avere è 5. Mentre il numero minimo e massimo di chiavi 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 chiavi superiori a quelle minime
• Basta eliminare la chiave

Nell'esempio sopra:

• Il nodo di destinazione ha chiavi pari alle chiavi minime, quindi non è possibile eliminarlo direttamente poiché violerebbe 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 in ordine verrà trasferito al genitore e il genitore trasferirà il valore massimo al nodo di destinazione (vedere il diagramma seguente)

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

• 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 possa fornire la propria 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 principale
• Viene selezionata la chiave del nodo genitore che si trova tra i fratelli tra i due nodi di fusione
• Elimina la chiave di destinazione dal nodo unito

Elimina Operazione pseudocodice

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 dati autobilanciata per una migliore ricerca, inserimento e cancellazione dei dati dal disco.
• B L'albero è regolato dal grado specificato
• B Le chiavi e i nodi dell'albero sono disposti in ordine crescente.
• L'operazione di ricerca di B Tree è quella più semplice, che parte sempre dalla radice e inizia controllando se la chiave di destinazione è maggiore o minore del valore del nodo.
• Piuttosto dettagliata è l'operazione di inserimento del B Tree, che prima trova una posizione di inserimento appropriata per la chiave di destinazione, la inserisce, valuta la validità del B Tree rispetto a diversi casi, e poi ristruttura i nodi del B Tree di conseguenza.
• 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 minima e massima del nodo di destinazione, fratelli e genitore.