B+ TREE: Cerca, inserisci ed elimina Operazioni Esempio

Cos'è un albero B+?

A B+ Albero viene utilizzato principalmente per implementare l'indicizzazione dinamica su più livelli. Rispetto al B-Tree, il B+ Tree memorizza i puntatori dei dati solo nei nodi foglia dell'albero, il che rende la ricerca più accurata e veloce.

Regole per B+ Tree

Ecco le regole essenziali per B+ Tree.

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

Perché utilizzare B+ Tree

Ecco i motivi per utilizzare B+ Tree:

• Le chiavi vengono utilizzate principalmente per facilitare la ricerca indirizzando alla foglia corretta.
• B+ Tree utilizza un “fattore di riempimento” per gestire l'aumento e la diminuzione di un 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 completa di tutti gli elementi è un albero che necessita di 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 B+ Tree e B Tree

B+ Albero	B Albero
Le chiavi di ricerca possono essere ripetute.	Le chiavi di ricerca non possono essere ridondanti.
I dati vengono salvati solo sui nodi foglia.	Sia i nodi foglia che i nodi interni possono archiviare dati
I dati memorizzati sul nodo foglia rendono la ricerca più accurata e veloce.	La ricerca è lenta a causa dei dati memorizzati su Leaf e sui nodi interni.
La cancellazione non è difficile poiché un elemento viene rimosso solo da un nodo foglia.	La cancellazione degli elementi è un processo complicato e dispendioso in termini di tempo.
I nodi foglia collegati rendono la ricerca efficiente e veloce.	Non è possibile collegare i nodi foglia.

Cerca Operaproduzione

In B+ Tree, una ricerca è una delle procedure più semplici da eseguire e da essa si ottengono risultati rapidi e accurati.

È 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."

Uscita:

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 accuratamente con il valore chiave minimo 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.	Even 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.  

Uscita:

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, che sono 1, 4 e 6, vengono aggiunti nelle posizioni appropriate nei nodi.
• Il valore successivo nella serie di dati è 12 e deve essere inserito nell'albero.
• Per ottenere ciò, dividi il nodo, aggiungi 6 come elemento puntatore.
• Ora viene creata una gerarchia di destra di un albero e i valori dei dati rimanenti vengono adeguati di conseguenza tenendo presenti le regole applicabili dei valori uguali o maggiori rispetto ai nodi dei valori-chiave 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+:

• Per prima cosa dobbiamo individuare una voce foglia nell'albero che contiene il tasto e il puntatore. , elimina la voce foglia dall'albero se la foglia soddisfa le esatte condizioni di eliminazione del record.
• Se il nodo foglia soddisfa solo il fattore soddisfacente di essere mezzo pieno, l'operazione è completata; in caso contrario, il nodo foglia ha un numero minimo di voci e non può essere eliminato.
• Gli altri nodi collegati a destra e a sinistra possono liberare qualsiasi voce e spostarla sulla Foglia. Se questi criteri non sono soddisfatti, allora dovrebbero combinare il nodo foglia e il suo nodo collegato nella gerarchia dell'albero.
• Dopo l'unione del nodo foglia con i suoi vicini a destra o a sinistra, le voci dei valori nel nodo foglia o nel vicino collegato che puntano al nodo di livello superiore vengono cancellate.

L'esempio sopra illustra la procedura per rimuovere un elemento dal B+ Tree di un ordine specifico.

• Innanzitutto nell'Albero vengono identificate le posizioni esatte dell'elemento da eliminare.
• Qui l'elemento da eliminare può essere identificato con precisione solo a livello della foglia e non nella posizione dell'indice. Pertanto, l'elemento può essere eliminato senza influenzare le regole di eliminazione, ovvero il valore della chiave minima.

• Nell'esempio sopra, dobbiamo eliminare 31 dall'albero.
• Dobbiamo individuare le istanze di 31 in Index e Leaf.
• Possiamo vedere che 31 è disponibile sia a livello di nodo Indice che a quello Foglia. Quindi, lo eliminiamo da entrambe le istanze.
• Ma dobbiamo riempire l'indice che punta a 42. Ora esamineremo il bambino giusto sotto i 25 anni, prenderemo il valore minimo e lo inseriremo 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 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

Uscita:

La chiave "K" viene eliminata e le chiavi vengono prese in prestito dai fratelli per modificare i valori in n e nei suoi nodi principali, se necessario.

Sommario

• B+ Tree è un sistema autobilanciante struttura dati per eseguire procedure di ricerca, inserimento ed eliminazione accurate e rapide sui dati
• Possiamo facilmente recuperare dati completi o dati parziali perché passare attraverso la struttura ad albero collegata lo rende efficiente.
• La struttura ad albero B+ cresce e si restringe con l'aumento/diminuzione del numero di record archiviati.
• L'archiviazione dei dati sui nodi foglia e la successiva ramificazione dei nodi interni riduce evidentemente l'altezza dell'albero, riducendo le operazioni di input e output del disco, consumando in definitiva molto meno spazio sui dispositivi di archiviazione.