Albero B nella struttura dati: ricerca, inserimento, eliminazione

Cos'è un albero B?

B Albero È una struttura dati autobilanciante basata su un insieme specifico di regole per la ricerca, l'inserimento e la cancellazione 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 albero B è un tipo speciale di albero in una struttura dati. Questo metodo fu introdotto per la prima volta nel 1972 da McCreight e Bayer, che lo chiamarono Albero di ricerca m-way bilanciato in altezza. Consente di mantenere i dati ordinati e permette di eseguire diverse operazioni come inserimento, ricerca ed eliminazione in tempi ridotti.

Regole per B-Tree

Ecco le regole importanti per la creazione di un albero B:

• Tutte le foglie verranno create allo stesso livello.
• Un albero B è determinato da un numero di grado, che è anche chiamato “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.
• 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 chiavi che un nodo radice, così come i suoi nodi figli, possono contenere viene calcolato con la seguente formula: m − 1. Per esempio:

  m = 4
  max keys: 4 − 1 = 3

• Ogni nodo, eccetto la radice, deve contenere un numero minimo di chiavi 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 un albero B:

• Riduce il numero di operazioni di lettura effettuate sul disco.
• Gli alberi B possono essere facilmente ottimizzati per adattare le loro dimensioni (ovvero il numero di nodi figli) in base alle dimensioni del disco.
• Si tratta di una tecnica appositamente progettata per gestire una grande quantità di dati.
• È un algoritmo utile per database e file system.
• Un'ottima scelta quando si tratta di leggere e scrivere grandi quantità di dati.

Storia di B-Tree

• I dati vengono memorizzati sul disco in blocchi. Questi dati, quando vengono trasferiti nella memoria principale (o RAM), costituiscono una struttura dati.
• Nel caso di grandi quantità di dati, la ricerca di un singolo record sul disco richiede la lettura dell'intero disco; ciò aumenta i tempi di elaborazione 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 indice che salvano il riferimento ai 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 un albero B per la chiaveping I dati sono stati ordinati in modo autobilanciante.

Cerca Operaproduzione

L'operazione di ricerca è l'operazione più semplice su un albero B. Viene applicato il seguente algoritmo:

• Sia "k" la chiave (il valore) da cercare.
• Inizia la ricerca dalla radice e procedi ricorsivamente verso il basso.
• Se k è minore del valore della radice, cerca nel sottoalbero sinistro; se k è maggiore del valore della radice, cerca nel sottoalbero destro.
• 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é un albero B è un albero autobilanciante, non è possibile inserire forzatamente 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.

Nell'esempio sopra:

• Cerca la posizione appropriata nel nodo per la chiave.
• Inserisci la chiave nel nodo di destinazione e verifica le regole.
• Dopo l'inserimento, il nodo ha un numero di chiavi maggiore o uguale al numero minimo, ovvero 1? In questo caso, sì. Controlla la regola successiva.
• Dopo l'inserimento, il nodo ha più del numero massimo di chiavi, ovvero 3? In questo caso, no. 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.
• Nel caso di un numero pari di chiavi, il nodo centrale verrà selezionato in base alla preferenza a sinistra o a destra.

Nell'esempio sopra:

• Il nodo ha meno del numero massimo di chiavi.
• Il numero 1 viene inserito accanto al 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 "meno di chiavi massime" 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 del numero massimo di chiavi.
• 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 prevede 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.
• Vengono applicate tre condizioni 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ù di chiavi minime. Eliminando questo non violerà la proprietà dell'albero B.
• Target si trova nel nodo foglia e ha un numero minimo di nodi chiave. Eliminandolo si violerebbe la proprietà dell'albero B.
• Il nodo di destinazione può prendere in prestito una chiave dal nodo immediatamente a sinistra o dal nodo immediatamente a destra (fratello).
• Il fratello dirà sì se ha più del numero minimo di chiavi.
• La chiave verrà presa in prestito dal nodo padre, il valore massimo verrà trasferito al padre, il valore massimo del nodo padre verrà trasferito al nodo di destinazione e il valore di destinazione verrà rimosso.
• Target è nel nodo foglia, ma nessun fratello ha più del numero minimo di chiavi: cerca la chiave, unisci con i fratelli e il minimo dei nodi padre, il numero totale di chiavi sarà ora maggiore del minimo e la chiave di destinazione verrà sostituita con il minimo di un nodo padre.

Se la chiave di destinazione si trova in un nodo interno

• Scegliere un predecessore in ordine o un successore in ordine.
• Nel caso di un predecessore in ordine, verrà selezionata la chiave massima dal suo sottoalbero sinistro.
• Nel caso di un successore in ordine, verrà selezionata la chiave minima dal suo sottoalbero destro.
• Se il predecessore in ordine della chiave di destinazione ha più chiavi del numero minimo, solo allora può sostituire la chiave di destinazione con il numero massimo del predecessore in ordine.
• Se il predecessore in ordine della chiave di destinazione non ha più di min chiavi, 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

• Sostituire con l'elemento massimo del sottoalbero predecessore in ordine.
• Se, dopo la cancellazione, il nodo di destinazione ha meno di min chiavi, allora il nodo di destinazione prenderà in prestito il valore massimo dal suo fratello tramite il genitore di quest'ultimo.
• Il valore massimo del genitore verrà preso dal target, ma con i nodi del valore massimo del fratello.

Ora comprendiamo l'operazione di eliminazione con un esempio.

Il diagramma sopra riportato mostra diversi casi dell'operazione di cancellazione in un albero B. Questo albero B è di ordine 5, il che significa che il numero minimo di nodi figli che un nodo può avere è 3, e il numero massimo di nodi figli che un nodo può avere è 5. Il numero minimo e massimo di chiavi che un nodo può avere è rispettivamente 2 e 4.

Nell'esempio sopra:

• Il nodo di destinazione possiede la chiave di destinazione da eliminare.
• Il nodo di destinazione ha più chiavi del numero minimo di chiavi.
• È sufficiente eliminare la chiave.

Nell'esempio sopra:

• Il nodo di destinazione ha chiavi pari al numero minimo di chiavi, quindi non possiamo eliminarlo direttamente poiché ciò violerebbe le condizioni.

Ora, il diagramma seguente spiega come eliminare questa chiave:

• Il nodo di destinazione prenderà in prestito una chiave da un fratello immediato, in questo caso il predecessore in ordine (fratello sinistro), poiché 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 sottostante).

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 da un 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 nodo fratello che possa cedergli la propria chiave. Pertanto, è necessaria l'unione. Consultare la procedura per eliminare tale chiave:

• Unisci il nodo di destinazione con uno qualsiasi dei suoi fratelli diretti, insieme alla chiave del nodo padre.
• Viene selezionata la chiave del nodo padre che si trova tra i due nodi da unire.
• Elimina la chiave di destinazione dal nodo unito.

Elimina Operazione Pseudo Code

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
    }
}

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

DOMANDE FREQUENTI