B-Tree
Ein B-Baum ist ein selbstbalancierter mehrwegiger Suchbaum, bei dem jeder Knoten mehrere Schlüssel und Kindzeiger hält und O(log N)-Suchen mit etwa O(1)-Fan-out garantiert.
Zweck
Die zentrale Datenstruktur von Datenbankindizes verstehen und ihre Lese-/Schreibleistung sowie Seitenfüllung analysieren.
Mechanismus
Ein B-Baum der Ordnung m hat höchstens m Kinder pro Knoten und mindestens ceil(m/2). Einfügungen spalten und Löschungen verschmelzen, um das Gleichgewicht zu halten; alle Blätter liegen auf gleicher Tiefe. Die Knotengröße richtet sich nach dem Datenbank-Seiten-I/O (z. B. 16 KB), und hoher Fan-out hält den Baum flach (3-4 Ebenen indizieren TBs).
Anwendungsfälle
- Index-Datenstrukturen
- Datenbankinternas
- Speicheroptimierung