Vor dem Verstehen B-Baum Und B+ Baum Aufgrund der Unterschiede sollten wir den B-Baum und den B+-Baum getrennt kennen.

Was ist der B-Baum?

B-Baum ist ein selbstausgleichender Baum und ein m-Wege-Baum, wobei m die Reihenfolge des Baums definiert. Btree ist eine Verallgemeinerung des Binärer Suchbaum Dabei kann ein Knoten je nach Wert von mehr als einen Schlüssel und mehr als zwei untergeordnete Elemente haben M . Im B-Baum werden die Daten in einer sortierten Reihenfolge angegeben, mit niedrigeren Werten im linken Teilbaum und höheren Werten im rechten Teilbaum.

String zum Char in Java

Eigenschaften des B-Baums

Das Folgende sind die Eigenschaften des B-Baums:

• Im B-Baum müssen sich alle Blattknoten auf der gleichen Ebene befinden, während im Fall eines Binärbaums die Blattknoten auf unterschiedlichen Ebenen liegen können.

Lassen Sie uns diese Eigenschaft anhand eines Beispiels verstehen.

Im obigen Baum befinden sich nicht alle Blattknoten auf derselben Ebene, aber sie haben die beiden äußersten untergeordneten Knoten. Daher können wir sagen, dass der obige Baum ein ist Binärbaum aber kein B-Baum.

• Wenn der B-Baum eine Ordnung von m hat, kann jeder Knoten maximal haben M Bei minimalen Kindern haben die Blattknoten null Kinder, der Wurzelknoten zwei Kinder und die internen Knoten haben eine Obergrenze von m/2.
• Jeder Knoten kann maximal (m-1) Schlüssel haben. Wenn der Wert von m beispielsweise 5 ist, beträgt der maximale Wert der Schlüssel 4.
• Der Wurzelknoten hat mindestens einen Schlüssel, während alle anderen Knoten außer dem Wurzelknoten (Obergrenze von m/2 minus - 1) Mindestschlüssel haben.
• Wenn wir das Einfügen im B-Baum durchführen, wird der Knoten immer in den Blattknoten eingefügt.

Angenommen, wir möchten einen B-Baum der Ordnung 3 erstellen, indem wir Werte von 1 bis 10 einfügen.

Schritt 1: Zuerst erstellen wir einen Knoten mit 1 Wert, wie unten gezeigt:

Schritt 2: Das nächste Element ist 2, das wie unten gezeigt nach 1 kommt:

Schritt 3: Das nächste Element ist 3 und wird wie unten gezeigt nach 2 eingefügt:

Da wir wissen, dass jeder Knoten maximal 2 Schlüssel haben kann, teilen wir diesen Knoten durch das mittlere Element auf. Das mittlere Element ist 2 und wird daher zu seinem übergeordneten Element verschoben. Der Knoten 2 hat keinen übergeordneten Knoten und wird daher zum Stammknoten, wie unten gezeigt:

Schritt 4: Das nächste Element ist 4. Da 4 größer als 2 und 3 ist, wird es wie unten gezeigt nach der 3 hinzugefügt:

Schritt 5: Das nächste Element ist 5. Da 5 größer als 2, 3 und 4 ist, wird es nach 4 hinzugefügt, wie unten gezeigt:

Da wir wissen, dass jeder Knoten maximal 2 Schlüssel haben kann, teilen wir diesen Knoten durch das mittlere Element auf. Das mittlere Element ist 4 und wird daher zu seinem übergeordneten Element verschoben. Der übergeordnete Knoten ist Knoten 2; Daher werden 4 nach 2 hinzugefügt, wie unten gezeigt:

Schritt 6: Das nächste Element ist 6. Da 6 größer als 2, 4 und 5 ist, kommt 6 nach 5, wie unten gezeigt:

Schritt 7: Das nächste Element ist 7. Da 7 größer als 2, 4, 5 und 6 ist, kommt 7 nach 6, wie unten gezeigt:

Da wir wissen, dass jeder Knoten maximal 2 Schlüssel haben kann, teilen wir diesen Knoten durch das mittlere Element auf. Das mittlere Element ist 6 und wird daher wie unten gezeigt zu seinem übergeordneten Element verschoben:

Nach 4 kann jedoch nicht 6 hinzugefügt werden, da der Knoten maximal 2 Schlüssel haben kann. Daher teilen wir diesen Knoten durch das mittlere Element auf. Das mittlere Element ist 4 und wird daher zu seinem übergeordneten Element verschoben. Da Knoten 4 keinen übergeordneten Knoten hat, wird Knoten 4 wie unten gezeigt zum Stammknoten:

