Cos'è un albero B +?
Un albero B + viene utilizzato principalmente per implementare l'indicizzazione dinamica su più livelli. Rispetto a B-Tree, B + Tree memorizza i puntatori di dati solo nei nodi foglia dell'albero, il che rende il processo di ricerca più accurato e veloce.
In questo tutorial di B + Tree imparerai:
- Cos'è un albero B +?
- Regole per B + Tree
- Perché usare B + Tree
- Albero B + contro Albero B.
- Operazione di ricerca
- Inserisci operazione
- Elimina operazione
Regole per B + Tree
Ecco le regole essenziali per B + Tree.
- Le foglie vengono utilizzate per memorizzare i 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 appena al suo lato sinistro.
- Se il valore di una chiave di destinazione è maggiore o uguale al nodo interno, viene seguito il punto appena al suo lato destro.
- La radice ha un minimo di due figli.
Perché usare B + Tree
Ecco i motivi per utilizzare B + Tree:
- Le chiavi vengono utilizzate principalmente per aiutare la ricerca dirigendosi verso la foglia appropriata.
- 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 sulla pagina di memoria perché non hanno i dati associati ai nodi interni. Pertanto, accederà rapidamente ai dati dell'albero che si trovano sul nodo foglia.
- Una scansione completa completa di tutti gli elementi è un albero che richiede un solo passaggio lineare perché tutti i nodi foglia di un albero B + sono collegati tra loro.
Albero B + contro Albero B.
Ecco le principali differenze tra B + Tree e B Tree
| B + Albero | B Tree |
| 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ù precisa e veloce. | La ricerca è lenta a causa dei dati memorizzati su Leaf e sui nodi interni. |
| L'eliminazione non è difficile in quanto un elemento viene rimosso solo da un nodo foglia. | L'eliminazione 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. |
Operazione di ricerca
In B + Tree, una ricerca è una delle procedure più semplici da eseguire e ottenere risultati rapidi e precisi da essa.
È applicabile il seguente algoritmo di ricerca:
- Per trovare il record richiesto, è necessario eseguire la ricerca binaria sui record disponibili nella struttura ad albero.
- In caso di corrispondenza esatta con la chiave di ricerca, il record corrispondente viene restituito all'utente.
- Nel caso in cui la chiave esatta non venga individuata dalla ricerca nel nodo padre, corrente o foglia, all'utente viene visualizzato un "messaggio non trovato".
- Il processo di ricerca può essere rieseguito per ottenere risultati migliori e più accurati.
Algoritmo delle operazioni di ricerca
1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."
Uscita :
Il record abbinato impostato sulla chiave esatta viene visualizzato all'utente; in caso contrario, all'utente viene mostrato un tentativo fallito.
Inserisci operazione
Il seguente algoritmo è applicabile per l'operazione di inserimento:
- Il 50 percento degli elementi nei nodi viene spostato in 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 padre in più posizioni nel caso in cui venga completamente utilizzato.
- Ora, per risultati migliori, la chiave centrale è associata al nodo di primo livello di quella Foglia.
- Fino a quando il nodo di primo livello non viene trovato, continuare a ripetere il processo spiegato nei passaggi precedenti.
Inserisci algoritmo di operazione
1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. 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 treeb. 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 sopra è spiegato nei passaggi seguenti:
- In primo luogo, abbiamo 3 nodi ei primi 3 elementi, che sono 1, 4 e 6, vengono aggiunti in posizioni appropriate nei nodi.
- Il valore successivo nella serie di dati è 12 che deve essere inserito nella struttura ad albero.
- Per ottenere ciò, dividi il nodo, aggiungi 6 come elemento puntatore.
- A questo punto, viene creata una gerarchia a destra di un albero e i valori dei dati rimanenti vengono regolati di conseguenza tenendo presente le regole applicabili di uguale o maggiore di valori rispetto ai nodi valore-chiave a destra.
Elimina operazione
La complessità della procedura di cancellazione nell'albero B + supera quella delle funzionalità di inserimento e ricerca.
Il seguente algoritmo è applicabile durante l'eliminazione di un elemento dall'albero B +:
- In primo luogo, dobbiamo individuare una voce foglia nell'albero che contiene la chiave e il puntatore. , elimina la voce foglia dall'albero se la foglia soddisfa le condizioni esatte per l'eliminazione del record.
- Nel caso in cui il nodo foglia soddisfi solo il fattore soddisfacente di essere mezzo pieno, l'operazione è completata; in caso contrario, il nodo Foglia ha voci minime e non può essere eliminato.
- Gli altri nodi collegati a destra e a sinistra possono liberare qualsiasi voce, quindi spostarli nella Foglia. Se questi criteri non sono soddisfatti, devono combinare il nodo foglia e il relativo nodo collegato nella gerarchia ad albero.
- Dopo l'unione del nodo foglia con i suoi vicini a destra oa sinistra, le voci di valori nel nodo foglia o nel vicino collegato che puntano al nodo di primo livello vengono cancellate.
L'esempio sopra illustra la procedura per rimuovere un elemento dall'albero B + di un ordine specifico.
- In primo luogo, le posizioni esatte dell'elemento da eliminare vengono identificate nella struttura ad albero.
- Qui l'elemento da eliminare può essere identificato con precisione solo a livello foglia e non al posizionamento dell'indice. Quindi, l'elemento può essere cancellato senza influenzare le regole di cancellazione, che è il valore della chiave del minimo indispensabile.
- 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 livello di nodo 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 collocheremo come indice. Quindi, essendo 42 l'unico valore presente, diventerà l'indice.
Elimina algoritmo di operazione
1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) 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 nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node
Uscita :
La chiave "K" viene eliminata e le chiavi vengono prese in prestito dai fratelli per regolare i valori in n e nei suoi nodi padre, se necessario.
Sommario:
- B + Tree è una struttura dati autobilanciata per eseguire procedure di ricerca, inserimento ed eliminazione accurate e veloci 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 un aumento / diminuzione del numero di record memorizzati.
- La memorizzazione dei dati sui nodi foglia e la successiva ramificazione dei nodi interni riduce evidentemente l'altezza dell'albero, il che riduce le operazioni di input e output del disco, consumando in definitiva molto meno spazio sui dispositivi di archiviazione.