Wat is een B + Tree?
Een B + Tree wordt voornamelijk gebruikt voor het implementeren van dynamische indexering op meerdere niveaus. In vergelijking met B-Tree slaat de B + Tree de gegevenswijzers alleen op de bladknooppunten van de Tree op, waardoor het zoekproces nauwkeuriger en sneller verloopt.
In deze B + Tree-tutorial leer je:
- Wat is een B + Tree?
- Regels voor B + Tree
- Waarom B + Tree gebruiken
- B + Tree versus B Tree
- Zoekoperatie
- Plaats operatie
- Bewerking verwijderen
Regels voor B + Tree
Hier zijn essentiële regels voor B + Tree.
- Bladeren worden gebruikt om gegevensrecords op te slaan.
- Het is opgeslagen in de interne knooppunten van de boom.
- Als een doelsleutelwaarde kleiner is dan het interne knooppunt, wordt het punt net aan de linkerkant gevolgd.
- Als een doelsleutelwaarde groter is dan of gelijk is aan het interne knooppunt, wordt het punt net aan de rechterkant gevolgd.
- De wortel heeft minimaal twee kinderen.
Waarom B + Tree gebruiken
Hier zijn redenen om B + Tree te gebruiken:
- Sleutel wordt voornamelijk gebruikt om het zoeken te vergemakkelijken door naar het juiste blad te verwijzen.
- B + Tree gebruikt een "vulfactor" om de toename en afname van een boom te beheren.
- In B + -bomen kunnen gemakkelijk talrijke sleutels op de pagina van het geheugen worden geplaatst omdat ze niet de gegevens hebben die zijn gekoppeld aan de interne knooppunten. Daarom zal het snel toegang krijgen tot boomgegevens die zich op het bladknooppunt bevinden.
- Een uitgebreide volledige scan van alle elementen is een boom die slechts één lineaire passage nodig heeft, omdat alle bladknooppunten van een B + -boom met elkaar zijn verbonden.
B + Tree versus B Tree
Hier zijn de belangrijkste verschillen tussen B + Tree en B Tree
| B + Boom | B Boom |
| Zoeksleutels kunnen worden herhaald. | Zoeksleutels kunnen niet overbodig zijn. |
| Gegevens worden alleen opgeslagen op de bladknooppunten. | Zowel bladknooppunten als interne knooppunten kunnen gegevens opslaan |
| Gegevens die op de leaf-node zijn opgeslagen, maken de zoekopdracht nauwkeuriger en sneller. | Het zoeken is traag vanwege de gegevens die zijn opgeslagen op Leaf en interne knooppunten. |
| Verwijderen is niet moeilijk omdat een element alleen uit een bladknooppunt wordt verwijderd. | Het verwijderen van elementen is een ingewikkeld en tijdrovend proces. |
| Gekoppelde bladknooppunten maken het zoeken efficiënt en snel. | U kunt geen bladknooppunten koppelen. |
Zoekoperatie
In B + Tree is een zoekopdracht een van de gemakkelijkste procedures om uit te voeren en er snelle en nauwkeurige resultaten uit te halen.
Het volgende zoekalgoritme is van toepassing:
- Om het vereiste record te vinden, moet u de binaire zoekopdracht uitvoeren op de beschikbare records in de boomstructuur.
- In het geval van een exacte match met de zoeksleutel, wordt het corresponderende record teruggestuurd naar de gebruiker.
- Als de exacte sleutel niet wordt gevonden door de zoekopdracht in de bovenliggende, huidige of leaf-node, wordt een "niet gevonden bericht" aan de gebruiker getoond.
- Het zoekproces kan opnieuw worden uitgevoerd voor betere en nauwkeurigere resultaten.
Zoekbewerkingsalgoritme
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."
Uitgang :
Het overeenkomende record dat tegen de exacte sleutel is ingesteld, wordt aan de gebruiker getoond; anders wordt een mislukte poging aan de gebruiker getoond.
Plaats operatie
Het volgende algoritme is van toepassing op de invoegbewerking:
- 50 procent van de elementen in de knooppunten wordt voor opslag naar een nieuw blad verplaatst.
- De ouder van het nieuwe blad wordt nauwkeurig gekoppeld aan de minimale sleutelwaarde en een nieuwe locatie in de boom.
- Splits het bovenliggende knooppunt in meer locaties voor het geval het volledig wordt gebruikt.
- Voor betere resultaten is de middelste toets nu gekoppeld aan het knooppunt op het hoogste niveau van dat blad.
- Blijf het proces herhalen dat in de bovenstaande stappen wordt uitgelegd totdat het knooppunt op het hoogste niveau niet wordt gevonden.
Voeg het bedieningsalgoritme in
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.
Uitgang :
Het algoritme zal het element bepalen en het met succes invoegen in het vereiste bladknooppunt.
Het bovenstaande B + Tree-voorbeeldvoorbeeld wordt uitgelegd in de onderstaande stappen:
- Ten eerste hebben we 3 knooppunten en de eerste 3 elementen, 1, 4 en 6, worden op de juiste locaties in de knooppunten toegevoegd.
- De volgende waarde in de reeks gegevens is 12 die deel moet uitmaken van de boom.
- Om dit te bereiken, deelt u het knooppunt in, voegt u 6 toe als een aanwijzerelement.
- Nu wordt een rechterhiërarchie van een boomstructuur gemaakt en worden de resterende gegevenswaarden dienovereenkomstig aangepast door rekening te houden met de toepasselijke regels van gelijk aan of groter dan waarden tegen de sleutelwaardeknooppunten aan de rechterkant.
Bewerking verwijderen
De complexiteit van de verwijderprocedure in de B + Tree overtreft die van de invoeg- en zoekfunctionaliteit.
Het volgende algoritme is van toepassing bij het verwijderen van een element uit de B + Tree:
- Ten eerste moeten we een bladitem in de boom zoeken dat de sleutel en de aanwijzer bevat. , verwijder het bladitem uit de boomstructuur als het blad voldoet aan de exacte voorwaarden voor het verwijderen van records.
- Als het bladknooppunt alleen voldoet aan de bevredigende factor om halfvol te zijn, is de bewerking voltooid; anders heeft de Leaf-node minimale invoer en kan deze niet worden verwijderd.
- De andere gekoppelde knooppunten aan de rechter- en linkerkant kunnen alle items leegmaken en ze vervolgens naar het blad verplaatsen. Als niet aan deze criteria wordt voldaan, moeten ze het bladknooppunt en het gekoppelde knooppunt in de boomhiërarchie combineren.
- Bij het samenvoegen van een leaf-knooppunt met zijn buren aan de rechter- of linkerkant, worden invoerwaarden van waarden in het leaf-knooppunt of de gekoppelde buur die naar het knooppunt op het hoogste niveau verwijst verwijderd.
Het bovenstaande voorbeeld illustreert de procedure om een element uit de B + Tree van een specifieke volgorde te verwijderen.
- Ten eerste worden de exacte locaties van het te verwijderen element geïdentificeerd in de boomstructuur.
- Hier kan het te verwijderen element alleen nauwkeurig worden geïdentificeerd op bladniveau en niet op de indexplaatsing. Daarom kan het element worden verwijderd zonder de verwijderingsregels te beïnvloeden, wat de waarde is van de absolute minimumsleutel.
- In het bovenstaande voorbeeld moeten we 31 uit de boomstructuur verwijderen.
- We moeten de instanties van 31 vinden in Index en Leaf.
- We kunnen zien dat 31 beschikbaar is op zowel Index- als Leaf-knooppuntniveau. Daarom verwijderen we het uit beide instanties.
- Maar we moeten de index vullen die naar 42 wijst. We zullen nu naar het juiste kind onder de 25 kijken en de minimumwaarde nemen en deze als index plaatsen. Dus 42 is de enige waarde die aanwezig is, het wordt de index.
Bewerkingsalgoritme verwijderen
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
Uitgang :
De sleutel "K" wordt verwijderd en sleutels worden geleend van broers en zussen voor het aanpassen van waarden in n en de bovenliggende knooppunten indien nodig.
Overzicht:
- B + Tree is een zelfbalancerende datastructuur voor het nauwkeurig en sneller zoeken, invoegen en verwijderen van procedures op data
- We kunnen eenvoudig volledige gegevens of gedeeltelijke gegevens opvragen omdat het efficiënt is om door de gekoppelde boomstructuur te gaan.
- De B + -boomstructuur groeit en krimpt met een toename / afname van het aantal opgeslagen records.
- Opslag van gegevens op de bladknooppunten en daaropvolgende vertakking van interne knooppunten verkort duidelijk de boomhoogte, wat de invoer- en uitvoerbewerkingen van de schijf vermindert, waardoor uiteindelijk veel minder ruimte op de opslagapparaten wordt verbruikt.