Ein B-Baum ist ein selbstbalancierender Suchbaum, bei dem jeder Knoten viele Schlüssel enthält und viele Kinder hat (hoher fanout). Dies hält den Baum flach, wodurch die Anzahl der Festplattenzugriffe minimiert wird — genau das, was Datenbanken und Dateisysteme benötigen.
Binary BST over 1,000,000 keys -> height ~20 (20 disk seeks)
B-tree, 100 keys/node -> height ~3 (3 disk seeks)
Each node = one disk block/page read.
[ 17 | 35 ]
/ | \
[4|9|12] [20|28] [40|50|60]
each node packs many keys -> few levels
In einem B+-Baum befinden sich alle Werte in den Blättern und die Blätter sind verlinkt, daher durchlaufen Bereichsscans eine verlinkte Liste von Blättern — ideal für Abfragen wie WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operation | Zeit | Disk I/O |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
Festspeicher- und SSD-Zugriffe sind um Größenordnungen langsamer als der Speicher, daher ist die wichtigste Metrik die I/O-Anzahl, nicht Vergleiche.
Hoher fanout reduziert I/O drastisch, indem der Baum nur wenige Ebenen tief bleibt.
Deshalb ist fast jeder relationale Datenbankindex (und viele Dateisysteme) auf B+-Bäumen aufgebaut und nicht auf binären Suchbäumen.