B+-Baum
Der B+-Baum 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.
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.
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.
Sei s der Schlüssel des aktuellen Datensatzes der Sequenz. Ist dieser Schlüssel nicht an rechtester Stelle in einem Blatt abgelegt, so befindet sich sein nachfolgender Datensatz (mit dem Schlüssel s') im selben Blatt rechts neben s. Ist der Schlüssel doch an rechtester Stelle eines Blattes gespeichert, müsste die Suche wiederum bei der Wurzel beginnen. Dies kann vermieden werden, indem man die Blätter des B+-Baumes, wie beim B*-Baum, in einer linearen Liste miteinander verbindet. 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 den selben Daten zur Verfügung.
Siehe auch
- 2-3-4-Baum und B*-Baum sind weitere B-Baum-Varianten.