B BAUM in der Datenstruktur: Beispiel für Suchen, Einfügen, Löschen

Inhaltsverzeichnis:

Anonim

Was ist ein B-Baum?

B Tree ist eine selbstausgleichende Datenstruktur, die auf einem bestimmten Regelwerk basiert, um die Daten schneller und speichereffizienter zu suchen, einzufügen und zu löschen. Um dies zu erreichen, werden die folgenden Regeln befolgt, um einen B-Baum zu erstellen.

Ein B-Baum ist eine spezielle 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, die sortierten Daten zu erhalten und verschiedene Vorgänge wie Einfügen, Suchen und Löschen in kürzerer Zeit zu ermöglichen.

In diesem B-Tree-Tutorial lernen Sie:

  • Was ist ein B-Baum?
  • Warum B-Tree verwenden?
  • Geschichte von B Tree
  • Suchvorgang
  • Operation einfügen
  • Vorgang löschen

Regeln für B-Tree

Hier finden Sie wichtige Regeln zum Erstellen von B_Tree

  • Alle Blätter werden auf der gleichen Ebene erstellt.
  • B-Tree wird durch eine Anzahl von Graden bestimmt, die auch als "Reihenfolge" (von einem externen Akteur wie einem Programmierer angegeben) bezeichnet wird 
    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 geringere Werte als die rechte Seite des Teilbaums. Dies bedeutet, dass die Knoten auch in aufsteigender Reihenfolge von links nach rechts sortiert sind.
  • Die maximale Anzahl von untergeordneten Knoten, die ein Stammknoten sowie seine untergeordneten Knoten enthalten können, wird nach folgender Formel berechnet: 
    m - 1
    Zum Beispiel: 
    m = 4max keys: 4 - 1 = 3

  • Jeder Knoten außer root muss Mindestschlüssel von enthalten 
    [m/2]-1
    Zum Beispiel: 
    m = 4min keys: 4/2-1 = 1
  • Die maximale Anzahl von untergeordneten Knoten, die ein Knoten haben kann, entspricht seinem Grad 
    m
  • Das Minimum an Kindern, die ein Knoten haben kann, ist die Hälfte der Reihenfolge, die m / 2 ist (der Höchstwert wird 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 auf der Festplatte vorgenommenen Lesevorgänge
  • B Bäume können einfach optimiert werden, um ihre Größe (dh die Anzahl der untergeordneten Knoten) entsprechend der Festplattengröße anzupassen
  • Es ist eine speziell entwickelte Technik für den Umgang mit einer großen Datenmenge.
  • Es ist ein nützlicher Algorithmus für Datenbanken und Dateisysteme.
  • Eine gute Wahl, wenn Sie große Datenblöcke lesen und schreiben möchten

Geschichte von B Tree

  • Daten werden in Blöcken auf der Festplatte gespeichert. Diese Daten werden, wenn sie in den Hauptspeicher (oder RAM) gebracht werden, als Datenstruktur bezeichnet.
  • Bei großen Datenmengen muss zum Durchsuchen eines Datensatzes auf der Festplatte die gesamte Festplatte gelesen werden. Dies erhöht die Zeit und den Hauptspeicherverbrauch aufgrund der hohen Festplattenzugriffsfrequenz und Datengröße.
  • Um dies zu überwinden, werden Indextabellen erstellt, in denen die Datensatzreferenz der Datensätze basierend auf den Blöcken gespeichert wird, in denen sie sich befinden. Dies reduziert den Zeit- und Speicherverbrauch drastisch.
  • Da wir über große Datenmengen verfügen, können wir mehrstufige Indextabellen erstellen.
  • Ein mehrstufiger Index kann mithilfe von B Tree erstellt werden, um die Daten selbstausgleichend zu sortieren.

Suchvorgang

Die Suchoperation ist die einfachste Operation in B Tree.

Der folgende Algorithmus wird angewendet:

  • Lassen Sie den Schlüssel (den Wert) mit "k" durchsuchen.
  • Beginnen Sie mit der Suche von der Wurzel aus und durchlaufen Sie sie rekursiv.
  • Wenn k kleiner als der Wurzelwert ist, suchen Sie den linken Teilbaum. Wenn k größer als der Wurzelwert ist, suchen Sie den rechten Teilbaum.
  • Wenn der Knoten das gefundene k hat, geben Sie einfach den Knoten zurück.
  • Wenn das k nicht im Knoten gefunden wird, fahren Sie mit einem größeren Schlüssel zum Kind hinunter.
  • Wenn k nicht im Baum gefunden wird, geben wir NULL zurück.

Operation einfügen

Da B Tree ein selbstausgleichender Baum ist, können Sie das Einfügen eines Schlüssels in keinen beliebigen Knoten erzwingen.

Der folgende Algorithmus gilt:

  • Führen Sie den Suchvorgang aus und suchen Sie den geeigneten Einfügeplatz.
  • Fügen Sie den neuen Schlüssel an der richtigen Stelle ein, aber wenn der Knoten bereits eine maximale Anzahl von Schlüsseln hat:
  • 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 beiden anderen untergeordneten Knoten.
  • Die Knoten müssen die Schlüssel in aufsteigender Reihenfolge neu anordnen.

TRINKGELD

Folgendes gilt nicht für den Einfügealgorithmus:

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 suchen Sie nach Regeln
  • Hat der Knoten nach dem Einfügen mehr als eine Mindestanzahl von Schlüsseln, die 1 ist? In diesem Fall ja. Überprüfen Sie die nächste Regel.
  • Hat der Knoten nach dem Einfügen mehr als eine maximale Anzahl von Schlüsseln, nämlich 3? In diesem Fall nein, das tut es nicht. Dies bedeutet, dass der B-Baum keine Regeln verletzt und das Einfügen abgeschlossen ist.

Im obigen Beispiel:

  • Der Knoten hat die maximale Anzahl von Schlüsseln erreicht
  • Der Knoten wird geteilt und der mittlere Schlüssel wird zum Wurzelknoten der restlichen zwei Knoten.
  • Bei einer geraden Anzahl von Schlüsseln wird der mittlere Knoten durch linke oder rechte Vorspannung ausgewählt.

Im obigen Beispiel:

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

In ähnlicher Weise können 13 und 2 leicht in den Knoten eingefügt werden, da sie weniger als die maximale Schlüsselregel für die Knoten erfüllen.

Im obigen Beispiel:

  • Der Knoten verfügt über Schlüssel, die den maximalen Schlüsseln entsprechen.
  • Der Schlüssel wird in den Zielknoten eingefügt, verstößt jedoch gegen die Regel der maximalen Schlüssel.
  • Der Zielknoten ist geteilt, und der mittlere Schlüssel nach links ist jetzt das übergeordnete Element der neuen untergeordneten Knoten.
  • Die neuen Knoten sind in aufsteigender Reihenfolge angeordnet.

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

Vorgang löschen

Der Löschvorgang enthält mehr Regeln als Einfüge- und Suchvorgänge.

Der folgende Algorithmus gilt:

  • Führen Sie die Suchoperation aus und suchen Sie den Zielschlüssel in den Knoten
  • Drei Bedingungen gelten basierend auf der Position des Zielschlüssels, wie in den folgenden Abschnitten erläutert

Wenn sich der Zielschlüssel im Blattknoten befindet

  • Ziel ist im Blattknoten mehr als min Schlüssel.
    • Wenn Sie dies löschen, wird die Eigenschaft von B Tree nicht verletzt
  • Das Ziel befindet sich im Blattknoten und hat mindestens Schlüsselknoten
    • Wenn Sie dies löschen, wird die Eigenschaft von B Tree verletzt
    • Der Zielknoten kann den Schlüssel vom unmittelbaren linken Knoten oder vom unmittelbaren rechten Knoten (Geschwister) ausleihen.
    • Das Geschwister sagt ja, wenn es mehr als die Mindestanzahl von 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 keine Geschwister haben mehr als die Mindestanzahl von Schlüsseln
    • Suche nach Schlüssel
    • 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 den Vorgänger in der Reihenfolge oder den Nachfolger in der Reihenfolge
  • Bei Vorgängern in der richtigen Reihenfolge wird der maximale Schlüssel aus dem linken Teilbaum ausgewählt
  • Im Falle eines In-Order-Nachfolgers wird der Mindestschlüssel aus dem rechten Teilbaum ausgewählt
  • Wenn der Vorgänger des Zielschlüssels in der Reihenfolge mehr als die Min-Schlüssel hat, kann er nur dann den Zielschlüssel durch das Maximum des Vorgängers in der Reihenfolge ersetzen
  • Wenn der Vorgänger des Zielschlüssels in der Reihenfolge nicht mehr als Min. Schlüssel hat, suchen Sie nach dem Mindestschlüssel des Nachfolgers in der Reihenfolge.
  • Wenn der Vorgänger und der Nachfolger des Zielschlüssels weniger als min Schlüssel haben, führen Sie den Vorgänger und den Nachfolger zusammen.

Wenn sich der Zielschlüssel in einem Stammknoten befindet

  • Ersetzen Sie durch das maximale Element des Vorgänger-Teilbaums in der Reihenfolge
  • Wenn das Ziel nach dem Löschen weniger als min Schlüssel hat, leiht der Zielknoten den Maximalwert von seinem Geschwister über das übergeordnete Element des Geschwisters aus.
  • Der Maximalwert des übergeordneten Elements wird von einem Ziel übernommen, jedoch mit den Knoten des Maximalwerts des Geschwisters.

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 hat die Ordnung 5, was bedeutet, dass die minimale Anzahl von untergeordneten Knoten, die ein Knoten haben kann, 3 ist und die maximale Anzahl von untergeordneten Knoten, die jeder Knoten haben kann, 5 ist. Während die minimale und maximale Anzahl von Schlüsseln jeder Knoten ist können haben sind 2 bzw. 4.

Im obigen Beispiel:

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

Im obigen Beispiel:

  • Der Zielknoten verfügt über Schlüssel, die den Mindestschlüsseln entsprechen. Daher kann er nicht direkt gelöscht werden, da dies die Bedingungen verletzt

In der folgenden Abbildung wird nun erläutert, wie Sie diesen Schlüssel löschen:

  • Der Zielknoten leiht einen Schlüssel vom unmittelbaren Geschwister aus, in diesem Fall vom Vorgänger in der Reihenfolge (linkes Geschwister), da er keinen Nachfolger in der Reihenfolge (rechtes Geschwister) hat.
  • Der Maximalwert des Inorder-Vorgängers wird an das übergeordnete Element übertragen, und das übergeordnete Element überträgt den Maximalwert an den Zielknoten (siehe Abbildung unten).

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

  • Der Zielknoten leiht einen Schlüssel vom unmittelbaren Geschwister aus, in diesem Fall vom Nachfolger in der Reihenfolge (rechtes Geschwister), da sein Vorgänger in der Reihenfolge (linkes Geschwister) Schlüssel hat, die den Mindestschlüsseln entsprechen.
  • Der minimale Wert des In-Order-Nachfolgers wird an das übergeordnete Element übertragen, und das übergeordnete Element überträgt den maximalen Wert an den Zielknoten.

Im folgenden Beispiel hat der Zielknoten kein Geschwister, das dem Zielknoten seinen Schlüssel geben kann. Daher ist eine Zusammenführung erforderlich.

Siehe das Verfahren zum Löschen eines solchen Schlüssels:

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

Operation Pseudo Code löschen

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

Ausgabe :

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

Zusammenfassung:

  • B Tree ist eine selbstausgleichende Datenstruktur zum besseren Suchen, Einfügen und Löschen von Daten von der Festplatte.
  • B Baum wird durch den angegebenen Grad reguliert
  • B Baumschlüssel und Knoten sind in aufsteigender Reihenfolge angeordnet.
  • Die Suchoperation von B Tree ist die einfachste, die immer von der Wurzel ausgeht und prüft, ob der Zielschlüssel größer oder kleiner als der Knotenwert ist.
  • Die Einfügeoperation von B Tree ist ziemlich detailliert. Dabei wird zunächst eine geeignete Einfügeposition für den Zielschlüssel gefunden, eingefügt, die Gültigkeit von B Tree anhand verschiedener Fälle bewertet und anschließend die B Tree-Knoten entsprechend umstrukturiert.
  • Der Löschvorgang von B Tree sucht zuerst nach dem zu löschenden Zielschlüssel, löscht ihn und bewertet die Gültigkeit anhand mehrerer Fälle wie Minimal- und Maximalschlüssel des Zielknotens, der Geschwister und des übergeordneten Schlüssels.