B-Baum
Ein B-Baum ist in der Informatik eine Datenstruktur, genauer eine Indexstruktur, 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. Ein B-Baum ist nicht mit einem Binärbaum verwandt und darf keinesfalls damit verwechselt werden.
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
Ein n-m-Baum ist ein externer Suchbaum, bei dem alle Blätter die selbe Tiefe haben und für den gilt, dass
- die Anzahl der Kinder an den inneren Knoten außer der Wurzel mindestens n und höchstens m betragen darf,
- die Anzahl der Kinder der Wurzel mindestens 2 und höchstens m betragen darf und
- .
Von B-Bäumen spricht man, wenn 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ättern. 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 großer 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 wichtigsten 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.
Siehe auch
- R-Baum ist ein verwandtes Indexverfahren für mehrdimensionale Daten.
Literatur
deutsch
- Niklaus Wirth: Algorithmen und Datenstrukturen mit Modula-2, Stuttgart 1986, ISBN 3519022605
englisch
- R. Bayer, E. McCreight: Organization and Maintenance of Large 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
Internet
Tools zum Ausprobieren von B-Bäumen:
Siehe auch: Baum (Graphentheorie)