Ein B-Baum (englisch B-tree) ist ein spezieller Suchbaum, der Daten so organisiert, dass Zugriffe selbst auf riesigen Datenmengen zuverlässig in logarithmischer Zeit bleiben. Er wurde 1970 von Rudolf Bayer und Edward McCreight bei Boeing Research Laboratories entwickelt – das B steht je nach Lesart für balanciert, breit oder Boeing. Der B-Baum ist die wichtigste Indexstruktur moderner Datenbanken und Dateisysteme.
Wie ein B-Baum funktioniert
Anders als ein binärer Suchbaum, der pro Knoten höchstens zwei Kinder hat, darf ein Knoten im B-Baum viele Schlüssel und entsprechend viele Kinder speichern. Die maximale Kinderzahl heißt Ordnung des Baums. Zwei Regeln halten den Baum im Gleichgewicht:
- Alle Blätter liegen auf derselben Tiefe – der Baum wächst nur an der Wurzel, nicht an den Blättern.
- Jeder Knoten bleibt mindestens halb gefüllt – beim Einfügen wird ein voller Knoten geteilt, beim Löschen notfalls mit Nachbarknoten verschmolzen.
Dadurch ist die Höhe des Baums garantiert logarithmisch, und jede Suche braucht nur so viele Zugriffe wie die Höhe – für Millionen Datensätze oft nur drei oder vier Ebenen. Der Aufwand jeder Operation ist O(log n).
Warum B-Bäume für Massendaten ideal sind
Der entscheidende Vorteil gegenüber den im Arbeitsspeicher lebenden Baumvarianten wie AVL-Baum oder Rot-Schwarz-Baum ist die Blockorientierung: Ein Knoten des B-Baums wird so dimensioniert, dass er genau einer Speicherseite oder einem Plattenblock entspricht. Jede Ebene kostet genau einen Plattenzugriff, und durch die vielen Schlüssel pro Knoten bleibt die Anzahl der Ebenen winzig. Für jede gesuchte Struktur gibt es so eine eigene Datenstruktur – die Baum-Datenstruktur ist nur der gemeinsame Oberbegriff.
Einsatzgebiete
- Datenbank-Indizes: MySQL (InnoDB) und PostgreSQL speichern ihre Indizes als B-Bäume – jede Query und jeder SQL-Zugriff profitiert davon.
- Dateisysteme: ext4, NTFS und ZFS nutzen B-Baum-Varianten, um Verzeichnisse und Metadaten zu verwalten.
- NoSQL-Systeme: Viele dokumenten- und key-value-orientierte Datenbanken verwenden ebenfalls B-Bäume.
B+-Baum: die praxisüblichste Variante
Die verbreitetste Abwandlung ist der B+-Baum. Er speichert die eigentlichen Daten ausschließlich in den Blättern; die inneren Knoten enthalten nur Schlüssel als Wegweiser. Zusätzlich sind die Blätter untereinander verkettet, sodass Bereichsabfragen und sequenzielles Lesen in einem Durchlauf möglich sind – ein großer Vorteil gegenüber einer ungeordneten Hash-Tabelle, die nur exakte Treffer in O(1) liefert.
Abgrenzung zu anderen Strukturen
- Binärbaum: allgemeiner Baum mit höchstens zwei Kindern, ohne Such- oder Balance-Eigenschaft.
- Binärer Suchbaum: sortierte Binärstruktur im Arbeitsspeicher, kann entarten.
- AVL-Baum und Rot-Schwarz-Baum: selbstbalancierende Binärbäume – schnell im RAM, aber nicht blockorientiert.
- Heap: ungeordnete Baumstruktur für Prioritätswarteschlangen, nicht zum Suchen geeignet.
- Trie: Sonderfall für Zeichenketten mit Präfixsuche – für Datenbankindizes mit Zahlen und kurzen Schlüsseln bleibt der B-Baum die erste Wahl.
Wer Daten auf Platte oder SSD ablegt und schnell wiederfinden will, kommt an B-Bäumen praktisch nicht vorbei – sie sind der Standard unter den Indexstrukturen.