B TREE in der Datenstruktur: Beispiel für einen Such-, Einfüge- und Löschvorgang

Was ist ein B-Baum?

B Baum ist eine selbstausgleichende Datenstruktur, die auf einem bestimmten Regelsatz für sich selbst basiertarching, Einfügen und Löschen der Daten auf eine schnellere und speichereffizientere Weise. Um dies zu erreichen, ist Folgendes erforderlichwing Es werden Regeln befolgt, um einen B-Baum zu erstellen.

Ein B-Baum ist eine besondere Art von Baum in einer Datenstruktur. 1972 wurde diese Methode erstmals von McCreight eingeführt und Bayer nannte sie Height Balanced m-way Search Tree. Es hilft Ihnen, Daten sortiert aufzubewahren und verschiedene Vorgänge wie Einfügen usw. zu ermöglichenarching und Löschung in kürzerer Zeit.

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
    

Regeln für B-Baum

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

Suchvorgang

Der Suchvorgang ist der einfachste Vorgang im 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.

Vorgang einfügen

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 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 Die folgendenwing trifft nicht zu auf den Einfügungsalgorithmus:

Da der Knoten voll ist, wird er geteilt und dann wird ein neuer Wert eingefügt

Vorgang einfügen

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.

Vorgang einfügen

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.

Vorgang einfügen

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.

Vorgang einfügen

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.

Vorgang einfügen

Vorgang löschen

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

Die folgendenwing Algorithmus gilt:

  • Führen Sie den Suchvorgang aus und suchen Sie den Zielschlüssel in den Knoten
  • Basierend auf der Position des Zielschlüssels galten drei Bedingungen, wie im Folgenden erläutertwing Abschnitte

Wenn sich der Zielschlüssel im Blattknoten befindet

  • Das Ziel befindet sich im Blattknoten, mehr als die Mindestschlüsselzahl.
  • Durch das Löschen wird das Eigentum von B Tree nicht verletzt
  • Das Ziel befindet sich im Blattknoten und verfügt über minimale Schlüsselknoten
  • Durch das Löschen wird das Eigentum von B Tree verletzt
  • Der Zielknoten kann den Schlüssel vom unmittelbar linken Knoten oder vom unmittelbar rechten Knoten (Geschwister) 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
  • Das Ziel befindet sich im Blattknoten, aber kein Geschwisterknoten 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.

Vorgang löschen

Das obige Diagramm zeigt verschiedene Fälle von Löschvorgängen 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.

Vorgang löschen

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

Vorgang löschen

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

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

Vorgang löschen

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

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

Vorgang löschen

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

Vorgang löschen

  • 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

Vorgangspseudocode löschen

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 Suchoperation von B Tree ist die einfachste. Sie beginnt immer bei der Wurzel und prüft, ob der Zielschlüssel größer oder kleiner als der Knotenwert ist.
  • Die Einfügeoperation von B Tree ist ziemlich detailliert. Sie findet zunächst eine geeignete Einfügeposition für den Zielschlüssel, fügt ihn ein, bewertet die Gültigkeit von B Tree anhand verschiedener Fälle und strukturiert dann die B Tree-Knoten entsprechend um.
  • Der Löschvorgang von B Tree sucht zunächst nach dem zu löschenden Zielschlüssel, löscht ihn und bewertet die Gültigkeit basierend auf mehreren Fällen wie minimalen und maximalen Schlüsseln des Zielknotens, der Geschwister und des übergeordneten Knotens.