B-Bäume grob

B-Bäume speichern mehrere Schlüssel pro Knoten und halten die Blätter auf gleicher Tiefe. Sie sind für blockorientierten Speicher (Festplatte, SSD-Seiten) ausgelegt.

Im Vergleich zu AVL: weniger Rotationen auf dem Pfad, breitere Knoten, typisch in Datenbanken und Dateisystemen.

hohe Verzweigung, balancierte Höhe.

Datenbank- und Dateisystemindizes (InnoDB, NTFS/HFS-Ideen), weil hohe Branching-Faktoren zu den Blockgrössen von SSD/HDD passen. Weniger Random I/O pro Suche als bei binären Knoten.

Vertiefung

Ein B-Baum speichert mehrere sortierte Schlüssel pro Knoten und besitzt entsprechend mehrere Kinder. Alle Blätter liegen auf derselben Ebene. Die hohe Verzweigung reduziert die Zahl der Knoten, die auf einem Suchpfad besucht werden.

Diese Struktur ist für blockorientierten Speicher geeignet. Ein Knoten wird so dimensioniert, dass viele Schlüssel mit einem Seitenzugriff gelesen werden. Die relevante Kostenmetrik ist daher oft die Zahl der Speicherzugriffe statt einzelner Vergleiche.

Beim Einfügen wird ein voller Knoten geteilt und ein Trennschlüssel zum Elternknoten befördert. Löschung kann Ausleihen oder Zusammenführen erfordern, damit Mindestbelegungen erhalten bleiben.

Schwierigkeitsstufen

1. Schlüsselintervalle den Kindern eines Knotens zuordnen.
2. Einen Knotensplit und die Beförderung verfolgen.
3. Hohe Verzweigung mit externen Speicherblöcken begründen.

Fallstricke

Ein B-Baum ist kein binärer Baum. Die erlaubte Schlüsselzahl hängt von der verwendeten Ordnungsdefinition ab, die in Lehrbüchern unterschiedlich notiert wird.