B-Bäume sind ähnlich wie binäre Suchbäume, allerdings
erlauben wir nun, dass ein Knoten mehrere Schlüssel speichert.
Wir führen folgende Schreibweise ein: wenn
\(X\) eine Menge von Schlüsseln und \(y\) ein einzelner Schlüssel ist,
dann bedeutet \(X \lt y\), dass \(x \lt y\) für alle \(x \in X\) gilt.
Für einen Baum oder Teilbaum \(T\), der Schlüssel speichert, bezeichnen wir mit
\(\keys(T)\) die Menge der Schlüssel, die in \(T\) gespeichert sind.
Definition(B-Bäume).
Ein B-Baum ist ein Baum, in welchem
jedes Blatt gleichen Abstand der Wurzel hat,
jeder innere Knoten, der
Kinder \(T_0, T_1, \dots, T_k\) hat, eine Folge von genau \(k\) Schlüsseln
\(x_1,\dots,x_k\) speichert, so dass
\begin{align*}
\keys(T_0) \lt x_1 \lt \keys(T_1) \lt x_2 \lt \dots \lt \keys(T_{k-1})
\lt x_k \lt \keys(T_k) \
\end{align*}
gilt.
Blätter speichern keine Schlüssel und werden mit \(\square\) notiert
(und machmal ganz weggelassen).
Ich gebe zu, es ist kein schöner Anblick, dass der Elternknoten von \(e\) keinen Schlüssel
speichert und nur ein Kind hat. Gewöhnen Sie sich aber an diesen Anblick; sie werden
ihn gleich in der delete-Operation zumindest zeitweise ertragen müssen.
Definition
Ein B-Baum heißt ein \((2,3)\)-Baum, wenn jeder innere Knoten
genau \(2\) oder \(3\) Kinder hat.
Das obige Beispiel ist also kein \((2,3)\)-Baum: der Elternknoten
von \(e\) hat nur ein Kind, also zu wenige, und der Wurzelknoten hat
vier Kinder, also zu viele. Hier wäre ein \((2,3)\)-Baum für die gleiche
Schlüsselmenge:
Als Datenstruktur ist ein \((2,3\)-Baum etwas schwieriger zu speichern
und zu unterhalten als ein Treap; dafür ist die Laufzeitanalyse
ein Kinderspiel:
Beobachtung
Ein \((2,3)\)-Baum der Höhe \(h\) hat mindestens
\(1 + 2 + 4 +\cdots + 2^{h-1} = 2^h - 1\) innere Knoten.
Somit hat ein \((2,3)\)-Baum \(T\), der \(n\) Schlüssel speichert,
höchstens Höhe
\begin{align*}
\height(T) \leq \log_2 (n+1) \ .
\end{align*}
Die Laufzeiten aller Operationen insert, find, delete werden
propotional zur Höhe des Baumes und somit \(O(\log n)\) sein.
Wir werden sie nun im Einzelnen beschreiben.
find geht so wie in BSTs, nur dass wir in
Knoten mit zwei Schlüsseln \(x_1,x_2\) den gesuchten Schlüssel \(k\)
im Allgemeinen mit \(x_1\) und mit \(x_2\) vergleichen müssen, um
zu bestimmen, in welchem Teilbaum wir fortfahren.
insert x sucht zu allererst den tiefsten inneren
Knoten und fügt ihn dort
an der richtigen Stelle ein (ich zögere, Blatt zu sagen, weil nach Definition die
Blätter \(\square\) keine Schlüssel speichern und in den obigen
Abbildungen auch gar nicht gezeichnet wurden). Wenn in dem
untersten Knoten noch Platz ist, dann ist alles in Ordnung:
Allerdings kann es vorkommen, dass wir nun unten einen Knoten mit zu vielen,
also drei Schlüsseln haben:
Der Knoten ist nun zu schwer geworden und zerfällt zwei Teilknoten und
sendet den mittleren Schlüssel nach oben. Der Knoten darüber,
also \(l n\), wird dadurch zu \(l n p\) und zerfällt seinerseits.
Wir stellen das in dieser kleinen Animation dar:
Der Zyklus zu schwer - zerbrechen - Mittelschlüssel nach oben
weiterschieben wird wiederholt, bis
der Schlüssel in einen Elternknoten hochgeschoben wird, der noch
Kapazität hat (also zuvor nur einen Schlüssel), oder bis zur Wurzel.
Wenn die Wurzel zerfällt, entsteht ein neuer Wurzelknoten mit nur
einem Schlüssel, und die Höhe des Baumes wächst um 1.
Auch in diesem Fall finde ich das konkrete Beispiel fast
weniger lehrreich als den "graphischen Pseudocode" für insert:
Die Buchstaben \(L, R\) stehen für die
Teillisten Baum/Schlüssel.../Baum, die links bzw. rechts von dem Pfeil
stehen und von denen einen auch leer sein kann.
delete x ist etwas komplizierter als insert.
Zuerst lokalisieren wir \(x\) (falls \(x \not \in \keys(T)\), dann werden wir
das feststellen, wenn wir an einem Blatt landen, und müssen nichts weiter tun);
wenn \(x\) in einem untersten Knoten liegt, löschen wir es einfach
erst mal; ansonsten, wenn \(x\) weiter oben liegt, sei \(y\) das
Maximum im linken Teilbaum von \(x\); der Schlüssel \(y\) liegt
in einem untersten Knoten; wir verschieben \(y\) an die Position von \(x\) und
sind nun in einer Situation, als hätten wir \(y\) gelöscht.
Wir müssen uns
also nur noch um den Fall kümmern, dass ein Element in einem untersten Knoten
gelöscht wird. Im obigen Beispiel hatten wir Glück: der unterste Knoten
hatte zwei Schlüssel und hat nach Löschen noch einen; der Baum ist
also immer noch ein \((2,3)\)-Baum und wir müssen nichts weiter tun.
Anders sieht es aus, wenn im untersten Knoten der letzte Schlüssel gelöscht
wird,
wir also nun 0 Schlüssel haben. Im allgemeinen werden wir
mit der Situation konfrontiert sein, dass es (genau einen) Knoten gibt,
der 0 Schlüssel (und somit genau ein Kind) hat, und dieser Knoten
muss nicht unbedingt ganz unten liegen. In diesem Falle
gibt es drei Möglichkeiten, den Fehler zu "reparieren":
1. Den kleinen Bruder anschnorren.
Wenn der leere Knoten einen linken Geschwisterknoten hat und dieser
ein Element entbehren kann, können wir eine Rechtsrotation
durchführen:
2. Die große Schwester anschnorren.
Dies ist symmetrisch zum vorherigen Fall:
Verschmelzen.
Eventuell können wir keine der zwei vorherigen Maßnahmen durchführen,
z.B. weil die Geschwister selbst nur einen Schlüssel besitzen.
In diesem Falle müssen wir zwei Geschwister verschmelzen.
Zuerst beachten Sie, dass der leere Knoten in jedem Fall mindestens
ein Geschwister hat: der Elternknoten selbst ist nicht leer (es wird
temporär nur maximal ein Knoten leer sein) und hat somit mindestens zwei
Kinder. Im folgenden zeige ich die Operation, die durchzuführen ist,
wenn der leere Knoten einen kleinen Bruder hat, der selbst nur
einen Schlüssel enthält:
Rechnen wir nach: kleiner Bruder und leerer Knoten hatten
zusammen drei Kinder und einen Schlüssel; nach der Operation
hat der entstandene Knoten zwei Schlüssel und drei Kinder.
Der Elternknoten hatte \(k \geq 1\) Schlüssel und \(k+1\)
Kinder; nun verliert er einen Schlüssel \(w\), und die Zahl der
Kinder nimmt durch das Verschmelzen um 1 ab: er hat nun also
\(k-1\) Schlüssel und \(k\) Kinder. Wir erhalten also einen
gültigen B-Baum.
Wenn \(k-1 \geq 1\), dann ist das sogar ein \((2,3)\)-Baum;
wenn \(k-1 = 0\), dann ist nun der Elternknoten leer und hat
nur ein Kind; wir müssen nun also die gleiche Reparaturoperation
am Elternknoten fortsetzen. Dies kann sich bis zur Wurzel
fortsetzen; wenn der Wurzelknoten selbst leer geworden ist
(und ein Kind hat), dann löschen wir den Wurzelknoten und ernennen
sein Kind zur neuen Wurzel; die Tiefe des Baumes nimmt nun um 1 ab.
Im konkreten Beispiel können Löschoperation so aussehen:
Es sollte klar sein, dass für Operationen die Laufzeit
proportional zur Höhe des Baumes und somit \(O(\log n)\) ist.
Verallgemeinerung.
Ein B-Baum heiße \((a,b)\)-Baum, wenn jeder innere Knoten
mindestens \(a\) und höchstens \(b\) Kinder haben darf.
Oben haben wir \(a = 2, b= 3\) gewählt. Welche Werte
sind "erlaubt"?
Hierfür müssen wir uns delete und
insert ansehen.
Bei delete kann ein "zu leichter" Knoten entstehen, der also
nur \(a-1\) Kinder hat; wenn wir ihn mit einem Geschwisterknoten
verschmelzen sollten, dann, weil dieser nur \(a\) Kinder hat, also
keins davon entbehren kann. Nach der Verschmelzung erhalten wir nun
einen Knoten mit \(2a - 1\) Knoten; dabei verliert der Elternknoten
ein Kind (und einen Schlüssel) und könnte seinerseits wieder "zu leicht" werden.
Kann der neu entstandene Kindknoten "zu schwer" werden? Nicht, wenn
wir verlangen, dass \(2a - 1 \leq b\) gelten muss.
Betrachten wir nun eine insert-Operation.
Dabei kann ein "zu schwerer" Knoten mit \(b+1\) Kindern
(und \(b\) Schlüsseln) entstehen. Diesen zerbrechen wir
in zwei Teilknoten mit \(\floor{\frac{b+1}{2}}\) bzw.
\(\ceil{\frac{b+1}{2}}\) Kindern. Dabei wird der "mittlere"
Schlüssel in den Elternknoten eingefügt, wodurch dieser wiederum
zu schwer werden kann. Kann aber einer der durch Teilung neu entstandenen
Knoten zu leicht sein?
Nicht, wenn wir \(\floor{\frac{b+1}{2}} \geq a\) verlangen,
was äquivalent zu \(b+1 \geq 2a\) bzw. \(2a - 1\leq b\).
Solange also \(b \geq 2a - 1\) ist, können wir \((a,b)\)-Bäume wie
oben implementieren. In der Literatur wird
\(b\) manchmal als die Ordnung des B-Baumes
bezeichnet. Unseren Beispielen oben haben B-Bäume der Ordnung
\(3\) verwendet. Größere Ordnung hat den Vorteil, dass
die Tiefe geringer wird, wir also weniger Knoten durchlaufen müssen;
der Nachteil ist, dass wir pro Knoten mehr Zeit zum Suchen brauchen.
Wenn wir es mit einem zweistufigen Rechnerspeicher zu tun haben,
beispielsweise einem großen aber (vergleichsweise) langsamen SSD-Speicher
und einem kleinen aber sehr schnellen Cache, dann bietet es sich
an, die Ordnung \(b\) so zu wählen, dass ein Knoten mit allen
in einen Cache-Block hineinpasst, wir also mit einem Memory-Zugriff
gerade einen ganzen Knoten laden können. Der Grund ist, dass
das Suchen innerhalb des Knotens nun ausschließlich im Cache stattfindet
und somit viel schneller ist als vergleichbare Hauptspeicherzugriffe.
