B-Baum
aus www.iwiki.de, der freien Wissensdatenbank
Ein B-Baum ist in der Informatik eine Daten- oder Indexstruktur, die häufig in Datenbanken und Dateisystemen eingesetzt wird. Ein B-Baum ist ein immer vollständig balancierter Baum, der Daten sortiert nach Schlüsseln speichert. B-Bäume wachsen – und schrumpfen – anders als die meisten Suchbäume von den Blättern hin zur Wurzel.
Eigenschaften von B-Bäumen
Ein B-Baum der Ordnung m ist ein Baum mit folgenden Eigenschaften:
- Jeder Knoten enthält zwischen m und 2m Elementen (außer der Wurzel, die weniger als m Elemente enthalten kann).
- Jeder Knoten ist entweder ein Blattknoten oder er hat k + 1 Nachfolger, wobei k die Anzahl der Elemente im Knoten ist.
- Alle Blattknoten liegen auf der gleichen Stufe
Typicher Aufbau eines B-Baum-Knotens (=Seite): Format eines Knotens bei sequentiell aufsteigender Anordnung der Elemente (SchlĂĽssel):
p0 | k1 d1 p1 | k2 d2 p2 |...|
pi: Zeiger auf Knoten mit Elementen ki < x < ki + 1
di: Zeiger auf Satz mit SchlĂĽssel ki
ki: i-tes Element (SchlĂĽssel) im Knoten (Seite)
