B-BAUM in der Datenstruktur: Suchen, Einfügen, Löschen OperaBeispiel (2024)

Regeln für B-Baum

Hier finden Sie wichtige Regeln zum Erstellen von B_Tree

• Alle Blätter werden auf der gleichen Ebene erstellt.
• Der B-Baum wird durch eine Reihe von Graden bestimmt, die auch als „Ordnung“ (angegeben durch einen externen Akteur, wie einen Programmierer) bezeichnet werden

  m

  weiter. Der Wert von

  m

  hängt von der Blockgröße auf der Festplatte ab, auf der sich die Daten befindenmarily gelegen.

  See Also

  B+ TREE: Suchen, Einfügen und Löschen OperaBeispielGuide to the B-Tree Data StructureIntroduction of B-Tree - GeeksforGeeksB-Baum: Ordnung, Einfügen, Löschen mit Beispiel

• Der linke Teilbaum des Knotens hat kleinere Werte als die rechte Seite des Teilbaums. Das bedeutet, dass die Knoten auch in aufsteigender Reihenfolge von links nach rechts sortiert sind.
• Die maximale Anzahl an untergeordneten Knoten, die ein Wurzelknoten und seine untergeordneten Knoten enthalten können, wird nach dieser Formel berechnet:

  m – 1

  Beispielsweise:

  m = 4max keys: 4 – 1 = 3

• Jeder Knoten außer Root muss mindestens Schlüssel von enthalten

  [m/2]-1

  Beispielsweise:

  m = 4min keys: 4/2-1 = 1

• Die maximale Anzahl untergeordneter Knoten, die ein Knoten haben kann, entspricht seinem Grad

  m

• Die minimalen untergeordneten Elemente, die ein Knoten haben kann, sind die Hälfte der Ordnung, also m/2 (es wird der Obergrenzenwert genommen).
• Alle Schlüssel in einem Knoten werden in aufsteigender Reihenfolge sortiert.

Warum B-Tree verwenden?

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

• Reduziert die Anzahl der Lesevorgänge auf der Festplatte
• B-Bäume können leicht optimiert werden, um ihre Größe (d. h. die Anzahl der untergeordneten Knoten) entsprechend der Festplattengröße anzupassen
• Es handelt sich um eine speziell entwickelte Technik zur Verarbeitung großer Datenmengen.
• Es ist ein nützlicher Algorithmus für Datenbanken und Dateisysteme.
• Eine gute Wahl, wenn es um das Lesen und Schreiben großer Datenblöcke geht

Geschichte von B Tree

• Daten werden in Blöcken auf der Festplatte gespeichert. Wenn diese Daten in den Hauptspeicher (oder RAM) übertragen werden, werden sie als Datenstruktur bezeichnet.
• Im Falle großer Datenmengen, zarchiUm einen Datensatz auf der Festplatte zu erstellen, muss die gesamte Festplatte gelesen werden. Dies erhöht den Zeit- und Hauptspeicherverbrauch aufgrund der hohen Festplattenzugriffsfrequenz und Datengröße.
• Um dieses Problem zu lösen, werden Indextabellen erstellt, die die Datensatzreferenz der Datensätze basierend auf den Blöcken, in denen sie sich befinden, speichern. Dies reduziert den Zeit- und Speicherverbrauch drastisch.
• Da wir über riesige Datenmengen verfügen, können wir mehrstufige Indextabellen erstellen.
• Mithilfe von B Tree kann ein mehrstufiger Index entworfen werden, um die Daten selbstausgleichend zu sortieren.

Suche OperaProduktion

Die Suche operation ist die einfachste operation auf B-Baum.

Die folgendenwing Algorithmus wird angewendet:

• Lassen Sie den Schlüssel (den Wert) durch „k“ durchsuchen.
• Starten Sie searching von der Wurzel aus und rekursiv nach unten durchlaufen.
• Wenn k kleiner als der Wurzelwert ist, durchsuchen Sie den linken Teilbaum. Wenn k größer als der Wurzelwert ist, durchsuchen Sie den rechten Teilbaum.
• Wenn der Knoten das gefundene k hat, geben Sie den Knoten einfach zurück.
• Wenn das k nicht im Knoten gefunden wird, gehen Sie zum untergeordneten Knoten mit einem größeren Schlüssel.
• Wenn k nicht im Baum gefunden wird, geben wir NULL zurück.

Insert OperaProduktion

Da es sich bei B Tree um einen selbstausgleichenden Baum handelt, können Sie nicht erzwingen, dass ein Schlüssel in einen beliebigen Knoten eingefügt wird.

Die folgendenwing Algorithmus gilt:

• Führen Sie die Suche aus operatung und finden Sie die passende Einfügestelle.
• Fügen Sie den neuen Schlüssel an der richtigen Stelle ein. Wenn der Knoten jedoch bereits über die maximale Anzahl an Schlüsseln verfügt:
• Der Knoten wird zusammen mit einem neu eingefügten Schlüssel vom mittleren Element getrennt.
• Das mittlere Element wird zum übergeordneten Element für die anderen beiden untergeordneten Knoten.
• Die Knoten müssen die Schlüssel in aufsteigender Reihenfolge neu anordnen.

