B+ TREE: Suchen, Einfügen und Löschen OperaBeispiel

Was ist ein B+-Baum?

A B+ Baum wird hauptsächlich zur Implementierung dynamischer Indizierung auf mehreren Ebenen verwendet. Im Vergleich zum B-Baum speichert der B+-Baum die Datenzeiger nur in den Blattknoten des Baums, was den Suchvorgang genauer und schneller macht.

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:

• Tasten werden in erster Linie verwendet, um die Suche zu erleichtern, indem sie zum richtigen Blatt leiten.
• 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.	Die Suche ist langsam, da die Daten auf Leaf- und internen Knoten gespeichert sind.
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.

Suche OperaProduktion

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

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

Insert Operationsalgorithmus

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.  

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:

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

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:

• 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 von halb voll erfüllt, ist der Vorgang abgeschlossen. Andernfalls weist der Blattknoten nur minimale Einträge auf 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.

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.

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

Löschen Operationsalgorithmus

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

Ausgang:

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 zur Durchführung präziser und schnellerer Such-, Einfüge- und Löschvorgänge auf 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 der internen Knoten wird offensichtlich die Baumhöhe verkürzt, was die Ein- und Ausgabevorgänge auf der Festplatte reduziert und letzten Endes viel weniger Platz auf den Speichergeräten verbraucht.