Vorlesung Informatik 2 - Teil B: Theorie
4.13 B-Bäume
1970 von Rudolf Bayer und Edward McCreight bei Boeing entwickelt.
Das Original Paper findet man z.B. hier: Organization and Maintenance of Large Ordered Indices
B-Bäume sind nach ihrem Erfinder Bayer so benannt, andere Interpretationen sind breit oder balanciert. B-Bäume sind keine Binärbäume! Einen B-Baum als Binärbaum zu bezeichnen ist etwas so wie von einer if-Schleife zu sprechen...
Ein B-Baum ist ein Suchbaum, dessen Knoten sehr viele Einträge haben, also eine Erweiterung der 2-3-4 Bäume. Dabei sind alle Pfade von der Wurzel zu den Blättern gleich lang.
Die Zahl der Einträge in einem B-Baum Knoten variiert zwischen n und 2n, wobei n als Ordnung des B-Baums bezeichnet wird (die Bezeichnung Ordnung ist in der Literatur aber nicht einheitlich, in manchen Büchern wird sie mit 2n+1 angegeben).
Ein kleines Beispiel eines B-Baumes der Ordnung n=2, dessen Schlüssel wieder Buchstaben sind:
|C|G|L|R|
| | | | |
--------------------- | | | ---------------------------------
| | | | |
| ---------| | ----------------- |
| | | | |
|A|B| |D|E|F| |H|J|K| |M|O|P|Q| |T|U|Z|
Die Anzahl der Einträge in jeder Seite liegt in diesem Beispiel zwischen 2 und 4.
Die Eigenschaften von B-Bäumen sind:
- Alle Pfade von der Wurzel bis zu den Blättern sind gleich lang,
- jede Knoten (Seite) außer der Wurzel hat zwischen n und 2n Einträge.
Die Höhe eines B-Baumes mit m Einträgen beträgt also logn m und somit hat die Komplexität der Such-, Einfüge- und Lösch Operationen die Ordnung O(log N).
Ähnlich wie beim 2-3-4 Baum wird ein Split durchgeführt, wenn in eine volle Seite ein weiterer Eintrag eingefügt werden soll.
Aus Zeitgründen gehen nicht weiter ins Detail der Algorithmen von B-Bäumen.
Sogenannte B+ Bäume trennen die Speicherung der Schlüssel und der Daten, wobei die Seiten mit den Daten die unterste Ebene des Baums bilden. Diese Datenstruktur ist besonders bei der Verwaltung von Dateisystemen von Vorteil.
B-Bäume werden meist eingesetzt um sehr große Datenmengen zu verwalten, die nicht mehr in den Hauptspeicher passen. Die Ordnung wird dann auf die Größe einer Speichereinheit (block, record, page) der Festplatte. Deshalb werden die Knoten eines B-Baums
häufig auch als Seiten bezeichnet.
Typische Blockgrößen von Dateisystemen liegen zwischen 1KiB und 128 KiB, würde ein Eintrag 16 Byte groß sein passen also zwischen 64 und 16.384 Einträge auf eine Seite.
Anwendungen von B-Bäumen:
Fast jedes Datenbanksystem setzt B-Bäume ein, um die Indizes von Tabellen zu verwalten, auch die Spanner Datenbank mit der Google große Datenmengen verwaltet.
Das Linux Dateisystem BTRFS (B-Tree File System) trägt die Datenstruktur im Namen.
Fast alle modernen Dateisysteme (NFTS, EXT4, ReiserFS, XFS, ZFS) verwenden B+ Bäume zur Verwaltung der Daten auf der Festplatte.