Im obigen Beispiel:

• Suchen Sie die entsprechende Position im Knoten nach dem Schlüssel
• Stecken Sie den Schlüssel in die target Knoten, und suchen Sie nach Regeln
• Verfügt der Knoten nach dem Einfügen über mehr als die Mindestanzahl an Schlüsseln, die 1 beträgt? In diesem Fall ja, das ist der Fall. Überprüfen Sie die nächste Regel.
• Verfügt der Knoten nach dem Einfügen über mehr als die maximale Anzahl von Schlüsseln, die 3 beträgt? In diesem Fall nein, das ist nicht der Fall. Dies bedeutet, dass der B-Baum keine Regeln verletzt und die Einfügung abgeschlossen ist.

Im obigen Beispiel:

• Der Knoten hat die maximale Anzahl an Schlüsseln erreicht
• Der Knoten wird geteilt und der mittlere Schlüssel wird zum Wurzelknoten der beiden anderen Knoten.
• Bei einer geraden Anzahl von Schlüsseln wird der mittlere Knoten nach links oder rechts ausgerichtet ausgewählt.

Im obigen Beispiel:

• Der Knoten hat weniger als die maximale Anzahl an Schlüsseln
• 1 wird neben 3 eingefügt, aber die Regel der aufsteigenden Reihenfolge wird verletzt
• Um dies zu beheben, werden die Schlüssel sortiert

Ebenso können 13 und 2 problemlos in den Knoten eingefügt werden, da sie die Regel für weniger als maximale Schlüssel für die Knoten erfüllen.

Im obigen Beispiel:

• Der Knoten verfügt über Schlüssel, die der maximalen Anzahl an Schlüsseln entsprechen.
• Der Schlüssel wird in die target Knoten, aber es verstößt gegen die Regel der maximalen Schlüsselzahl.
• Die target Knoten wird geteilt und der mittlere Schlüssel mit der Linksneigung ist nun der übergeordnete Knoten der neuen untergeordneten Knoten.
• Die neuen Knoten werden in aufsteigender Reihenfolge angeordnet.

In ähnlicher Weise können die restlichen Werte basierend auf den oben genannten Regeln und Fällen problemlos in den B-Baum eingefügt werden.

Löschen OperaProduktion

Das Löschen operation hat mehr Regeln als Einfügen und Suchen operanungen.

Die folgendenwing Algorithmus gilt:

• Führen Sie die Suche aus operation und finden Sie die target Geben Sie die Knoten ein
• Drei Bedingungen galten je nach Standort des target Schlüssel, wie im Folgenden erklärtwing Abschnitte

Besitzt das target Der Schlüssel befindet sich im Blattknoten

• Target befindet sich im Blattknoten, mehr als min Schlüssel.
• Durch das Löschen wird das Eigentum von B Tree nicht verletzt
• Target ist im Blattknoten, es hat min Schlüsselknoten
• Durch das Löschen wird das Eigentum von B Tree verletzt
• Target Knoten kann Schlüssel vom unmittelbar linken Knoten oder vom unmittelbar rechten Knoten (Geschwisterknoten) ausleihen
• Das Geschwister wird sagen ja wenn es mehr als die Mindestanzahl an Schlüsseln hat
• Der Schlüssel wird vom übergeordneten Knoten ausgeliehen, der Maximalwert wird an einen übergeordneten Knoten übertragen, der Maximalwert des übergeordneten Knotens wird an den übergeordneten Knoten übertragen. target und entfernen Sie den target Wert
• Target befindet sich im Blattknoten, aber kein Geschwister hat mehr als die Mindestanzahl an Schlüsseln
• Schlüssel suchen
• Mit Geschwistern und dem Minimum an übergeordneten Knoten zusammenführen
• Die Gesamtzahl der Schlüssel beträgt jetzt mehr als min
• Die target Schlüssel wird durch das Minimum eines übergeordneten Knotens ersetzt

Besitzt das target Schlüssel befindet sich in einem internen Knoten

• Wählen Sie entweder „Reihenfolge-Vorgänger“ oder „Reihenfolge-Nachfolger“.
• Im Falle eines Vorgängers in der richtigen Reihenfolge wird der maximale Schlüssel aus seinem linken Teilbaum ausgewählt
• Im Falle eines Nachfolgers in der richtigen Reihenfolge wird der minimale Schlüssel aus seinem rechten Teilbaum ausgewählt
• Besitzt das target Schlüssels in der Reihenfolge hat mehr als die min-Schlüssel, nur dann kann er den ersetzen target Schlüssel mit dem Maximum des In-Order-Vorgängers
• Besitzt das target Der Vorgänger des Schlüssels in der Reihenfolge hat nicht mehr als die Mindestanzahl an Schlüsseln. Suchen Sie nach dem Mindestschlüssel des Nachfolgers in der Reihenfolge.
• Besitzt das target Der in der Reihenfolge befindliche Vorgänger und Nachfolger des Schlüssels haben beide weniger als die Mindestanzahl an Schlüsseln. Dann werden Vorgänger und Nachfolger zusammengeführt.

