B-Baum

Grundidee und Einsatz

Ein B-Baum ist eine Daten- und Indexstruktur der Informatik, die Schlüssel sortiert in einem vollständig balancierten Baum speichert. Er wird besonders in Datenbanken und Dateisystemen eingesetzt. Anders als ein Binärbaum kann ein Knoten mehr als zwei Kinder besitzen. Dadurch hat der Baum einen hohen Verzweigungsgrad und bleibt auch bei sehr vielen Datensätzen vergleichsweise niedrig.

Das ist vor allem bei Daten wichtig, die nicht vollständig in den Hauptspeicher passen und blockweise von einem Hintergrundspeicher, etwa einer Festplatte, gelesen werden. Ein Knoten kann dabei einem Speicherblock entsprechen. Weil pro Knoten viele Schlüssel gespeichert werden, sind für eine Suche nur wenige langsame Lesezugriffe nötig. Die variable Zahl von Schlüsseln pro Knoten verringert außerdem die Häufigkeit von Ausgleichsoperationen.

Suchen, Einfügen und Löschen benötigen O(log(n)) Zeit, wobei n die Zahl der gespeicherten Schlüssel ist. Der Baum wächst und schrumpft durch Veränderungen in Richtung der Wurzel. Einfügungen selbst finden ausschließlich in Blattknoten statt.

Aufbau und Regeln

Ein Knoten speichert eine variable Anzahl s aufsteigend sortierter Schlüssel k₁,…,kₛ und optional zu jedem Schlüssel ein Datenelement. Eine Markierung isLeaf zeigt an, ob der Knoten ein Blatt ist. Ein innerer Knoten besitzt zusätzlich s+1 Verweise auf Kindknoten.

Die Schlüssel eines inneren Knotens trennen die Wertebereiche seiner Unterbäume. Für den Unterbaum x.cⱼ gilt:

bei j=1: k<x.kⱼ,
bei j∈{2,…,s}: x.kⱼ₋₁<k<x.kⱼ,
bei j=s+1: x.kⱼ₋₁<k.

Alle Blätter liegen in derselben Tiefe; diese entspricht der Höhe h des Baumes. Für einen durch den minimalen Verzweigungsgrad t definierten B-Baum gelten folgende Belegungsgrenzen:

Jeder Knoten außer der Wurzel enthält mindestens t−1 und höchstens 2t−1 Schlüssel.
Ein innerer Knoten außer der Wurzel besitzt entsprechend mindestens t und höchstens 2t Kindverweise.
Ist die Wurzel der einzige Knoten, enthält sie mindestens 1 und höchstens 2t−1 Schlüssel.
Bei einer Höhe größer als 0 hat die Wurzel mindestens 2 und höchstens 2t Kindverweise.

Die Bedeutung von t ist in der Literatur nicht einheitlich. Bezeichnet t die maximale Kinderzahl, sind höchstens t−1 Schlüssel erlaubt. Bezeichnet t dagegen die minimale Kinderzahl, liegt das Maximum bei 2t−1 Schlüsseln. Im Datenbankkontext kann k die minimale Schlüsselzahl eines Knotens und 2k dessen maximale Belegung bezeichnen; ein Knoten mit n Schlüsseln hat n+1 Kinder. Bei der Ordnung m bezeichnet m die maximale Kinderzahl: Ein Knoten hat dann mindestens ⌈m/2⌉ und höchstens m Kinder, während ein Vater mit n Kindern n−1 Schlüssel besitzt.

Für einen vollständig besetzten Baum, bei dem t die maximal erlaubte Kinderzahl ist, lautet die Schlüsselzahl t^(h+1)−1. Bei t=1024 und h=3 sind das 1024⁴−1=(2¹⁰)⁴−1=2⁴⁰−1=1.099.511.627.775 Schlüssel.

Höhe und Suche

Für einen B-Baum mit n Datenelementen und minimalem Verzweigungsgrad t gilt für die Höhe h:

log_(2t−1)(n+1) ≤ h ≤ log_t((n+1)/2)+1.

Damit erfordert das Auffinden eines Elements auch im schlimmsten Fall O(log(n)) Knotenzugriffe. Gegenüber einem balancierten binären Suchbaum ist die Höhe wegen des hohen Verzweigungsgrades deutlich kleiner. Das Verhältnis wird näherungsweise durch

log₂(n) / log_t((n+1)/2) ≈ log₂(t)

beschrieben. Bei t=1024 sind ungefähr zehnmal weniger Knotenzugriffe erforderlich. Dominiert der Zugriff auf Hintergrundspeicher die Laufzeit, ergibt sich laut Artikel dadurch eine zehnfach höhere Ausführungsgeschwindigkeit.

Die Suche nach einem Schlüssel k beginnt an der Wurzel. In einem inneren Knoten wird der kleinste Schlüssel gesucht, der größer oder gleich k ist. Ist er gleich k, ist die Suche beendet und liefert den Knoten sowie die Position des Schlüssels. Ist er größer, wird im links davon liegenden Kind weitergesucht. Ist k größer als alle Schlüssel des Knotens, folgt die Suche dem letzten Kindverweis. In einem Blatt wird k direkt unter den dort gespeicherten Schlüsseln gesucht. Ist es nicht vorhanden, lautet das Ergebnis „nicht enthalten“.

Im Artikelbeispiel wird nach k=9 gesucht. Da im betrachteten Knoten 5≤9≤13 gilt, wird der Unterbaum zwischen den Schlüsseln 5 und 13 gewählt.

Einfügen und Teilen

