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.