B+ TREE: Cerca, Inserisci ed Elimina Operazioni

Cos'è un albero B+?

A B+ Albero Viene utilizzato principalmente per implementare l'indicizzazione dinamica su più livelli. Rispetto a un albero B, l'albero B+ memorizza i puntatori ai dati solo nei nodi foglia dell'albero, il che rende il processo di ricerca più preciso e veloce.

Regole per B+ Tree

Ecco le regole essenziali per un albero B+.

• Le foglie vengono utilizzate per memorizzare record di dati.
• I record vengono memorizzati nei nodi interni dell'albero.
• Se il valore della chiave di destinazione è inferiore al nodo interno, viene seguito il puntatore immediatamente alla sua sinistra.
• Se il valore della chiave di destinazione è maggiore o uguale al nodo interno, viene seguito il puntatore immediatamente alla sua destra.
• La radice ha un minimo di due figli.

Perché utilizzare B+ Tree

Ecco i motivi per utilizzare un albero B+:

• Le chiavi di identificazione servono principalmente ad agevolare la ricerca, indirizzando alla pagina corretta.
• Un albero B+ utilizza un "fattore di riempimento" per gestire l'aumento e la diminuzione all'interno dell'albero.
• Negli alberi B+ numerose chiavi possono essere facilmente posizionate nella pagina di memoria perché non hanno i dati associati ai nodi interni. Pertanto, accederà rapidamente ai dati dell'albero che si trova sul nodo foglia.
• Una scansione completa di tutti gli elementi richiede un solo passaggio lineare perché tutti i nodi foglia di un albero B+ sono collegati tra loro.

B+ Albero contro B Albero

Ecco le principali differenze tra un albero B+ e un albero B.

Cerca Operaproduzione

In un albero B+, la ricerca è una delle procedure più semplici da eseguire e fornisce risultati rapidi e precisi.

È applicabile il seguente algoritmo di ricerca:

• Per trovare il record richiesto, è necessario eseguire il file ricerca binaria sui record disponibili nell'albero.
• In caso di corrispondenza esatta con la chiave di ricerca, all'utente viene restituito il record corrispondente.
• Nel caso in cui la chiave esatta non venga individuata dalla ricerca nel nodo principale, corrente o foglia, all'utente viene visualizzato un messaggio di "non trovato".
• Il processo di ricerca può essere eseguito nuovamente per ottenere risultati migliori e più accurati.

Cerca OperaAlgoritmo di zione

1. Call the binary search method on the records in the B+ Tree.
2. If the search parameters match the exact key
       The accurate result is returned and displayed to the user
   Else, if the node being searched is the current and the exact key is not found by the algorithm
       Display the statement "Recordset cannot be found."

Produzione: All'utente viene mostrato il set di record corrispondente alla chiave esatta; in caso contrario, viene mostrato un tentativo non riuscito.

inserire Operaproduzione

Per l'operazione di inserimento è applicabile il seguente algoritmo:

• Il 50% degli elementi nei nodi viene spostato su una nuova foglia per l'archiviazione.
• Il genitore della nuova foglia è collegato in modo preciso con il valore minimo della chiave e una nuova posizione nell'albero.
• Dividi il nodo principale in più posizioni nel caso in cui venga completamente utilizzato.
• Ora, per ottenere risultati migliori, la chiave centrale è associata al nodo di livello superiore di quella foglia.
• Fino a quando il nodo di livello superiore non viene trovato, continua a ripetere il processo spiegato nei passaggi precedenti.

inserire OperaAlgoritmo di zione

1. If inserting at least 1 entry into the leaf container does not make it full, then add the record.
2. Else, divide the node into more locations to fit more records.
   a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the tree.
   b. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.
   c. Divide the top-level node if it gets full of keys and addresses.
      i. Similarly, insert a key in the center of the top-level node in the hierarchy of the Tree.
   d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore.
3. Build a new top-level root node of 1 key and 2 indicators.

Produzione: L'algoritmo determinerà l'elemento e lo inserirà con successo nel nodo foglia richiesto.

