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

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 hauptsächlich befinden.

• 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 = 4
  max keys: 4 – 1 = 3
  

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

  [m/2]-1

  Beispielsweise:

  m = 4
  min 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.
• Bei großen Datenmengen erfordert die Suche nach einem Datensatz auf der Festplatte das Lesen der gesamten Festplatte. Aufgrund der hohen Festplattenzugriffsfrequenz und der Datengröße erhöht dies den Zeitaufwand und den Hauptspeicherverbrauch.
• 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 Suchoperation ist die einfachste Operation im B-Baum.

Der folgende Algorithmus wird angewendet:

• Lassen Sie den Schlüssel (den Wert) durch „k“ durchsuchen.
• Beginnen Sie mit der Suche an der Wurzel und durchlaufen Sie sie rekursiv nach unten.
• 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.

Es gilt folgender Algorithmus:

• Führen Sie den Suchvorgang aus und finden Sie die entsprechende 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.

TIPP	Folgendes trifft auf den Einfügealgorithmus nicht zu: Da der Knoten voll ist, wird er geteilt und dann wird ein neuer Wert eingefügt

Im obigen Beispiel:

• Suchen Sie die entsprechende Position im Knoten nach dem Schlüssel
• Fügen Sie den Schlüssel in den Zielknoten ein und prüfen Sie, ob Regeln vorliegen
• 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 den Zielknoten eingefügt, verstößt jedoch gegen die Regel der maximalen Schlüsselanzahl.
• Der Zielknoten wird geteilt und der mittlere Schlüssel nach links 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

Für den Löschvorgang gelten mehr Regeln als für Einfüge- und Suchvorgänge.

Es gilt folgender Algorithmus:

• Führen Sie die Suchoperation aus und finden Sie den Zielschlüssel in den Knoten
• Drei Bedingungen gelten je nach Standort des Zielschlüssels, wie in den folgenden Abschnitten erläutert

Wenn sich der Zielschlüssel im Blattknoten befindet

• 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 Zielknoten übertragen und der Zielwert wird entfernt
• 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
• Der Zielschlüssel wird durch das Minimum eines übergeordneten Knotens ersetzt

Wenn sich der Zielschlüssel in einem internen Knoten befindet

• 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
• Wenn der In-Order-Vorgänger des Zielschlüssels mehr als die Min-Schlüssel hat, kann er nur dann den Zielschlüssel durch den Max-Wert des In-Order-Vorgängers ersetzen
• Wenn der In-Order-Vorgänger des Zielschlüssels nicht mehr als Min-Schlüssel hat, suchen Sie nach dem In-Order-Nachfolger-Mindestschlüssel.
• Wenn sowohl der Vorgänger als auch der Nachfolger des Zielschlüssels in der richtigen Reihenfolge weniger als min. Schlüssel haben, führen Sie den Vorgänger und den Nachfolger zusammen.

Wenn sich der Zielschlüssel in einem Wurzelknoten befindet

• Ersetzen Sie es durch das maximale Element des Vorgänger-Teilbaums in der Reihenfolge
• Wenn das Ziel nach dem Löschen weniger als die minimalen Schlüssel hat, leiht sich der Zielknoten den maximalen Wert von seinem Geschwisterknoten über den übergeordneten Knoten des Geschwisterknotens.
• Der Maximalwert des Elternknotens wird von einem Ziel übernommen, jedoch mit den Knoten des Maximalwerts des Geschwisterknotens.

Lassen Sie uns nun den Löschvorgang anhand eines Beispiels verstehen.

Das obige Diagramm zeigt verschiedene Fälle von Löschvorgängen in einem B-Baum. Dieser B-Baum ist von der Ordnung 5, was bedeutet, dass die Mindestanzahl von untergeordneten Knoten, die ein Knoten haben kann, 3 und die Höchstanzahl von untergeordneten Knoten, die ein Knoten haben kann, 5 beträgt. Die Mindest- und Höchstanzahl von Schlüsseln, die ein Knoten haben kann, beträgt hingegen 2 bzw. 4.

Im obigen Beispiel:

• Der Zielknoten verfügt über den zu löschenden Zielschlüssel
• Der Zielknoten verfügt über mehr Schlüssel als die Mindestschlüssel
• Löschen Sie einfach den Schlüssel

Im obigen Beispiel:

• Der Zielknoten verfügt über Schlüssel, die den Mindestschlüsseln entsprechen, und kann daher nicht direkt gelöscht werden, da dies gegen die Bedingungen verstößt

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

• Der Zielknoten leiht sich einen Schlüssel vom unmittelbaren Geschwisterknoten, 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 Knoten übertragen, und der übergeordnete Knoten überträgt den Maximalwert an den Zielknoten (siehe Abbildung unten).

Das folgende Beispiel veranschaulicht, wie ein Schlüssel gelöscht wird, der einen Wert von seinem in der richtigen Reihenfolge vorhandenen Nachfolger benötigt.

• Der Zielknoten leiht sich einen Schlüssel vom unmittelbaren Geschwisterknoten, in diesem Fall vom Nachfolger in der Reihenfolge (rechter Geschwisterknoten), da sein Vorgänger in der Reihenfolge (linker Geschwisterknoten) Schlüssel hat, die den Mindestschlüsseln entsprechen.
• Der Mindestwert des Nachfolgers in der Reihenfolge wird an den übergeordneten Knoten übertragen, und der übergeordnete Knoten überträgt den maximalen Wert an den Zielknoten.

Im folgenden Beispiel verfügt der Zielknoten über keinen Geschwisterknoten, der seinen Schlüssel an den Zielknoten weitergeben kann. Daher ist eine Zusammenführung erforderlich.

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

• Führen Sie den Zielknoten zusammen mit dem übergeordneten Schlüssel mit einem seiner unmittelbaren Geschwister zusammen
• Der Schlüssel vom übergeordneten Knoten wird ausgewählt, der zwischen den beiden zusammengeführten Knoten liegt
• Löschen Sie den Zielschlüssel aus dem 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
    }
}

Ausgang:

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 Suchoperation des B-Baums ist die einfachste. Sie beginnt immer an der Wurzel und prüft zunächst, ob der Zielschlüssel größer oder kleiner als der Knotenwert ist.
• Der Einfügevorgang des B-Baums ist ziemlich detailliert. Zuerst wird eine geeignete Einfügeposition für den Zielschlüssel gefunden, dieser eingefügt, die Gültigkeit des B-Baums in verschiedenen Fällen bewertet und dann die B-Baum-Knoten entsprechend neu strukturiert.
• Der Löschvorgang des B-Baums sucht zuerst nach dem zu löschenden Zielschlüssel, löscht ihn und bewertet die Gültigkeit basierend auf verschiedenen Fällen wie Mindest- und Höchstschlüssel des Zielknotens, der Geschwister und des übergeordneten Knotens.