Besitzt das target Der Schlüssel befindet sich in einem Stammknoten.

• Ersetzen Sie es durch das maximale Element des Vorgänger-Teilbaums in der Reihenfolge
• Wenn nach dem Löschen die target weniger als min Schlüssel hat, dann target Der Knoten wird den Maximalwert von seinem Geschwisterknoten über dessen übergeordneten Knoten übernehmen.
• Der Maximalwert des übergeordneten Elements wird übernommen von target, aber mit den Knoten des Maximalwerts des Geschwisters.

Lassen Sie uns nun das Löschen verstehen operaanhand eines Beispiels.

Das obige Diagramm zeigt verschiedene Löschfälle operation in einem B-Baum. Dieser B-Baum hat die Ordnung 5, was bedeutet, dass die Mindestanzahl an untergeordneten Knoten, die jeder Knoten haben kann, 3 und die maximale Anzahl an untergeordneten Knoten, die jeder Knoten haben kann, 5 beträgt kann 2 bzw. 4 haben.

Im obigen Beispiel:

• Die target Knoten hat die target Taste zum Löschen
• Die target Knoten hat mehr Schlüssel als Mindestanzahl an Schlüsseln
• Löschen Sie einfach den Schlüssel

Im obigen Beispiel:

• Die target Der Knoten hat Schlüssel, die den Mindestschlüsseln entsprechen, und kann ihn daher nicht direkt löschen, da dies gegen die Bedingungen verstoßen würde

Nun das Following Das Diagramm erklärt, wie dieser Schlüssel gelöscht wird:

• Die target Der Knoten wird einen Schlüssel vom unmittelbaren Geschwisterknoten leihen, in diesem Fall vom Vorgänger in der Reihenfolge (linker Geschwisterknoten), da er keinen Nachfolger in der Reihenfolge (rechter Geschwisterknoten) hat.
• Der Maximalwert des Inorder-Vorgängers wird an den übergeordneten Eintrag übertragen und dieser überträgt den Maximalwert an den target Knoten (siehe Diagramm unten)

Die folgendenwing Das Beispiel zeigt, wie ein Schlüssel, der einen Wert benötigt, aus seinem Nachfolger in der Reihenfolge gelöscht wird.

• Die target Der Knoten wird einen Schlüssel vom unmittelbaren Geschwisterknoten leihen, in diesem Fall vom Nachfolger in der Reihenfolge (rechter Geschwisterknoten), da sein Vorgänger in der Reihenfolge (linker Geschwisterknoten) über Schlüssel verfügt, die den Mindestschlüsselzahlen entsprechen.
• Der Mindestwert des Nachfolgers wird an den übergeordneten Wert übertragen, und der übergeordnete Wert überträgt den Höchstwert an den target Knoten.

Im folgenden Beispiel wird die target Knoten hat keinen Geschwisterknoten, der seinen Schlüssel an den target Knoten. Daher ist eine Zusammenführung erforderlich.

Sehen Sie sich die Vorgehensweise zum Löschen eines solchen Schlüssels an:

• Zusammenführen der target Knoten mit einem seiner unmittelbaren Geschwister zusammen mit dem übergeordneten Schlüssel
• Der Schlüssel vom übergeordneten Knoten wird ausgewählt, der zwischen den beiden zusammengeführten Knoten liegt
• Löschen Sie die target Schlüssel vom zusammengeführten Knoten

Löschen Operations-Pseudocode

private int removeBiggestElement(){ if (root has no child) remove and return the last element else { answer = subset[childCount-1].removeBiggestElement() if (subset[childCount-1].dataCount < MINIMUM) fixShort (childCount-1) return answer }}

Output:

Das größte Element wird aus dem B-Baum gelöscht.

Zusammenfassung

• B Tree ist eine selbstausgleichende Datenstruktur zum besseren Suchen, Einfügen und Löschen von Daten auf der Festplatte.
• B Tree wird durch den angegebenen Grad reguliert
• B Baumschlüssel und Knoten sind in aufsteigender Reihenfolge angeordnet.
• Die Suche operation von B Tree ist die einfachste, die immer von der Wurzel ausgeht und prüft, ob die target Schlüssel ist größer oder kleiner als der Knotenwert.
• Der Einsatz operaDie Beschreibung des B-Baums ist ziemlich detailliert, wobei zunächst eine geeignete Einfügeposition für den target Schlüssel, fügt ihn ein, bewertet die Gültigkeit des B-Baums anhand verschiedener Fälle und strukturiert die B-Baum-Knoten dann entsprechend neu.
• Das Löschen operation von B Tree sucht zuerst nach dem target Schlüssel, der gelöscht werden soll, löscht ihn, bewertet die Gültigkeit anhand verschiedener Fälle wie minimale und maximale Schlüssel des target Knoten, Geschwister und Elternteil.