B+ TREE: Zoeken, invoegen en verwijderen Operaties

Wat is een B+-boom?

A B+ Boom Het wordt voornamelijk gebruikt voor het implementeren van dynamische indexering op meerdere niveaus. In vergelijking met een B-boom slaat de B+ boom de datapointers alleen op bij de bladknoppen van de boom, waardoor het zoekproces nauwkeuriger en sneller verloopt.

Regels voor B+ Boom

Hieronder volgen de essentiële regels voor een B+-boom.

• Bladeren worden gebruikt om gegevensrecords op te slaan.
• De gegevens worden opgeslagen in de interne knooppunten van de boomstructuur.
• Als de waarde van een doelsleutel kleiner is dan die van het interne knooppunt, wordt de aanwijzer direct links daarvan gevolgd.
• Als de waarde van een doelsleutel groter is dan of gelijk aan de waarde van het interne knooppunt, wordt de aanwijzer direct rechts daarvan gevolgd.
• De wortel heeft minimaal twee kinderen.

Waarom B+Tree gebruiken

Hieronder volgen redenen om een ​​B+ boom te gebruiken:

• Sleutels worden voornamelijk gebruikt om het zoeken te vergemakkelijken door naar het juiste blad te wijzen.
• Een B+ boom gebruikt een "vullingsfactor" 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 volledige scan van alle elementen vereist slechts één lineaire doorgang, omdat alle bladknoppen van een B+-boom met elkaar verbonden zijn.

B+ Boom versus B Boom

Hieronder volgen de belangrijkste verschillen tussen een B+ boom en een B boom.

Zoeken Operatie

In een B+ boom is een zoekopdracht een van de eenvoudigste procedures om uit te voeren en levert deze snelle en nauwkeurige resultaten op.

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.

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

Output: 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 boomstructuur.
• Splits het bovenliggende knooppunt op in meer locaties voor het geval het volledig wordt benut.
• Voor betere resultaten wordt de centrale sleutel 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. 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.

Output: 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:

• Allereerst hebben we 3 knooppunten, en de eerste 3 elementen, namelijk 1, 4 en 6, worden op de juiste plaatsen in de knooppunten toegevoegd.
• De volgende waarde in de reeks is 12, die onderdeel moet worden van de boomstructuur.
• Om dit te bereiken, deel je het knooppunt en voeg je 6 toe als aanwijzerelement.
• Nu wordt een rechts-hiërarchie van een boom gecreëerd en worden de resterende gegevenswaarden dienovereenkomstig aangepast door kee.ping Houd daarbij rekening met de geldende regels voor waarden die gelijk zijn aan of groter zijn dan de waarden die gelden voor de sleutel-waardeparen aan de rechterkant.

Verwijdering 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:

• Allereerst moeten we een bladvermelding in de boomstructuur vinden die de sleutel en de aanwijzer bevat. Vervolgens verwijderen we die bladvermelding uit de boomstructuur als deze voldoet aan de exacte voorwaarden voor het verwijderen van een record.
• Als het bladknooppunt slechts voor de helft gevuld is, is de bewerking voltooid; anders bevat het bladknooppunt te weinig gegevens en kan het niet worden verwijderd.
• De andere gekoppelde knooppunten aan de rechter- en linkerkant kunnen alle vermeldingen vrijmaken en deze vervolgens naar het blad verplaatsen. Als aan deze criteria niet wordt voldaan, moeten ze het bladknooppunt en het daaraan gekoppelde knooppunt in de boomstructuur samenvoegen.
• Bij het samenvoegen van een bladknooppunt met zijn buren aan de rechter- of linkerkant worden de waarden in het bladknooppunt of de gekoppelde buur die naar het knooppunt op het hoogste niveau verwijzen, verwijderd.

Het bovenstaande voorbeeld illustreert de procedure voor het verwijderen van een element uit een B+ boom van een specifieke orde.

• Ten eerste worden de exacte locaties van het te verwijderen element in de boom geïdentificeerd.
• Het te verwijderen element kan hier alleen nauwkeurig worden geïdentificeerd op het bladniveau en niet op indexniveau. Het element kan dus worden verwijderd zonder de verwijderingsregels te beïnvloeden, wat de waarde van de minimale sleutel is.

• In het bovenstaande voorbeeld moeten we 31 uit de boom verwijderen.
• We moeten de instanties van 31 in de index en de bladeren lokaliseren.
• We zien dat 31 zowel op index- als op bladknooppuntniveau aanwezig is. Daarom verwijderen we het uit beide instanties.
• Maar we moeten de index die naar 42 verwijst invullen. We kijken nu naar het juiste kind onder de 25 en nemen de laagste waarde om die als index te gebruiken. Omdat 42 de enige aanwezige waarde is, wordt dat de index.

Verwijdering Operaalgoritme

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

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

Veelgestelde vragen