TechCodeview

Im folgenden Tutorial lernen wir die B-Tree-Datenstruktur kennen und überlegen, sie zu visualisieren.

Also lasst uns anfangen.

Was ist ein B-Baum?

Der B Baum ist ein spezielle Art von Mehrweg-Suchbaum , allgemein bekannt als M-Weg Baum, der sich selbst ausbalanciert. Aufgrund ihrer ausgewogenen Struktur werden diese Bäume häufig zum Betreiben und Verwalten riesiger Datenbanken und zur Vereinfachung von Suchvorgängen verwendet. In einem B-Baum kann jeder Knoten höchstens n untergeordnete Knoten haben. B Tree ist ein Beispiel für die mehrstufige Indizierung in einem Datenbankverwaltungssystem (DBMS). Blatt- und interne Knoten verfügen beide über Datensatzreferenzen. Der B-Baum wird als Balanced Stored Tree bezeichnet, da sich alle Blattknoten auf derselben Ebene befinden.

Das folgende Diagramm ist ein Beispiel für einen B-Baum:

Abbildung 1. A B Baum mit Ordnung 3

Die Regeln des B-Baums verstehen

Im Folgenden sind die wichtigen Eigenschaften eines B-Baums aufgeführt:

1. Alle Blattknoten liegen auf der gleichen Ebene.
2. Die B-Baum-Datenstruktur wird durch den Begriff Mindestgrad „d“ definiert. Der Wert von „d“ hängt von der Größe des Plattenblocks ab.
3. Jeder Knoten, mit Ausnahme der Wurzel, muss aus mindestens d-1 Schlüsseln bestehen. Der Wurzelknoten darf aus mindestens 1 Schlüssel bestehen.
4. Alle Knoten (einschließlich des Wurzelknotens) dürfen höchstens aus bestehen (2d-1) Schlüssel.
5. Die Anzahl der Kinder eines Knotens ist gleich Addition der Anzahl der darin vorhandenen Schlüssel und .
6. Alle Schlüssel eines Knotens werden in aufsteigender Reihenfolge sortiert. Das Kind zwischen zwei Schlüsseln, k1 und k2, besteht aus allen Schlüsseln, die jeweils zwischen k1 und k2 liegen.
7. Im Gegensatz zum binären Suchbaum wächst und schrumpft die Datenstruktur des B-Baums von der Wurzel aus. Während der binäre Suchbaum nach unten wächst und nach unten schrumpft.
8. Ähnlich wie bei anderen selbstbalancierten binären Suchbäumen ist die zeitliche Komplexität der B-Baum-Datenstruktur für Vorgänge wie Suchen, Einfügen und Löschen gleich O(log?n) .
9. Das Einfügen eines Knotens in den B-Baum erfolgt nur am Blattknoten.

Betrachten wir das folgende Beispiel eines B-Baums mit der Mindestordnung 5.

Figur 2. A B Baum der Ordnung 5

Hinweis: Der Wert der Mindestbestellmenge beträgt in einem praktischen B-Bäume viel mehr als 5.

Im obigen Diagramm können wir beobachten, dass sich alle Blattknoten auf derselben Ebene befinden und alle Nicht-Blattknoten keinen leeren Teilbaum haben und aus Schlüsseln bestehen, die um eins kleiner sind als die Anzahl ihrer untergeordneten Knoten.

Die festgelegte Formulierung der B-Baum-Regeln:

Jeder B-Baum hängt von einer positiven konstanten ganzen Zahl ab, die als bekannt ist MINIMUM , die verwendet wird, um die Anzahl der Datenelemente zu bestimmen, die in einem einzelnen Knoten gespeichert werden können.

Regel 1: Die Wurzel kann nur ein Datenelement haben (oder sogar keine Datenelemente, wenn sie auch keine untergeordneten Elemente hat); Jeder andere Knoten hat mindestens MINIMUM Datenelemente.

Regel 2: Die maximale Anzahl der in einem Knoten gespeicherten Datenelemente beträgt das Doppelte des Wertes von MINIMUM .

Regel 3: Die Datenelemente jedes Knotens des B-Baums werden in einem teilweise gefüllten Array gespeichert, sortiert vom kleinsten Datenelement (bei Index). 0 ) bis zum größten Datenelement (an der endgültig genutzten Position des Arrays).

Regel 4: Die Gesamtzahl der Teilbäume unterhalb eines Nicht-Blattknotens ist immer um eins größer als die Anzahl der Datenelemente in diesem Knoten.

• Teilbaum 0, Teilbaum 1,...

