B+ BOOM: Zoeken, invoegen en verwijderen Operaties Voorbeeld

Wat is een B+-boom?

A B+ Boom wordt voornamelijk gebruikt voor het implementeren van dynamische indexering op meerdere niveaus. Vergeleken met B-Tree slaat de B+ Tree de datapointers alleen op bij de leaf nodes van de Tree, wat het zoeken nauwkeuriger en sneller maakt.

Regels voor B+ Boom

Hier zijn essentiële regels voor B+ Tree.

• Bladeren worden gebruikt om gegevensrecords op te slaan.
• Het wordt 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:

• Sleutels worden voornamelijk gebruikt om het zoeken te vergemakkelijken door naar het juiste blad te verwijzen.
• B+ Tree gebruikt een “vulfactor” om de toename en afname in een boom te beheren.
• In B+-bomen kunnen eenvoudig talloze sleutels op de geheugenpagina worden geplaatst, omdat ze niet de gegevens bevatten die zijn gekoppeld aan de interne knooppunten. Daarom heeft het snel toegang tot boomgegevens die zich op het bladknooppunt bevinden.
• Een uitgebreide volledige scan van alle elementen levert een boom op die slechts één lineaire doorgang nodig heeft, omdat alle bladknopen van een B+ boom met elkaar verbonden zijn.

B+ Boom versus B Boom

Hier zijn de belangrijkste verschillen tussen B+ Tree en B Tree

B+ Boom	B Boom
Zoektoetsen kunnen worden herhaald.	Zoeksleutels mogen niet overbodig zijn.
Gegevens worden alleen opgeslagen op de bladknooppunten.	Zowel bladknooppunten als interne knooppunten kunnen gegevens opslaan
Gegevens die op het bladknooppunt zijn opgeslagen, maken de zoekopdracht nauwkeuriger en sneller.	Het zoeken verloopt traag omdat de gegevens op Leaf en interne knooppunten zijn opgeslagen.
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 bladknooppunten niet koppelen.

Zoek Operatie

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 opdracht uitvoeren Binaire zoekopdracht op de beschikbare records in de boom.
• Bij een exacte match met de zoeksleutel wordt het bijbehorende record teruggegeven aan de gebruiker.
• Als de exacte sleutel niet kan worden gevonden door de zoekopdracht in het bovenliggende, huidige of bladknooppunt, wordt er een 'niet gevonden'-bericht aan de gebruiker weergegeven.
• Het zoekproces kan opnieuw worden uitgevoerd voor betere en nauwkeurigere resultaten.

Zoek Operaalgoritme

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

uitgang:

De overeenkomende recordset voor de exacte sleutel wordt aan de gebruiker getoond. Anders wordt een mislukte poging aan de gebruiker getoond.

Invoegen 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 is nauwkeurig gekoppeld aan de minimale sleutelwaarde en een nieuwe locatie in de Boom.
• Splits het bovenliggende knooppunt op in meer locaties voor het geval het volledig wordt benut.
• Voor betere resultaten is de middelste toets nu gekoppeld aan het knooppunt op het hoogste niveau van dat blad.
• Totdat het knooppunt op het hoogste niveau niet is gevonden, blijft u het proces herhalen dat in de bovenstaande stappen is uitgelegd.

Invoegen Operaalgoritme

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.  

uitgang:

Het algoritme bepaalt het element en voegt het met succes in het vereiste bladknooppunt in.

Het bovenstaande B+ Tree-voorbeeldvoorbeeld wordt in de onderstaande stappen uitgelegd:

• Ten eerste hebben we 3 knooppunten en de eerste 3 elementen, namelijk 1, 4 en 6, worden op de juiste locaties in de knooppunten toegevoegd.
• De volgende waarde in de reeks gegevens is 12 en moet deel uitmaken van de boom.
• Om dit te bereiken verdeelt u het knooppunt en voegt u 6 toe als aanwijzerelement.
• Nu wordt er een rechterhiërarchie van een boom gecreëerd, en de resterende gegevenswaarden worden dienovereenkomstig aangepast door de toepasselijke regels van gelijk aan of groter dan waarden in gedachten te houden ten opzichte van de sleutelwaardeknooppunten aan de rechterkant.

Verwijder Operatie

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 vinden dat de sleutel en de aanwijzer bevat. verwijdert u het bladitem uit de boom als het blad voldoet aan de exacte voorwaarden voor het verwijderen van records.
• Indien het bladknooppunt slechts aan de bevredigende factor van halfvol voldoet, is de bewerking voltooid. Indien dit niet het geval is, heeft het bladknooppunt een minimum aantal invoeren en kan het niet worden verwijderd.
• De andere gekoppelde knooppunten aan de rechter- en linkerkant kunnen alle vermeldingen verlaten en deze vervolgens naar het Blad verplaatsen. Als niet aan deze criteria wordt voldaan, moeten ze het bladknooppunt en het daaraan gekoppelde knooppunt in de boomhiërarchie combineren.
• Bij het samenvoegen van een bladknooppunt met zijn buren aan de rechter- of linkerkant, worden invoer van waarden in het bladknooppunt of de gekoppelde buur die naar het knooppunt op het hoogste niveau wijst, verwijderd.

Het bovenstaande voorbeeld illustreert de procedure om een ​​element uit de B+ Boom van een specifieke bestelling te verwijderen.

• Ten eerste worden de exacte locaties van het te verwijderen element in de boom geïdentificeerd.
• Hier kan het te verwijderen element alleen nauwkeurig worden geïdentificeerd op leaf-niveau en niet op de indexplaatsing. Daarom kan het element worden verwijderd zonder dat dit gevolgen heeft voor de verwijderingsregels, wat de waarde is van de absolute minimumsleutel.

• In het bovenstaande voorbeeld moeten we 31 uit de boom verwijderen.
• We moeten de exemplaren van 31 in Index en Leaf lokaliseren.
• 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 invullen die naar 42 wijst. We zullen nu naar het juiste kind onder de 25 kijken, de minimumwaarde nemen en deze als index plaatsen. Omdat 42 dus de enige aanwezige waarde is, wordt dit de index.

Verwijder Operaalgoritme

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

uitgang:

De sleutel “K” wordt verwijderd en sleutels worden geleend van broers en zussen om de waarden in n en de bovenliggende knooppunten indien nodig aan te passen.

Samenvatting

• B+ Tree is een zelfbalancerend middel data structuur voor het uitvoeren van nauwkeurige en snellere zoek-, invoeg- en verwijderprocedures op gegevens
• We kunnen eenvoudig volledige gegevens of gedeeltelijke gegevens ophalen, omdat het doorlopen van de gekoppelde boomstructuur dit efficiënt maakt.
• De B+-boomstructuur groeit en krimpt met een toename/afname van het aantal opgeslagen records.
• Het opslaan van gegevens op de bladknooppunten en het vervolgens vertakken van interne knooppunten zorgt er duidelijk voor dat de boomhoogte korter wordt, waardoor er minder invoer- en uitvoerbewerkingen op de schijf nodig zijn en er uiteindelijk veel minder ruimte op de opslagapparaten wordt gebruikt.