Einführung in die Eigenschaften von B-Tree

B-Baum ist eine allgemeine Datenstruktur. Daneben gibt es noch den B+-Baum.

Hier müssen wir das Konzept klären. Was ist der Unterschied zwischen B-Baum, B-Baum und B+-Baum? In welcher Beziehung stehen sie zueinander?

Tatsächlich gibt es nur zwei Arten von Datenstrukturen, nämlich B-Baum und B+-Baum. Manchmal wird auch „B-Baum“ als „B-Tree“ bezeichnet, es handelt sich jedoch um dasselbe. Beachten Sie, dass das "-" in der Mitte eines B-Baums ein Bindestrich und kein "Minuszeichen" ist. Auf Englisch heißt es B-Tree, was im Chinesischen als B-tree übersetzt wird. Manche Übersetzer fügen gerne einen Bindestrich „-“ ein, sodass es B-tree wird, und manche Leser interpretieren B-tree fälschlicherweise als B-Minus-Tree.

Bevor wir B-Bäume vorstellen, schauen wir uns zunächst ein wichtiges Konzept an: die Reihenfolge.

Die Ordnung eines Baums ist die maximale Anzahl von untergeordneten Knoten jedes Knotens im Baum. Das heißt, wenn einige Knoten 2 untergeordnete Knoten haben, einige Knoten 4 untergeordnete Knoten haben und die maximale Anzahl der untergeordneten Knoten 5 ist, dann ist die Ordnung des Baums 5.

Aus dieser Perspektive ist die Ordnung eines Binärbaums 2.

Als nächstes stellen wir die wichtigsten Eigenschaften des B-Baums vor. Wir nehmen an, dass die Ordnung des B-Baums m ist. Ein B-Baum der Ordnung m ist entweder ein leerer Baum oder ein Baum mit den folgenden Eigenschaften:

1. Jeder Knoten hat höchstens m untergeordnete Knoten. Es gibt mindestens m/2 (aufgerundet) Knoten. Oder es kann folgendermaßen ausgedrückt werden: m/2 <= Anzahl der untergeordneten Knoten <= m. Der Stammknoten stellt jedoch eine Ausnahme dar. Der Stammknoten kann mindestens zwei untergeordnete Knoten haben.

2. Die Anzahl der untergeordneten Knoten jedes Knotens ist um 1 größer als die Anzahl der im Knoten gespeicherten Schlüsselwörter. Das heißt, wenn k Schlüsselwörter in einem Knoten gespeichert sind, hat der Knoten k + 1 untergeordnete Knoten (Unterbäume).

3. Die k Schlüsselwörter in jedem Knoten werden von klein nach groß angeordnet und als k1, k2, k3, ... kk aufgezeichnet. Dann hat der Knoten k+1 Zeiger, bezeichnet als p0, p1, p2, ... pk. Darüber hinaus sind alle Elemente in den untergeordneten Knoten, auf die p3 zeigt, größer als k3 und kleiner als k4, wie in der folgenden Abbildung dargestellt. Auch das ist relativ einfach zu verstehen und zu merken. Jeder Zeiger p liegt genau an der Lücke zwischen den Schlüsselwörtern k. Daher sollte der Wert des Elements des Kindknotens, auf das der Zeiger an der Lücke zeigt, natürlich größer sein als das Element links vom Zeiger und kleiner als das Element rechts vom Zeiger.

4. Der B-Baum ist ein streng ausgeglichener Suchbaum, bei dem die Höhen seiner linken und rechten Teilbäume gleich sind. Die Blattknoten befinden sich auf derselben Ebene und können durch leere Knoten dargestellt werden.

Ein Beispiel für einen B-Baum:

Zusammenfassen

Das Obige ist der vollständige Inhalt dieses Artikels. Ich hoffe, dass der Inhalt dieses Artikels einen gewissen Lernwert für Ihr Studium oder Ihre Arbeit hat. Vielen Dank für Ihre Unterstützung von 123WORDPRESS.COM. Wenn Sie mehr darüber erfahren möchten, schauen Sie sich bitte die folgenden Links an