Regel 5: In Bezug auf jeden Nicht-Blattknoten:

1. Ein Datenelement am Index ist größer als alle Datenelemente in der Teilbaumnummer ich des Knotens und
2. Ein Datenelement am Index ist kleiner als alle Datenelemente in der Teilbaumnummer i+1 des Knotens.

Regel 6: Jedes Blatt in einem B-Baum hat die gleiche Tiefe. Dadurch wird sichergestellt, dass ein B-Baum das Problem eines unausgeglichenen Baums verhindert.

Operationen an einer B-Baum-Datenstruktur

Um sicherzustellen, dass keine der Eigenschaften einer B-Baum-Datenstruktur während der Operationen verletzt wird, kann der B-Baum geteilt oder verbunden werden. Im Folgenden sind einige Operationen aufgeführt, die wir an einem B-Baum ausführen können:

1. Durchsuchen eines Datenelements im B-Baum
2. Einfügen eines Datenelements in den B-Baum
3. Löschen eines Datenelements im B-Baum

Suchvorgang für einen B-Baum

Die Suche nach einem Element in einem B-Baum ähnelt der in einem binären Suchbaum. Aber anstatt wie ein binärer Suchbaum eine Zwei-Wege-Entscheidung (Links oder Rechts) zu treffen, trifft ein B-Baum an jedem Knoten eine M-Wege-Entscheidung, wobei m die Anzahl der Kinder des Knotens ist.

Schritte zum Suchen eines Datenelements in einem B-Baum:

Schritt 1: Die Suche beginnt am Wurzelknoten. Vergleichen Sie das Suchelement k mit der Wurzel.

Schritt 1.1: Wenn der Wurzelknoten aus dem Element k besteht, ist die Suche abgeschlossen.

Schritt 1.2: Wenn das Element k kleiner als der erste Wert in der Wurzel ist, gehen wir zum untergeordneten Element ganz links und suchen das untergeordnete Element rekursiv.

Schritt 1.3.1: Wenn die Wurzel nur zwei untergeordnete Knoten hat, gehen wir zum untergeordneten Knoten ganz rechts und durchsuchen die untergeordneten Knoten rekursiv.

Schritt 1.3.2: Wenn die Wurzel mehr als zwei Schlüssel hat, werden wir den Rest durchsuchen.

Schritt 2: Wenn das Element k nach dem Durchlaufen des gesamten Baums nicht gefunden wird, ist das Suchelement im B-Baum nicht vorhanden.

Lassen Sie uns die oben genannten Schritte anhand eines Beispiels veranschaulichen. Angenommen, wir wollten im folgenden B-Baum nach einem Schlüssel k=34 suchen:

Abbildung 3.1. Ein gegebener B-Baum

1. Zunächst prüfen wir, ob der Schlüssel vorhanden ist k = 34 befindet sich am Wurzelknoten. Da sich der Schlüssel nicht im Stamm befindet, gehen wir zu seinen untergeordneten Knoten über. Wir können auch beobachten, dass der Wurzelknoten zwei untergeordnete Knoten hat; Daher vergleichen wir den erforderlichen Wert zwischen den beiden Schlüsseln.
   
   Abbildung 3.2. Der Schlüssel k ist im Root nicht vorhanden
2. Da wir nun feststellen können, dass der Schlüssel k größer als der Wurzelknoten ist, also 30, fahren wir mit dem rechten Kind der Wurzel fort.
   
   Abbildung 3.3. Der Schlüssel k > 30, zum rechten Kind wechseln
3. Wir vergleichen nun den Schlüssel k mit den auf dem Knoten vorhandenen Werten, also 40 bzw. 50. Da der Schlüssel k kleiner als der linke Schlüssel ist, also 40, bewegen wir uns zum linken Kind des Knotens.
   
   Abbildung 3.4. Der Schlüssel k<40, move to left child< li>
4. Da der Wert im linken untergeordneten Element von 40 34 ist, was der erforderliche Wert ist, können wir daraus schließen, dass der Schlüssel gefunden wurde und der Suchvorgang abgeschlossen ist.
   
   Abbildung 3.4. Der Schlüssel k = 34, das linke Kind von 40

Wir haben den Schlüssel im obigen Beispiel mit vier verschiedenen Werten verglichen, bis wir ihn gefunden haben. Somit beträgt die zeitliche Komplexität, die für die Suchoperation in einem B-Baum erforderlich ist O(log?n) .

Einfügen einer Operation in einen B-Baum