L'esempio di esempio B+ Tree riportato sopra è spiegato nei passaggi seguenti:

• Innanzitutto, abbiamo 3 nodi e i primi 3 elementi, ovvero 1, 4 e 6, vengono aggiunti nelle posizioni appropriate all'interno dei nodi.
• Il valore successivo nella serie di dati è 12, che deve essere inserito nell'albero.
• Per ottenere questo risultato, dividi il nodo e aggiungi 6 come elemento puntatore.
• Ora viene creata una gerarchia destra di un albero e i valori dei dati rimanenti vengono regolati di conseguenza da keeping tenendo presente le regole applicabili dei valori uguali o maggiori rispetto ai nodi chiave-valore sulla destra.

Elimina Operaproduzione

La complessità della procedura di eliminazione nell'albero B+ supera quella delle funzionalità di inserimento e ricerca.

Il seguente algoritmo è applicabile durante l'eliminazione di un elemento dall'albero B+:

• Innanzitutto, dobbiamo individuare una voce foglia nell'albero che contenga la chiave e il puntatore, quindi eliminare la voce foglia dall'albero se la foglia soddisfa esattamente le condizioni per l'eliminazione del record.
• Nel caso in cui il nodo foglia soddisfi solo il criterio di riempimento a metà, l'operazione è completata; altrimenti, il nodo foglia ha il numero minimo di voci e non può essere eliminato.
• Gli altri nodi collegati a destra e a sinistra possono liberare qualsiasi voce e quindi spostarla alla foglia. Se questi criteri non vengono soddisfatti, allora devono combinare il nodo foglia e il suo nodo collegato nella gerarchia dell'albero.
• Quando un nodo foglia viene unito ai suoi vicini a destra o a sinistra, le voci di valore presenti nel nodo foglia o nel vicino collegato che punta al nodo di livello superiore vengono eliminate.

L'esempio sopra riportato illustra la procedura per rimuovere un elemento da un albero B+ di un ordine specifico.

• Innanzitutto nell'Albero vengono identificate le posizioni esatte dell'elemento da eliminare.
• In questo caso, l'elemento da eliminare può essere identificato con precisione solo a livello di foglia e non a livello di indice. Pertanto, l'elemento può essere eliminato senza compromettere le regole di eliminazione, che corrispondono al valore della chiave minima indispensabile.

• Nell'esempio sopra, dobbiamo eliminare 31 dall'albero.
• Dobbiamo individuare le occorrenze del valore 31 nell'Indice e nella Foglia.
• Possiamo notare che il valore 31 è disponibile sia a livello di nodo Indice che a livello di nodo Foglia. Pertanto, lo eliminiamo da entrambe le istanze.
• Ma dobbiamo riempire l'indice che punta a 42. Ora esamineremo il figlio destro inferiore a 25, prenderemo il valore minimo e lo imposteremo come indice. Quindi, essendo 42 l'unico valore presente, diventerà l'indice.

Elimina OperaAlgoritmo di zione

1) Start at the root and go up to the leaf node containing the key K.
2) Find the node n on the path from the root to the leaf node containing K.
   A. If n is root, remove K
      a. if root has more than one key, done
      b. if root has only K
         i)  if any of its child nodes can lend a node
             Borrow key from the child and adjust child links
         ii) Otherwise merge the children nodes. It will be a new root
      c. If n is an internal node, remove K
         i)  If n has at least ceil(m/2) keys, done!
         ii) If n has less than ceil(m/2) keys,
             If a sibling can lend a key,
                Borrow key from the sibling and adjust keys in n and the parent node
                Adjust child links
             Else
                Merge n with its sibling
                Adjust child links
      d. If n is a leaf node, remove K
         i)  If n has at least ceil(M/2) elements, done!
             In case the smallest key is deleted, push up the next key
         ii) If n has less than ceil(m/2) elements
             If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
             Else
                Merge n and its sibling
                Adjust keys in the parent node

Produzione: La chiave “K” viene eliminata e, se necessario, vengono prese in prestito le chiavi dai nodi fratelli per regolare i valori in n e nei suoi nodi genitori.

DOMANDE FREQUENTI