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

Inhaltsverzeichnis:

Anonim

Was ist ein B + Baum?

Ein B + -Baum wird hauptsächlich zum Implementieren der dynamischen Indizierung auf mehreren Ebenen verwendet. Im Vergleich zu B-Tree speichert der B + Tree die Datenzeiger nur an den Blattknoten des Tree, wodurch die Suche genauer und schneller verarbeitet wird.

In diesem B + Tree-Tutorial lernen Sie:

  • Was ist ein B + Baum?
  • Regeln für B + Tree
  • Warum B + Tree verwenden?
  • B + Baum gegen B Baum
  • Suchvorgang
  • Operation einfügen
  • Vorgang löschen

Regeln für B + Tree

Hier sind wichtige Regeln für B + Tree.

  • Blätter werden zum Speichern von Datensätzen verwendet.
  • Es wurde in den internen Knoten des Baums gespeichert.
  • Wenn ein Zielschlüsselwert kleiner als der interne Knoten ist, wird dem Punkt direkt auf der linken Seite gefolgt.
  • Wenn ein Zielschlüsselwert größer oder gleich dem internen Knoten ist, wird dem Punkt direkt auf seiner rechten Seite gefolgt.
  • 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 unterstützen, indem sie zum richtigen Blatt geleitet werden.
  • B + Tree verwendet einen "Füllfaktor", um die Zunahme und Abnahme eines Baums zu verwalten.
  • In B + -Bäumen können zahlreiche Schlüssel leicht auf der Speicherseite platziert werden, da ihnen nicht die Daten zugeordnet sind, die den inneren Knoten zugeordnet sind. Daher wird schnell auf Baumdaten zugegriffen, 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 verbunden sind.

B + Baum gegen B Baum

Hier sind die Hauptunterschiede zwischen B + Tree und B Tree

B + Baum B Baum
Suchschlüssel können wiederholt werden. Suchschlüssel können 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 aufgrund der auf Leaf und internen Knoten gespeicherten Daten langsam.
Das Löschen ist nicht schwierig, da ein Element nur von 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. Sie können keine Blattknoten verknüpfen.

Suchvorgang

In B + Tree ist eine Suche eine der am einfachsten auszuführenden Prozeduren, um schnelle und genaue Ergebnisse zu erhalten.

Der folgende Suchalgorithmus ist anwendbar:

  • Um den erforderlichen Datensatz zu finden, müssen Sie die binäre Suche für die verfügbaren Datensätze im Baum ausführen.
  • Bei einer genauen Übereinstimmung mit dem Suchschlüssel wird der entsprechende Datensatz an den Benutzer zurückgegeben.
  • Wenn der genaue Schlüssel bei der Suche im übergeordneten, aktuellen oder Blattknoten nicht gefunden wird, wird dem Benutzer eine "nicht gefundene Nachricht" angezeigt.
  • Der Suchvorgang kann erneut ausgeführt werden, um bessere und genauere Ergebnisse zu erzielen.

Suchoperationsalgorithmus

1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."

Ausgabe :

Der gegen den genauen Schlüssel gesetzte übereinstimmende Datensatz wird dem Benutzer angezeigt. Andernfalls wird dem Benutzer ein fehlgeschlagener Versuch angezeigt.

Operation einfügen

Der folgende 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 Blattes ist genau mit dem minimalen Schlüsselwert und einer neuen Position im Baum verknüpft.
  • Teilen Sie den übergeordneten Knoten in mehrere Speicherorte auf, falls er vollständig genutzt wird.
  • Um bessere Ergebnisse zu erzielen, wird der mittlere Schlüssel jetzt dem Knoten der obersten Ebene dieses Blattes zugeordnet.
  • Bis der Knoten der obersten Ebene nicht gefunden wird, wiederholen Sie den in den obigen Schritten erläuterten Prozess.

Operationsalgorithmus einfügen

1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. 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 treeb. 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.

Ausgabe :

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

Das obige B + Tree-Beispielbeispiel wird in den folgenden Schritten erläutert:

  • Erstens haben wir 3 Knoten, und die ersten 3 Elemente, 1, 4 und 6, werden an geeigneten Stellen in den Knoten hinzugefügt.
  • Der nächste Wert in der Datenreihe ist 12, der Teil des Baums sein muss.
  • Um dies zu erreichen, teilen Sie den Knoten und fügen Sie 6 als Zeigerelement hinzu.
  • Jetzt wird eine rechte Hierarchie eines Baums erstellt, und die verbleibenden Datenwerte werden entsprechend angepasst, indem die anwendbaren Regeln berücksichtigt werden, die gleich oder größer als die Werte für die Schlüsselwertknoten auf der rechten Seite sind.

Vorgang löschen

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 suchen, 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.
  • Wenn der Blattknoten nur den zufriedenstellenden Faktor erfüllt, halb voll zu sein, ist die Operation abgeschlossen; Andernfalls verfügt der Blattknoten über minimale Einträge und kann nicht gelöscht werden.
  • Die anderen verknüpften Knoten rechts und links können alle Einträge räumen und 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 rechts oder links werden Werteinträge im Blattknoten oder verknüpften Nachbarn, die auf den Knoten der obersten Ebene zeigen, gelöscht.

Das obige Beispiel zeigt 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 bei der Indexplatzierung genau identifiziert werden. Daher kann das Element gelöscht werden, ohne die Löschregeln zu beeinflussen, bei denen es sich um den Wert des Bare-Minimum-Schlüssels handelt.

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

Betriebsalgorithmus löschen

1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) 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 nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node

Ausgabe :

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 eine selbstausgleichende Datenstruktur zum Ausführen genauer und schnellerer Such-, Einfüge- und Löschvorgänge für Daten
  • Wir können problemlos vollständige oder teilweise Daten abrufen, da das Durchlaufen der verknüpften Baumstruktur die Effizienz erhöht.
  • Die B + -Baumstruktur wächst und schrumpft mit einer Zunahme / Abnahme der Anzahl gespeicherter Datensätze.
  • Das Speichern von Daten auf den Blattknoten und das anschließende Verzweigen von internen Knoten verkürzen offensichtlich die Baumhöhe, was die Eingabe- und Ausgabeoperationen der Festplatte verringert und letztendlich viel weniger Speicherplatz auf den Speichergeräten verbraucht.