Beim Einfügen eines Datenelements in einen B-Baum müssen wir zunächst prüfen, ob dieses Element bereits im Baum vorhanden ist oder nicht. Wenn das Datenelement im B-Baum gefunden wird, wird der Einfügevorgang nicht ausgeführt. Sollte dies jedoch nicht der Fall sein, werden wir mit der Einfügung fortfahren. Beim Einfügen eines Elements in den Blattknoten müssen zwei Szenarien beachtet werden:

Der Knoten besteht nicht aus mehr als der MAXIMALEN Anzahl an Schlüsseln –Wir werden den Schlüssel an der richtigen Stelle in den Knoten einfügen.Ein Knoten besteht aus einer MAXIMALEN Anzahl von Schlüsseln –Wir fügen den Schlüssel zum vollständigen Knoten ein und dann findet eine Teilungsoperation statt, bei der der vollständige Knoten in drei Teile geteilt wird. Der zweite oder mittlere Schlüssel wird zum übergeordneten Knoten verschoben, und der erste und der dritte Teil fungieren jeweils als linker und rechter untergeordneter Knoten. Dieser Vorgang wird mit dem übergeordneten Knoten wiederholt, wenn dieser ebenfalls aus einer MAXIMALEN Anzahl von Schlüsseln besteht.

Schritte zum Einfügen eines Datenelements in einen B-Baum:

Schritt 1: Wir beginnen mit der Berechnung der maximalen Anzahl von Schlüsseln im Knoten auf der Grundlage der Reihenfolge des B-Baums.

Schritt 2: Wenn der Baum leer ist, wird ein Wurzelknoten zugewiesen und wir fügen den Schlüssel ein, der als Wurzelknoten fungiert.

Schritt 3: Wir suchen nun nach dem entsprechenden Knoten zum Einfügen.

Schritt 4: Wenn der Knoten voll ist:

Schritt 4.1: Wir werden die Datenelemente in aufsteigender Reihenfolge einfügen.

Schritt 4.2: Wenn die Datenelemente größer als die maximale Anzahl von Schlüsseln sind, teilen wir den vollständigen Knoten am Median auf.

Schritt 4.3: Wir werden die mittlere Taste nach oben schieben und die linke und rechte Taste als linkes und rechtes untergeordnetes Element aufteilen.

Schritt 5: Wenn der Knoten nicht voll ist, fügen wir ihn in aufsteigender Reihenfolge ein.

Lassen Sie uns die oben genannten Schritte anhand eines Beispiels veranschaulichen. Angenommen, wir müssen einen B-Baum der Ordnung 4 erstellen. Die Datenelemente, die in den B-Baum eingefügt werden müssen, sind 5,3,21,11,1,16,8,13,4 und 9 .

1. Da m gleich 3 ist, ist dies die maximale Anzahl von Schlüsseln für einen Knoten = m-1 = 3-1 = 2 .
2. Wir beginnen mit dem Einfügen 5 im leeren Baum.
   
   Abbildung 4.1. Einfügen 5
3. Wir werden nun 3 in den Baum einfügen. Da 3 kleiner als 5 ist, fügen wir 3 links von 5 in denselben Knoten ein.
   
   Abbildung 4.2. Einfügen 3
4. Wir fügen nun 21 in den Baum ein, und da 21 größer als 5 ist, wird es rechts von 5 im selben Knoten eingefügt. Da wir jedoch wissen, dass die maximale Anzahl von Schlüsseln im Knoten 2 beträgt, wird einer dieser Schlüssel auf einen Knoten darüber verschoben, um ihn aufzuteilen. Somit wird 5, das mittlere Datenelement, nach oben verschoben, und 3 und 21 werden zu dessen linken bzw. rechten Knoten.
   
   Abbildung 4.3. Einfügen 21
5. Jetzt ist es an der Zeit, das nächste Datenelement einzufügen, nämlich 11, das größer als 5, aber kleiner als 21 ist. Daher wird 11 als Schlüssel auf der linken Seite des Knotens eingefügt, der aus 21 als Schlüssel besteht.
   
   Abbildung 4.4. Einfügen 11
6. In ähnlicher Weise werden wir das nächste Datenelement 1 in den Baum einfügen, und wie wir beobachten können, ist 1 kleiner als 3; Daher wird es als Schlüssel auf der linken Seite des Knotens eingefügt, der aus 3 als Schlüssel besteht.
   
   Abbildung 4.5. Einfügen 1
7. Jetzt fügen wir das Datenelement 16 in den Baum ein, das größer als 11, aber kleiner als 21 ist. Allerdings übersteigt die Anzahl der Schlüssel in diesem Knoten die maximale Anzahl der Schlüssel. Daher wird der Knoten geteilt und der mittlere Schlüssel zur Wurzel verschoben. Daher wird 16 rechts von 5 eingefügt, wodurch 11 und 21 in zwei separate Knoten aufgeteilt werden.
   
   Abbildung 4.6. Einfügen 16
