Algorithmen und Datenstrukturen in C: B-Bäume
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. Das Einfügen, Suchen und Löschen von Daten in B-Bäumen ist in amortisiert logarithmischer Zeit möglich. B-Bäume wachsen – und schrumpfen – anders als die meisten Suchbäume von den Blättern hin zur Wurzel. 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. Die Erfinder lieferten keine Erklärung über die Herkunft des Namens B-Baum. Die häufigste Interpretation ist, dass B für balanciert steht. Weitere Interpretationen sind B für Bayer, Broad, Bushy, oder Boeing, da Rudolf Bayer für Boeing Scientific Research Labs gearbeitet hat.
B-Baum steht nicht für Binärbaum. Ein Knoten in einem Binärbaum besitzt höchstens zwei Verweise auf Kindknoten, während in einem B-Baum ein Knoten eine Vielzahl von Verweisen auf Kindknoten speichern kann.
<< AVL-Bäume | Inhaltsverzeichnis | Laufzeitberechnung >>