Namenschaos um den B*-Baum

Gerade in dem Fachgebiet, in dem eindeutige Bezeichnungen so wichtig sind, wie in keinem anderen, dem Fachgebiet Informatik, sollte man doch eigentlich davon ausgehen, dass sich bei der Benennung von Entwicklungen Mühe gegeben wird, einen eindeutigen Namen zu wählen. Bei Recherchen im Rahmen eines Seminars Indexstrukturen für Datenbanken musste ich mich leider eines Besseren belehren lassen:

Eine wichtige Datenstruktur für Datenbanken sind die B⁺-Bäume. Diese sind eine Variante der B-Bäume von Rudolf Bayer. Sie wurden 1973 von Donald Ervin Knuth vorgeschlagen, jedoch ohne ihnen einen Namen zu geben. In der selben Veröffentlichung beschrieb er auch die B*-Bäume. 1974 verwendet Hartmut Wedekind den Namen B*-Baum bei der ausführlichen Beschreibung der B⁺-Bäume. Diesen Namen bekamen sie erst 1979 zur besseren Unterscheidbarkeit von Douglas Comer. 1977 jedoch übernahm Rudolf Bayer den Begriff B*-Baum für die später als B⁺-Baum bezeichnete Variante. Die Folge: In Literatur und Lehre kursieren beide Datenstrukturen unter beiden Namen. Beschäftigt man sich nur oberflächlich mit dem Thema sorgt das möglicherweise für erhebliche Verwirrung. Letztlich bleibt nur, sich im jeweiligen Kontext zu orientieren, welche der beiden Strukturen gemeint ist. Damit aber nicht genug. Zur Pfadsuche in Graphen gibt es den sogenannten B*-Algorithmus. Dieser Algorithmus baut einen Suchbaum auf. Schon Comer machte sich in seiner Veröffentlichung geradezu darüber lustig, dass dieser Suchbaum ebenfalls als B*-Baum bezeichnet wird. Soviel zum Thema Eindeutigkeit.

Literatur

Knuth, D. E. The Art of Computer Programming, Volume III: Sorting and Searching Addison-Wesley, 1973, Seite 476-479

Comer, D. Ubiquitous B-Tree ACM Computing Surveys 11, 1979, 2, 121 – 137

Wedekind, H. On the Selection of Access Paths in a Data Base System IFIP Working Conference Data Base Management, 1974, 385-397

Bayer, R. & Unterauer, K. Prefix B-Trees ACM Trans. Database Syst., 1977, 2, 11-26