B⁺-Baum

Der B⁺-Baum ist eine in Datenbanken und Dateisystemen verwendete Daten- oder Indexstruktur. Sie ist eine Erweiterung des B-Baumes. Bei einem B⁺-Baum werden die eigentlichen Datenelemente nur in den Blattknoten gespeichert, während die inneren Knoten lediglich Schlüssel enthalten. Die Schlüssel in den Verzeichnisseiten bezeichnet man auch als Separatoren.

Der B⁺-Baum wird aus historischen Gründen manchmal auch als B*-Baum bezeichnet. B*-Baum bezeichnet jedoch auch eine B-Baum-Variante mit einem Mindestfüllgrad von 2/3 durch eine verbesserte Split-Strategie.

Ziel dieses Verfahrens ist es, die Zugriffszeiten auf die Datenelemente zu verbessern. Dazu muss man die Baumhöhe verringern, was bedeutet, dass der Verzweigungsgrad des Baumes wachsen muss. Da die maximale Speicherbelegung eines Knotens begrenzt ist, gewinnt man durch das Verlegen der Daten in die Blätter mehr Platz für Schlüssel bzw. Verzweigungen in den inneren Knoten. Dies gilt insbesondere bei der Speicherung komplexer Objekte, die deutlich mehr Speicher belegen als die Schlüssel oder auch nicht über eine feste Größe verfügen. Die reduzierte Baumhöhe impliziert auch weniger innere Knoten. Diese können so leichter im Hauptspeicher gehalten werden, was die Leistung im wahlfreien Zugriff steigert.

Ein weiteres Ziel kann sein, die Operation Bereichssuche zu verbessern, bei der alle Daten in einem gewissen Schlüsselintervall sequentiell durchlaufen werden. Werden die Daten nämlich ausschließlich in den Blättern abgelegt, muss der jeweils nächste Datensatz der Sequenz nicht wieder von der Wurzel aus gesucht werden. So muss für einen Komplettdurchlauf der Daten nur der erste Schlüssel gesucht werden, ein Großteil des Baumes wird nicht gelesen. Um Nachfolger und Vorgänger eines Blattknoten effizient (d. h. in konstanter Zeit) zu finden, müssen die Blätter in einer doppelt verketteten Liste miteinander verbunden sein. Dieses Feature wird häufig in die Definition des B⁺-Baumes mit aufgenommen.

Wesentlicher Vorteil eines externen Suchbaums (Daten nur in den Blättern) ist die Möglichkeit des Einsatzes von Sekundärindizes. Sie stellen einen weiteren – nach anderen Kriterien sortierbaren – Suchbaum auf denselben Daten zur Verfügung.