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

Was ist ein B-Baum?

B Baum Ein B-Baum ist eine selbstbalancierende Datenstruktur, die auf spezifischen Regeln für das schnelle und speichereffiziente Suchen, Einfügen und Löschen von Daten basiert. Um dies zu erreichen, werden beim Erstellen eines B-Baums die folgenden Regeln befolgt.

Ein B-Baum ist eine spezielle Art von Baum in einer Datenstruktur. 1972 wurde diese Methode erstmals von McCreight und Bayer vorgestellt, die sie als höhenbalancierten m-Wege-Suchbaum bezeichneten. Er hilft dabei, sortierte Daten zu erhalten und ermöglicht verschiedene Operationen wie Einfügen, Suchen und Löschen in kürzerer Zeit.

Regeln für B-Baum

Hier sind wichtige Regeln für die Erstellung eines B-Baums:

• Alle Blätter werden auf der gleichen Ebene erstellt.
• Ein B-Baum wird durch eine Anzahl von Knotengraden, auch „Ordnung“ genannt (festgelegt von einem externen Akteur, z. B. einem Programmierer), bestimmt. 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 Schlüsseln, die ein Wurzelknoten sowie seine Kindknoten enthalten können, wird mit dieser Formel berechnet: m − 1. Zum Beispiel:

  m = 4
  max keys: 4 − 1 = 3

• Jeder Knoten, außer dem Wurzelknoten, muss eine Mindestanzahl an Schlüsseln enthalten. [m/2] − 1. Zum Beispiel:

  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 eines B-Baums:

• Verringert die Anzahl der Lesevorgänge auf der Festplatte.
• B-Bäume lassen sich leicht optimieren, um ihre Größe (d. h. die Anzahl der Kindknoten) an die 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 Datenmengen geht.

Geschichte von B Tree

• Daten werden auf der Festplatte in Blöcken gespeichert. Werden diese Daten in den Hauptspeicher (RAM) geladen, nennt man sie Datenstruktur.
• Bei sehr großen Datenmengen erfordert die Suche nach einem einzelnen Datensatz auf der Festplatte das Lesen der gesamten Festplatte; dies erhöht die Zugriffszeit und den Hauptspeicherverbrauch aufgrund der hohen Zugriffshäufigkeit und der großen Datenmenge.
• Um dies zu beheben, werden Indextabellen erstellt, die die Datensatzreferenz der Datensätze anhand der Blöcke speichern, in denen sie sich befinden. Dies reduziert den Zeit- und Speicherverbrauch drastisch.
• Da wir über riesige Datenmengen verfügen, können wir mehrstufige Indextabellen erstellen.
• Ein mehrstufiger Index kann mithilfe eines B-Baums für die Schlüsselstruktur entworfen werden.ping Die Daten sortierten sich selbstausgleichend.

Suche OperaProduktion

Die Suchoperation ist die einfachste Operation auf einem B-Baum. Folgender Algorithmus wird angewendet:

• Der zu suchende Schlüssel (Wert) sei „k“.
• Beginnen Sie mit der Suche an der Wurzel und durchlaufen Sie sie rekursiv nach unten.
• Ist k kleiner als der Wurzelwert, durchsuche den linken Teilbaum; ist k größer als der Wurzelwert, durchsuche 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 ein B-Baum ein selbstbalancierender Baum ist, kann man nicht in jeden beliebigen Knoten einen Schlüssel einfügen. Folgender Algorithmus kommt zum Einsatz:

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

Im obigen Beispiel:

• Suchen Sie im Knoten an der entsprechenden Position nach dem Schlüssel.
• Fügen Sie den Schlüssel im Zielknoten ein und prüfen Sie, ob Regeln vorhanden sind.
• Besitzt der Knoten nach dem Einfügen mindestens die Mindestanzahl an Schlüsseln (1)? In diesem Fall ja. Prüfen Sie die nächste Regel.
• Besitzt der Knoten nach dem Einfügen mehr als die maximale Anzahl an Schlüsseln (3)? In diesem Fall nein. Das bedeutet, dass der B-Baum keine Regeln verletzt und das Einfügen abgeschlossen ist.

Im obigen Beispiel:

• Der Knoten hat die maximale Anzahl an Schlüsseln erreicht.
• Der Knoten wird sich teilen, und der mittlere Schlüssel wird zum Wurzelknoten der beiden verbleibenden Knoten.
• Bei einer geraden Anzahl von Schlüsseln wird der mittlere Knoten durch Linksbias oder Rechtsbias ausgewählt.

Im obigen Beispiel:

• Der Knoten hat weniger als die maximale Anzahl an Schlüsseln.
• Die 1 wird neben die 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 „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 zwar in den Zielknoten eingefügt, verstößt aber 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

Der Löschvorgang hat mehr Regeln als die Einfüge- und Suchvorgänge. Folgender Algorithmus kommt zum Einsatz:

