B*-Baum

Der B*-Baum ist eine Daten- bzw. Indexstruktur in der Informatik und eine Variante des B-Baums, die 1973 von Donald Knuth vorgeschlagen wurde und sich vom B-Baum in der Forderung unterscheidet, dass Knoten mindestens zu 2/3 gefüllt sein müssen (anstatt nur 1/2 gefüllt). Dies wird vor allem durch eine veränderte Split-Strategie erreicht, bei der 2 volle Knoten auf 3 Knoten mit einem Füllgrad von 2/3 aufgeteilt werden.

Der Name wird aus historischen Gründen oftmals für den B+-Baum verwendet, eine andere B-Baum-Variante, bei der Daten nur in den Blattknoten gespeichert und durch die Verkettung der Blattknoten Bereichsanfragen effizienter unterstützt werden.

  1. ↑ Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, 1973, ISBN 81-317-0983-3, S. 488 (englisch).
  2. ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7 (englisch).
Dieser Artikel wurde von Wikipedia herausgegeben. Der Text ist unter Creative Commons Attribution-Share Alike 4.0 verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.