8. Das Datenelement 8 wird als Schlüssel links von 11 eingefügt.
   
   Abbildung 4.7. Einfügen 8
9. Wir werden 13 in den Baum einfügen, was kleiner als 16 und größer als 11 ist. Daher sollte das Datenelement 13 rechts vom Knoten bestehend aus 8 und 11 eingefügt werden. Da jedoch die maximale Anzahl von Schlüsseln im Baum möglich ist Wenn der Wert nur 2 ist, erfolgt eine Aufteilung, bei der das mittlere Datenelement 11 zum obigen Knoten und 8 und 13 in zwei separate Knoten verschoben wird. Nun besteht der obige Knoten aus 5, 11 und 16, was wiederum die maximale Schlüsselanzahl überschreitet. Daher wird es eine weitere Aufteilung geben, wodurch das Datenelement 11 zum Wurzelknoten mit 5 und 16 als seinen untergeordneten Knoten wird.
   
   Abbildung 4.8. Einfügen 13
10. Da das Datenelement 4 kleiner als 5, aber größer als 3 ist, wird es rechts vom Knoten bestehend aus 1 und 3 eingefügt, wodurch die maximale Anzahl der Schlüssel in einem Knoten erneut überschritten wird. Daher kommt es erneut zu einem Überlauf, der die 3 zum oberen Knoten neben 5 verschiebt.
    
    Abbildung 4.9. Einfügen 4
11. Zuletzt wird das Datenelement 9, das größer als 8, aber kleiner als 11 ist, rechts vom Knoten bestehend aus 8 als Schlüssel eingefügt.
    
    Abbildung 4.10. Einfügen 9

Im obigen Beispiel haben wir verschiedene Vergleiche durchgeführt. Der erste Wert wurde direkt in den Baum eingefügt; Danach musste jeder Wert mit den in diesem Baum verfügbaren Knoten verglichen werden. Die zeitliche Komplexität für den Einfügevorgang in einem B-Baum hängt von der Anzahl der Knoten und ab.

Löschvorgang für einen B-Baum

Das Löschen eines Datenelements in einem B-Baum umfasst drei Hauptereignisse:

1. Durchsuchen des Knotens, in dem der zu löschende Schlüssel vorhanden ist,
2. Löschen des Schlüssels und

• Bei Bedarf den Baum ausbalancieren.

Beim Löschen eines Elements aus der Baumstruktur kann ein Zustand auftreten, der als Unterlauf bezeichnet wird. Ein Unterlauf tritt auf, wenn ein Knoten aus weniger als der Mindestanzahl an Schlüsseln besteht. es sollte halten.

Im Folgenden sind einige Begriffe aufgeführt, die verstanden werden müssen, bevor Sie sich den Lösch-/Entfernungsvorgang vorstellen können:

In der Reihenfolge Vorgänger:Der bedeutendste Schlüssel auf dem linken untergeordneten Knoten eines Knotens wird als dessen Vorgänger in der Reihenfolge bezeichnet.Ordnungsgemäßer Nachfolger:Der Mollschlüssel auf dem rechten untergeordneten Knoten eines Knotens wird als sein Nachfolger in der Reihenfolge bezeichnet.

Im Folgenden sind drei prominente Fälle des Löschvorgangs in einem B-Baum aufgeführt:

Fall 1: Das Löschen/Entfernen des Schlüssels liegt im Leaf-Knoten - Dieser Fall wird weiter in zwei verschiedene Fälle unterteilt:

1. Das Löschen/Entfernen des Schlüssels verstößt nicht gegen die Eigenschaft der Mindestanzahl von Schlüsseln, die ein Knoten enthalten sollte.

Lassen Sie uns diesen Fall anhand eines Beispiels veranschaulichen, in dem wir Schlüssel 32 aus dem folgenden B-Baum löschen.

Abbildung 4.1: Löschen eines Blattknotenschlüssels (32) aus dem B-Baum

Wie wir beobachten können, verstößt das Löschen von 32 aus diesem Baum nicht gegen die obige Eigenschaft.

2. Das Löschen/Entfernen des Schlüssels verstößt gegen die Eigenschaft der Mindestanzahl von Schlüsseln, die ein Knoten enthalten sollte. In diesem Fall müssen wir einen Schlüssel in der Reihenfolge von links nach rechts von seinem benachbarten Geschwisterknoten ausleihen.

