B+ TREE: Beispiel für Such-, Einfüge- und Löschvorgänge

Was ist ein B+-Baum?

A B+ Baum wird hauptsächlich zur Implementierung einer dynamischen Indizierung auf mehreren Ebenen verwendet. Im Vergleich zum B-Baum speichert der B+-Baum die Datenzeiger nur an den Blattknoten des Baums, wodurch der Suchvorgang präziser und schneller wird.

Regeln für B+-Baum

Hier sind wesentliche Regeln für B+ Tree.

  • Blätter dienen der Speicherung von Datensätzen.
  • Es wird in den internen Knoten des Baums gespeichert.
  • Wenn ein Zielschlüsselwert kleiner als der interne Knoten ist, wird der Punkt direkt links davon verfolgt.
  • Wenn ein Zielschlüsselwert größer oder gleich dem internen Knoten ist, wird der Punkt unmittelbar rechts davon verfolgt.
  • Die Wurzel hat mindestens zwei Kinder.

Warum B+ Tree verwenden?

Hier sind Gründe für die Verwendung von B+ Tree:

  • Schlüssel werden hauptsächlich verwendet, um die Suche zu erleichtern, indem sie zum richtigen Blatt führen.
  • B+ Tree verwendet einen „Füllfaktor“, um die Zunahme und Abnahme in einem Baum zu verwalten.
  • 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.
  • Ein umfassender vollständiger Scan aller Elemente ist ein Baum, der nur einen linearen Durchgang benötigt, da alle Blattknoten eines B+-Baums miteinander verknüpft sind.

B+-Baum vs. B-Baum

Hier sind die Hauptunterschiede zwischen B+ Tree und B Tree

B+ Baum B Baum
Suchschlüssel können wiederholt werden. Suchschlüssel dürfen nicht redundant sein.
Daten werden nur auf den Blattknoten gespeichert. Sowohl Blattknoten als auch interne Knoten können Daten speichern
Auf dem Blattknoten gespeicherte Daten machen die Suche genauer und schneller. Searching ist aufgrund der auf Leaf und internen Knoten gespeicherten Daten langsam.
Das Löschen ist nicht schwierig, da ein Element nur aus einem Blattknoten entfernt wird. Das Löschen von Elementen ist ein komplizierter und zeitaufwändiger Vorgang.
Verknüpfte Blattknoten machen die Suche effizient und schnell. Blattknoten können nicht verknüpft werden.

Suchvorgang

In B+ Tree ist eine Suche eines der am einfachsten durchzuführenden Verfahren, mit der man schnelle und genaue Ergebnisse erhält.

Die folgendenwing 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 bei der 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.

Suchoperationsalgorithmus

 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:

Der übereinstimmende Datensatz mit dem genauen Schlüssel wird dem Benutzer angezeigt. anderewise, wird dem Benutzer ein fehlgeschlagener Versuch angezeigt.

Vorgang einfügen

Die folgendenwing Der Algorithmus ist für die Einfügeoperation anwendbar:

  • 50 Prozent der Elemente in den Knoten werden zur Speicherung in ein neues Blatt verschoben.
  • Das übergeordnete Element des neuen Blatts wird genau 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 mittlere Schlüssel nun mit dem Knoten der obersten Ebene dieses Blatts verknüpft.
  • Wiederholen Sie den in den obigen Schritten erläuterten Prozess, bis der Knoten der obersten Ebene nicht gefunden wird.

Operationsalgorithmus einfügen

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.  

Output:

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

Vorgang einfügen

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

  • Erstens haben wir drei Knoten, und die ersten drei Elemente, nämlich 3, 3 und 1, werden an den entsprechenden 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 rechte Hierarchie eines Baums erstellt und die verbleibenden Datenwerte werden entsprechend angepasst, indem die geltenden Regeln für Gleich- oder Größer-Werte für die Schlüsselwertknoten auf der rechten Seite berücksichtigt werden.

Vorgang löschen

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

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

  • Zuerst müssen wir einen Blatteintrag im Baum finden, der den Schlüssel und den Zeiger enthält. , löschen Sie den Blatteintrag aus dem Baum, wenn das Blatt die genauen Bedingungen für das Löschen von Datensätzen erfüllt.
  • Falls der Blattknoten nur den zufriedenstellenden Faktor erfüllt, halb voll zu sein, ist die Operation abgeschlossen; anderewise, der Blattknoten hat Mindesteinträge und kann nicht gelöscht werden.
  • Die anderen verknüpften Knoten rechts und links können alle Einträge löschen und sie dann in das Blatt verschieben. Wenn diese Kriterien nicht erfüllt sind, sollten sie den Blattknoten und seinen verknüpften Knoten in der Baumhierarchie kombinieren.
  • Beim Zusammenführen des Blattknotens mit seinen Nachbarn auf der rechten oder linken Seite werden Einträge von Werten im Blattknoten oder im verknüpften Nachbarn, die auf den Knoten der obersten Ebene zeigen, gelöscht.

Vorgang löschen

Das obige Beispiel veranschaulicht die Vorgehensweise zum Entfernen eines Elements aus dem B+-Baum einer bestimmten Reihenfolge.

  • Zunächst werden die genauen Positionen des zu löschenden Elements im Baum identifiziert.
  • Hier kann das zu löschende Element nur auf Blattebene und nicht an der Indexplatzierung genau identifiziert werden. Daher kann das Element gelöscht werden, ohne dass sich dies auf die Löschregeln auswirkt, bei denen es sich um den Wert des absoluten Mindestschlüssels handelt.

Vorgang löschen

  • Im obigen Beispiel müssen wir 31 aus dem Baum löschen.
  • Wir müssen die Instanzen von 31 in Index und Leaf finden.
  • Wir können sehen, dass 31 sowohl auf Index- als auch auf Blattknotenebene verfügbar ist. Daher löschen wir es aus beiden Instanzen.
  • Aber wir müssen den Index so füllen, dass er auf 42 zeigt. Wir schauen uns nun das rechte Kind unter 25 an, nehmen den Mindestwert und platzieren ihn als Index. Da also 42 der einzige vorhandene Wert ist, wird er zum Index.

Operationsalgorithmus löschen

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

Output:

Der Schlüssel „K“ wird gelöscht und Schlüssel werden von Geschwistern ausgeliehen, um bei Bedarf Werte in n und seinen übergeordneten Knoten anzupassen.

Zusammenfassung

  • B+ Tree ist ein selbstausgleichender Baum Datenstruktur für eine präzise und schnellere Ausführungarching, Einfügen und Löschen von Prozeduren für Daten
  • Wir können problemlos vollständige Daten oder Teildaten abrufen, da die Verwendung der verknüpften Baumstruktur dies effizient macht.
  • Die B+-Baumstruktur wächst und schrumpft mit einer Zunahme/Abnahme der Anzahl der gespeicherten Datensätze.
  • Durch die Speicherung von Daten auf den Blattknoten und die anschließende Verzweigung interner Knoten wird die Baumhöhe offensichtlich verkürzt, was die Eingabe- und Ausgabevorgänge auf der Festplatte reduziert und letztendlich viel weniger Platz auf den Speichergeräten verbraucht.