• Führe die Suchoperation durch und finde den Zielschlüssel in den Knoten.
• Je nach Position des Zielschlüssels werden drei Bedingungen angewendet, wie in den folgenden Abschnitten erläutert wird.

Wenn sich der Zielschlüssel im Blattknoten befindet

• Target Befindet sich im Blattknoten und hat mehr als die minimale Anzahl an Schlüsseln. Das Löschen dieses Elements verletzt keine Eigenschaft des B-Baums.
• Target Es befindet sich im Blattknoten und hat die minimale Anzahl an Schlüsselknoten. Das Löschen dieses Knotens würde eine Eigenschaft des B-Baums verletzen.
• Der Zielknoten kann sich einen Schlüssel vom unmittelbar links liegenden Knoten oder vom unmittelbar rechts liegenden 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 den übergeordneten Knoten übertragen, der Maximalwert des übergeordneten Knotens wird an den Zielknoten übertragen und der Zielwert wird entfernt.
• Target Befindet sich der Schlüssel im Blattknoten, aber kein Geschwisterknoten hat mehr als die Mindestanzahl an Schlüsseln: Suche nach dem Schlüssel, führe ihn mit Geschwisterknoten und dem Minimum der Elternknoten zusammen, die Gesamtzahl der Schlüssel ist nun größer als das Minimum, und der Zielschlüssel wird durch das Minimum eines Elternknotens ersetzt.

Wenn sich der Zielschlüssel in einem internen Knoten befindet

• Entweder man wählt einen Vorgänger oder einen Nachfolger in der Reihenfolge.
• Im Falle eines in-order Vorgängers wird der maximale Schlüssel aus seinem linken Teilbaum ausgewählt.
• Im Falle eines In-Order-Nachfolgers wird der minimale Schlüssel aus seinem rechten Teilbaum ausgewählt.
• Nur wenn der Vorgänger des Zielschlüssels mehr als die Mindestanzahl an Schlüsseln hat, kann er den Zielschlüssel durch den größten Vorgänger ersetzen.
• Wenn der Vorgänger des Zielschlüssels in der Reihenfolge nicht mehr als min Schlüssel hat, suche nach dem minimalen Schlüssel des Nachfolgers in der Reihenfolge.
• 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 dies durch das größte Element des Vorgänger-Teilbaums in der richtigen Reihenfolge.
• Wenn der Zielknoten nach dem Löschen weniger als min Schlüssel hat, leiht sich der Zielknoten den Maximalwert von seinem Geschwisterknoten über dessen Elternknoten.
• Der Maximalwert des übergeordneten Elements wird vom Zielelement übernommen, wobei die Knoten den Maximalwert des Geschwisterelements aufweisen.

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

Das obige Diagramm zeigt verschiedene Fälle der Löschoperation in einem B-Baum. Dieser B-Baum ist von Ordnung 5, was bedeutet, dass ein Knoten mindestens 3 und maximal 5 Kindknoten haben kann. Die minimale und maximale Anzahl an Schlüsseln, die ein Knoten haben kann, beträgt hingegen 2 bzw. 4.

Im obigen Beispiel:

• Der Zielknoten enthält den zu löschenden Zielschlüssel.
• Der Zielknoten besitzt mehr Schlüssel als die Mindestanzahl an Schlüsseln.
• Löschen Sie einfach den Schlüssel.

Im obigen Beispiel:

• Der Zielknoten hat Schlüssel, die der Mindestanzahl an Schlüsseln entsprechen, daher können wir ihn nicht direkt löschen, da dies gegen die Bedingungen verstoßen würde.

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

• Der Zielknoten leiht sich einen Schlüssel von einem 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 Vorgängerknotens in der Reihenfolge wird an den Elternknoten übertragen, und der Elternknoten überträgt den Maximalwert an den Zielknoten (siehe das unten stehende Diagramm).

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 von einem unmittelbaren Geschwisterknoten, in diesem Fall vom Nachfolger in der Reihenfolge (rechter Geschwisterknoten), weil sein Vorgänger in der Reihenfolge (linker Geschwisterknoten) Schlüssel besitzt, die den minimalen Schlü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 hat der Zielknoten keinen Geschwisterknoten, der seinen Schlüssel an den Zielknoten weitergeben kann. Daher ist ein Zusammenführen erforderlich. Siehe die Vorgehensweise zum Löschen eines solchen Schlüssels:

• Verschmelze den Zielknoten mit einem seiner direkten Geschwisterknoten unter Verwendung des übergeordneten Schlüssels.
• Der Schlüssel des übergeordneten Knotens, der sich zwischen den beiden zusammenführenden Knoten befindet, wird ausgewählt.
• Löschen Sie den Zielschlüssel aus dem zusammengeführten Knoten.

Löschen Operation Pseudo Code

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.

Häufig gestellte Fragen