Zuerst besuchen wir das nächste linke Geschwisterkind. Wenn der linke Geschwisterknoten mehr als die Mindestanzahl an Schlüsseln hat, leiht er sich einen Schlüssel von diesem Knoten aus.

Andernfalls prüfen wir, ob wir etwas vom benachbarten rechten Geschwisterknoten leihen möchten.

Lassen Sie uns diesen Fall nun anhand eines Beispiels veranschaulichen, in dem wir 31 aus dem obigen B-Baum löschen. In diesem Fall leihen wir uns einen Schlüssel vom linken Geschwisterknoten.

Abbildung 4.2: Löschen eines Blattknotenschlüssels (31) aus dem B-Baum

Wenn beide benachbarten Geschwisterknoten bereits über eine Mindestanzahl an Schlüsseln verfügen, dann verschmelzen wir den Knoten entweder mit dem linken oder dem rechten Geschwisterknoten. Dieser Zusammenführungsprozess erfolgt über den übergeordneten Knoten.

Lassen Sie uns dies noch einmal veranschaulichen, indem wir den Schlüssel 30 aus dem obigen B-Baum löschen.

Abbildung 4.3: Löschen eines Blattknotenschlüssels (30) aus dem B-Baum

Fall 2: Das Löschen/Entfernen des Schlüssels liegt im Nicht-Blattknoten - Dieser Fall wird weiter in verschiedene Fälle unterteilt:

1. Der entfernte Nicht-Blatt-/interne Knoten wird durch einen In-Order-Vorgänger ersetzt, wenn der linke untergeordnete Knoten mehr als die Mindestanzahl an Schlüsseln aufweist.

Lassen Sie uns diesen Fall anhand eines Beispiels veranschaulichen, in dem wir den Schlüssel 33 aus dem B-Baum löschen.

Abbildung 4.4: Löschen eines Blattknotenschlüssels (33) aus dem B-Baum

2. Der entfernte Nicht-Blatt-/interne Knoten wird durch einen geordneten Nachfolger ersetzt, wenn der rechte untergeordnete Knoten mehr als die Mindestanzahl an Schlüsseln hat.

Wenn eines der untergeordneten Elemente eine Mindestanzahl an Schlüsseln hat, werden die linken und rechten untergeordneten Knoten zusammengeführt.

Lassen Sie uns diesen Fall visualisieren, indem wir den Schlüssel 30 aus dem B-Baum löschen.

Abbildung 4.5: Löschen eines Blattknotenschlüssels (30) aus dem B-Baum

'ABC's in Zahlen'

Wenn der übergeordnete Knoten nach dem Zusammenführen weniger als die Mindestanzahl an Schlüsseln hat, kann man wie folgt nach den Geschwistern suchen Fall 1 .

Fall 3: Im folgenden Fall schrumpft die Höhe des Baumes. Wenn der Zielschlüssel in einem internen Knoten liegt und das Entfernen des Schlüssels zu weniger Schlüsseln im Knoten führt (was weniger als das erforderliche Minimum ist), suchen Sie nach dem In-Order-Vorgänger und dem In-Order-Nachfolger. Wenn beide Kinder über eine Mindestanzahl an Schlüsseln verfügen, ist eine Ausleihe nicht möglich. Dies führt zu Fall 2(3) , d. h. Zusammenführen der untergeordneten Knoten.

Wir werden erneut nach dem Geschwister suchen, um einen Schlüssel auszuleihen. Wenn der Geschwisterknoten jedoch auch aus einer Mindestanzahl an Schlüsseln besteht, führen wir den Knoten mit dem Geschwisterknoten zusammen mit dem übergeordneten Knoten zusammen und ordnen die untergeordneten Knoten gemäß den Anforderungen an (aufsteigende Reihenfolge).

Lassen Sie uns diesen Fall anhand eines Beispiels veranschaulichen, in dem wir das Datenelement 10 aus dem angegebenen B-Baum löschen.

Abbildung 4.6: Löschen eines Blattknotenschlüssels (10) aus dem B-Baum

Die zeitliche Komplexität in den obigen Beispielen variiert je nach Ort, von dem aus der Schlüssel gelöscht werden muss. Somit beträgt die zeitliche Komplexität für den Löschvorgang in einem B-Baum O(log?n) .

Der Abschluss

In diesem Tutorial haben wir den B-Baum kennengelernt und seine verschiedenen Operationen anhand verschiedener Beispiele visualisiert. Wir haben auch einige grundlegende Eigenschaften und Regeln des B-Baums verstanden.