B-Baum

Ein B-Baum ist in der Informatik eine Datenstruktur, die gewöhnlich in Datenbanken und Dateisystemen eingesetzt wird. Es gibt unterschiedliche Ansichten darüber, wofür das B in B-Baum steht. Die häufigste Interpretation ist, dass es für balanciert steht, da alle Blätter auf der gleichen Ebene im Baum stehen. Eine weitere Interpretation ist, dass das B nach dem Namen seines Erfinders Rudolf Bayer für Bayer steht.

Die Idee hinter B-Bäumen ist, dass die inneren Knoten eine variable Anzahl von Kindern innerhalb eines festgelegten Bereichs besitzen können und so nicht so häufig ausbalanciert werden müssen, wie beispielsweise AVL-Bäume.

Definitionen

Datei:Bbaum.jpg

Evolution eines B-Baumes

Ein n-m-Baum ist ein externer Suchbaum, bei dem alle Blätter die selbe Tiefe haben und für den gilt, dass

1. die Anzahl der Kinder an den inneren Knoten außer der Wurzel mindestens n und höchstens m betragen darf,
2. die Anzahl der Kinder der Wurzel mindestens 2 und höchstens m betragen darf und
3. $2n-1\leq m$.

Von B-Bäumen spricht man, wenn $2n-1=m$ gilt. Für den Spezialfall n=2 und m=3 spricht man von 2-3-Bäumen. Eine Variante des B-Baumes ist der B*-Baum.

Beispiel

Die Grafik zeigt die Entstehung eines B-Baums mit 3 Kindern und 3 Blätter . Folgende Operationen wurden ausgeführt: new, +1, +2, +3, +4, +5, +6, +7, +8, +9, -1, -2, -3, -4, -5, -6

Einsatzgebiete

Durch die Sammlung einer größeren Menge von Schlüsseln in jedem der inneren Knoten eignen sich diese Bäume sehr gut für die Organisation riesiger Datenmengen auf externen Speichern, bei denen die Übertragung von Daten mit größeren Wartezeiten zwischen Zugriffsanforderung und Verfügbarkeit der Daten verbunden ist (z.B. Festplatten). Dazu kommt, dass alle Kindknoten in der gleichen Ebene des Baums liegen, und damit konstante Zugriffszeiten auf die Kindknoten gegeben sind. B-Bäume kommen dementsprechend auch in Dateisystemen und Datenbanken zum Einsatz. Weiterhin können B-Bäume sehr gut an die Hardware angepasst werden. So kann die Größe eines Knotens der Page-Größe angepasst werden. Dadurch kann der B-Baum sehr effizient auf externen Speichern abgelegt werden und es ist eine schnelle Suchzeit gesichert. Die wichtigesten Einzeloperationen (member, insert und delete) haben einen Aufwand von O(log n).

Geschichte

Der B-Baum wurde 1972 von Rudolf Bayer und Edward M. McCreight entwickelt. Er erwies sich als ideale Datenstruktur zur Verwaltung von Indizes für das relationale Datenmodell, das im gleichen Jahr von Edgar F. Codd entwickelt wurde. Diese Kombination führte zur Entwicklung des ersten SQL-Datenbanksystems System R bei IBM.

Literatur

deutsch

• Niklaus Wirth: Algorithmen und Datenstrukturen mit Modula-2, Stuttgart 1986, ISBN 3519022605

englisch

• R. Bayer, E. McCreight: Organization and Maintenance of Lange Ordered Indexes. In: Acta Informatica 1, 1972, S. 173-189

• R. Bayer, E. McCreight: Symmetric binary B-Trees: data structure and maintenance algorithms. In: Acta Informatica 1, 1972, S. 290-306