Vor dem Einfügen wird durch einen vollständigen Suchlauf festgestellt, ob der Schlüssel bereits vorhanden ist und in welches Blatt er gehört. Wird er schon in einem inneren Knoten gefunden, ist kein erneutes Einfügen nötig.

Beim Abstieg wird jeder ausgewählte Kindknoten darauf geprüft, ob er bereits die maximale Zahl von 2t−1 Schlüsseln enthält. Ein solcher voller Knoten wird vor dem Abstieg geteilt. Dadurch lässt sich die gesamte Einfügung in einem einzigen Abstieg durchführen, ohne den Baum anschließend reparieren zu müssen.

Ein voller Knoten besitzt eine ungerade Anzahl von Schlüsseln. Sein mittlerer Schlüssel wird in den Vaterknoten übernommen. Die verbleibenden Schlüssel werden auf zwei Knoten mit jeweils t−1 Schlüsseln verteilt. Danach wird abhängig vom einzufügenden Schlüssel in den linken oder rechten Teil abgestiegen. Im erreichten, nicht vollen Blatt wird der neue Schlüssel an der passenden Position in die sortierte Folge eingefügt. Ist bereits die Wurzel voll, entsteht durch ihre Teilung eine neue Wurzel; dabei wächst die Höhe des Baumes um eins.

Löschen und Wiederherstellen der Belegung

Das Löschen ist aufwendiger als das Einfügen. Vor jedem Abstieg wird sichergestellt, dass der gewählte Kindknoten mindestens t Schlüssel enthält. Hat er nur die erlaubte Mindestzahl t−1, wird vorher eine Verschiebung oder eine Verschmelzung vorgenommen. So verletzt eine anschließende Löschung nicht die Belegungsregeln. Ein in einem Blatt gefundener Schlüssel kann direkt entfernt werden.

Bei einer Verschiebung besitzt ein benachbarter Geschwisterknoten mindestens t Schlüssel. Ein Schlüssel dieses Geschwisters wird über den Vater in den zu schwach belegten Knoten verschoben: Der trennende Schlüssel des Vaters wandert in den ausgewählten Knoten, während ein äußerer Schlüssel des Geschwisters seinen Platz im Vater einnimmt. Gegebenenfalls wird auch der zugehörige Unterbaum umgesetzt. Die Sortierreihenfolge bleibt erhalten.

Eine Verschmelzung ist nötig, wenn der ausgewählte Knoten und seine benachbarten Geschwister jeweils nur t−1 Schlüssel besitzen. Der ausgewählte Knoten, ein Geschwister und der sie trennende Schlüssel des Vaters werden zu einem Knoten vereinigt. Werden die letzten beiden Kinder der Wurzel verschmolzen, wandert ihr letzter Schlüssel in das neue Kind. Die danach leere Wurzel wird gelöscht und durch dieses Kind ersetzt; die Baumhöhe sinkt um eins.

Ein Schlüssel in einem inneren Knoten kann nicht ohne Weiteres entfernt werden, weil er zwei Wertebereiche trennt. Er wird durch seinen symmetrischen Vorgänger oder Nachfolger ersetzt. Der Vorgänger ist der größte Schlüssel im linken Unterbaum, der Nachfolger der kleinste Schlüssel im rechten Unterbaum. Der Algorithmus wählt einen ausreichend belegten Unterbaum und löscht dort den Ersatzschlüssel. Haben beide angrenzenden Unterbäume nur t−1 Schlüssel, werden sie zunächst verschmolzen.

Spezialfälle, Beispiel und Umsetzung

Für t=2 entsteht ein 2-3-4-Baum: Seine Knoten enthalten mindestens einen und höchstens drei Schlüssel und können zwei, drei oder vier Kinder besitzen. Weitere verbreitete Varianten sind B⁺-Bäume, bei denen die Daten nur in den Blättern liegen, und B*-Bäume, die durch eine veränderte Überlaufbehandlung stets zu 2/3 gefüllt sind. Der R-Baum ist ein verwandtes Indexverfahren für mehrdimensionale Daten; AVL- und Rot-Schwarz-Bäume sind weitere ähnliche Baumstrukturen.

Das ausführliche Beispiel des Artikels zeigt einen 2-3-4-Baum mit t=2. Zunächst werden 5, 13 und 27 in einen leeren Baum eingefügt. Das Einfügen von 9 teilt die Wurzel. Nach dem Einfügen von 7 führt das Einfügen von 3 zur Teilung eines weiteren Knotens. Vor dem Löschen von 9 wird ein Schlüssel aus einem Geschwister verschoben. Beim Löschen von 7 werden zwei Knoten verschmolzen; 5 wird anschließend direkt aus einem Blatt entfernt. Das Löschen von 3 verschmilzt schließlich die letzten beiden Kinder der Wurzel, sodass die leere Wurzel durch ihr einziges Kind ersetzt wird.

Die gezeigte C++-Umsetzung verwendet die Klassen BTree und BTreeNode. Ein Knoten verwaltet ein Array mit höchstens 2t−1 Schlüsseln, ein Array mit höchstens 2t Kindverweisen, die aktuelle Schlüsselzahl und die Information, ob er ein Blatt ist. Rekursive Funktionen dienen zum sortierten Durchlaufen und Suchen. insertNonFull fügt in einen nicht vollen Knoten ein; splitChild teilt einen vollen Kindknoten und überträgt dessen mittleren Schlüssel an den Vater. Das Beispielprogramm erzeugt einen Baum mit Mindestgrad 3, fügt die Schlüssel 10, 20, 5, 6, 12, 30, 7 und 17 ein und sucht anschließend nach 6 und 15.