Was ist ein B+-Baum?

Der B+ Baum wird auch als fortgeschrittener selbstbalancierter Baum bezeichnet, da jeder Pfad von der Wurzel des Baums bis zum Blatt des Baums die gleiche Länge hat. Gleiche Länge bedeutet hier, dass alle Blattknoten auf der gleichen Ebene liegen. Es wird nicht vorkommen, dass einige der Blattknoten auf der dritten Ebene und einige auf der zweiten Ebene vorkommen.

Ein B+-Baumindex wird als mehrstufiger Index betrachtet, aber die B+-Baumstruktur ähnelt nicht den sequentiellen Dateien mit mehrstufigem Index.

Warum wird der B+-Baum verwendet?

Ein B+-Baum wird verwendet, um die Datensätze sehr effizient zu speichern, indem die Datensätze mithilfe der indizierten B+-Baumstruktur indiziert gespeichert werden. Durch die mehrstufige Indizierung wird der Datenzugriff schneller und einfacher.

B+-Baumknotenstruktur

Die Knotenstruktur des B+-Baums enthält Zeiger und Schlüsselwerte, die in der folgenden Abbildung dargestellt sind:

Wie wir in der obigen B+-Baumknotenstruktur beobachten können, enthält sie n-1 Schlüsselwerte (k₁zu k_n-1) und n Zeiger (S₁Spitze_N).

Die Suchschlüsselwerte, die im Knoten platziert werden, werden in sortierter Reihenfolge gehalten. Wenn ich alsoichJ.

entspricht einer Zeichenfolge in Java

Einschränkung für verschiedene Knotentypen

Sei 'b' die Ordnung des B+-Baums.

Nicht-Blattknoten

Stellt 'm' die Anzahl der Kinder eines Knotens dar, dann kann die Beziehung zwischen der Reihenfolge des Baums und der Anzahl der Kinder wie folgt dargestellt werden:

Angenommen, k stellt die Suchschlüsselwerte dar. Die Beziehung zwischen der Reihenfolge des Baums und dem Suchschlüssel kann wie folgt dargestellt werden:

Da wir wissen, dass die Anzahl der Zeiger gleich den Suchschlüsselwerten plus 1 ist, kann es mathematisch wie folgt geschrieben werden:

Anzahl der Zeiger (oder untergeordneten Elemente) = Anzahl der Suchschlüssel + 1

Daher wäre die maximale Anzahl von Zeigern „b“ und die minimale Anzahl von Zeigern wäre die Deckenfunktion von b/2.

Blattknoten

Ein Blattknoten ist ein Knoten, der auf der letzten Ebene des B+-Baums auftritt, und jeder Blattknoten verwendet nur einen Zeiger, um sich miteinander zu verbinden und den sequentiellen Zugriff auf der Blattebene bereitzustellen.

Im Blattknoten beträgt die maximale Anzahl untergeordneter Elemente:

Die maximale Anzahl an Suchschlüsseln beträgt:

Wurzelknoten

Die maximale Anzahl an Kindern im Fall des Wurzelknotens beträgt: b

Die Mindestanzahl der Kinder beträgt: 2

Sonderfälle im B+-Baum

Fall 1: Wenn der Wurzelknoten der einzige Knoten im Baum ist. In diesem Fall wird der Wurzelknoten zum Blattknoten.

In diesem Fall ist die maximale Anzahl von Kindern 1, d. h. der Wurzelknoten selbst, während die minimale Anzahl von Kindern b-1 ist, was der eines Blattknotens entspricht.

Darstellung eines Blattknotens im B+-Baum

In der obigen Abbildung ist '.' stellt den Zeiger dar, während 10, 20 und 30 die Schlüsselwerte sind. Der Zeiger enthält die Adresse, an der der Schlüsselwert gespeichert ist, wie in der obigen Abbildung dargestellt.

Beispiel eines B+-Baums

In der obigen Abbildung enthält der Knoten drei Schlüsselwerte, nämlich 9, 16 und 25. Der Zeiger, der vor 9 erscheint, enthält die durch k dargestellten Schlüsselwerte kleiner als 9_ich. Der Zeiger, der vor 16 erscheint, enthält die Schlüsselwerte größer oder gleich 9, aber kleiner als 16, dargestellt durch kj. Der Zeiger, der vor 25 erscheint, enthält die durch k dargestellten Schlüsselwerte größer oder gleich 16, aber kleiner als 25_N.

Unterschiede zwischen B-Baum und B+-Baum

Im Folgenden sind die Unterschiede zwischen dem B-Baum und dem B+-Baum aufgeführt: