B+ BAUM: Suchen, Einfügen und Löschen Operations

Was ist ein B+-Baum?

A B+ Baum Der B+-Baum wird primär zur Implementierung dynamischer Indizierung auf mehreren Ebenen verwendet. Im Vergleich zu einem B-Baum speichert der B+-Baum die Datenzeiger nur an den Blattknoten, was den Suchprozess genauer und schneller macht.

Regeln für B+-Baum

Hier sind die wichtigsten Regeln für einen B+-Baum.

• Blätter dienen der Speicherung von Datensätzen.
• Die Datensätze werden in den internen Knoten des Baums gespeichert.
• Ist der Wert eines Zielschlüssels kleiner als der des internen Knotens, so wird dem Zeiger direkt links davon gefolgt.
• Ist der Wert eines Zielschlüssels größer oder gleich dem Wert des internen Knotens, so wird dem Zeiger direkt rechts davon gefolgt.
• Die Wurzel hat mindestens zwei Kinder.

Warum B+ Tree verwenden?

Hier sind Gründe für die Verwendung eines B+-Baums:

• Schlüssel werden in erster Linie verwendet, um die Suche zu erleichtern, indem sie zum richtigen Seitenblatt führen.
• Ein B+-Baum verwendet einen „Füllfaktor“, um das Wachstum und die Abnahme innerhalb des Baums zu steuern.
• In B+-Bäumen können zahlreiche Schlüssel problemlos auf der Speicherseite platziert werden, da sie nicht über die mit den inneren Knoten verknüpften Daten verfügen. Daher kann schnell auf Baumdaten zugegriffen werden, die sich auf dem Blattknoten befinden.
• Für einen umfassenden vollständigen Scan aller Elemente ist nur ein linearer Durchlauf erforderlich, da alle Blattknoten eines B+-Baums miteinander verbunden sind.

B+-Baum vs. B-Baum

Hier sind die wichtigsten Unterschiede zwischen einem B+-Baum und einem B-Baum.

Suche OperaProduktion

In einem B+-Baum ist die Suche eine der einfachsten Prozeduren, die durchgeführt werden kann und schnelle und genaue Ergebnisse liefert.

Der folgende Suchalgorithmus ist anwendbar:

• Um den erforderlichen Datensatz zu finden, müssen Sie Folgendes ausführen binäre Suche auf die verfügbaren Datensätze im Baum.
• Bei einer genauen Übereinstimmung mit dem Suchschlüssel wird der entsprechende Datensatz an den Benutzer zurückgegeben.
• Falls der genaue Schlüssel durch die Suche im übergeordneten, aktuellen oder Blattknoten nicht gefunden wird, wird dem Benutzer die Meldung „Nicht gefunden“ angezeigt.
• Für bessere und genauere Ergebnisse kann der Suchvorgang erneut ausgeführt werden.

Suche Operationsalgorithmus

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

Ausgang: Dem Benutzer wird der mit dem genauen Schlüssel übereinstimmende Datensatz angezeigt. Andernfalls wird ihm ein fehlgeschlagener Versuch angezeigt.

Insert OperaProduktion

Für die Einfügeoperation ist folgender Algorithmus anwendbar:

• 50 Prozent der Elemente in den Knoten werden zur Speicherung in ein neues Blatt verschoben.
• Das übergeordnete Element des neuen Blattes ist präzise mit dem minimalen Schlüsselwert und einer neuen Position im Baum verknüpft.
• Teilen Sie den übergeordneten Knoten in mehrere Standorte auf, falls er vollständig ausgelastet ist.
• Um bessere Ergebnisse zu erzielen, wird der zentrale Schlüssel nun dem obersten Knoten dieses Blattes zugeordnet.
• Wiederholen Sie den in den obigen Schritten erläuterten Prozess, bis der Knoten der obersten Ebene nicht gefunden wird.

Insert Operationsalgorithmus

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.

Ausgang: Der Algorithmus ermittelt das Element und fügt es erfolgreich in den erforderlichen Blattknoten ein.

Das obige B+-Baum-Beispiel wird in den folgenden Schritten erklärt:

• Zunächst haben wir 3 Knoten, und die ersten 3 Elemente, nämlich 1, 4 und 6, werden an geeigneten Stellen in den Knoten hinzugefügt.
• Der nächste Wert in der Datenreihe ist 12, der in den Baum aufgenommen werden muss.
• Um dies zu erreichen, teilen Sie den Knoten und fügen Sie 6 als Zeigerelement hinzu.
• Nun wird eine Rechtshierarchie eines Baums erstellt, und die verbleibenden Datenwerte werden entsprechend durch kee angepasst.ping Beachten Sie die geltenden Regeln für Werte, die gleich oder größer als die Schlüssel-Wert-Knoten auf der rechten Seite sind.

Löschen OperaProduktion

Die Komplexität des Löschvorgangs im B+-Baum übertrifft die der Einfüge- und Suchfunktion.

Der folgende Algorithmus ist beim Löschen eines Elements aus dem B+-Baum anwendbar:

• Zunächst müssen wir einen Blatteintrag im Baum finden, der den Schlüssel und den Zeiger enthält. Anschließend löschen wir den Blatteintrag aus dem Baum, wenn der Blatteintrag die genauen Bedingungen für das Löschen eines Datensatzes erfüllt.
• Falls der Blattknoten nur die Bedingung erfüllt, halb voll zu sein, ist die Operation abgeschlossen; andernfalls hat der Blattknoten die Mindestanzahl an Einträgen und kann nicht gelöscht werden.
• Die anderen verbundenen Knoten rechts und links können beliebige Einträge freigeben und diese dann in das Blatt verschieben. Werden diese Kriterien nicht erfüllt, sollten sie den Blattknoten und den mit ihm verbundenen Knoten in der Baumhierarchie zusammenführen.
• Beim Zusammenführen eines Blattknotens mit seinen Nachbarn rechts oder links werden Einträge von Werten im Blattknoten oder verknüpften Nachbarn, die auf den Knoten der obersten Ebene verweisen, gelöscht.

Das obige Beispiel veranschaulicht das Vorgehen zum Entfernen eines Elements aus einem B+-Baum einer bestimmten Ordnung.

• Zunächst werden die genauen Positionen des zu löschenden Elements im Baum identifiziert.
• Hier lässt sich das zu löschende Element nur auf Blattebene, nicht aber an seiner Indexposition, exakt identifizieren. Daher kann das Element gelöscht werden, ohne die Löschregeln – den Wert des minimalen Schlüssels – zu beeinträchtigen.

• Im obigen Beispiel müssen wir 31 aus dem Baum löschen.
• Wir müssen die Vorkommen von 31 im Index und im Blatt finden.
• Wir sehen, dass 31 sowohl auf Index- als auch auf Blattknotenebene vorhanden ist. Daher löschen wir sie aus beiden Instanzen.
• Wir müssen aber den Index bis zur Zahl 42 füllen. Dazu betrachten wir das rechte Kind unter 25 Jahren, nehmen den kleinsten Wert und verwenden ihn als Index. Da 42 der einzige vorhandene Wert ist, wird er zum Index.

Löschen Operationsalgorithmus

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

Ausgang: Der Schlüssel „K“ wird gelöscht, und gegebenenfalls werden Schlüssel von Geschwisterknoten ausgeliehen, um Werte in n und seinen übergeordneten Knoten anzupassen.

Häufig gestellte Fragen