4.5 B-Bäume

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<y$, dass $x<y$ für alle $x\in X$ gilt. Für einen Baum oder Teilbaum $T$, der Schlüssel speichert, bezeichnen wir mit $\text{keys}(T)$ die Menge der Schlüssel, die in $T$ gespeichert sind.

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.

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:

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 $◻$ 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 $ln$, wird dadurch zu $lnp$ 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 $$ 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 $$ (falls $$, dann werden wir das feststellen, wenn wir an einem Blatt landen, und müssen nichts weiter tun); wenn $$ in einem untersten Knoten liegt, löschen wir es einfach erst mal; ansonsten, wenn $$ weiter oben liegt, sei $$ das Maximum im linken Teilbaum von $$; der Schlüssel $$ liegt in einem untersten Knoten; wir verschieben $$ an die Position von $$ und sind nun in einer Situation, als hätten wir $$ 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 $$-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. 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. 2. Die große Schwester anschnorren. Dies ist symmetrisch zum vorherigen Fall:

     

  3. 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 $$ Schlüssel und $$ Kinder; nun verliert er einen Schlüssel $$, und die Zahl der Kinder nimmt durch das Verschmelzen um 1 ab: er hat nun also $$ Schlüssel und $$ Kinder. Wir erhalten also einen gültigen B-Baum. Wenn $$, dann ist das sogar ein $$-Baum; wenn $$, 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 $$ ist.

Verallgemeinerung. Ein B-Baum heiße $$-Baum, wenn jeder innere Knoten mindestens $$ und höchstens $$ Kinder haben darf. Oben haben wir $$ 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 $$ Kinder hat; wenn wir ihn mit einem Geschwisterknoten verschmelzen sollten, dann, weil dieser nur $$ Kinder hat, also keins davon entbehren kann. Nach der Verschmelzung erhalten wir nun einen Knoten mit $$ 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 $$ gelten muss.

Betrachten wir nun eine insert-Operation. Dabei kann ein "zu schwerer" Knoten mit $$ Kindern (und $$ Schlüsseln) entstehen. Diesen zerbrechen wir in zwei Teilknoten mit $$ bzw. $$ 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 $$ verlangen, was äquivalent zu $$ bzw. $$.

Solange also $$ ist, können wir $$-Bäume wie oben implementieren. In der Literatur wird $$ manchmal als die Ordnung des B-Baumes bezeichnet. Unseren Beispielen oben haben B-Bäume der Ordnung $$ 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 $$ 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.