B+-Baum

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Der korrekte Titel dieses Artikels lautet „B⁺-Baum“. Diese Schreibweise ist aufgrund technischer Einschränkungen derzeit nicht möglich.

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 in einer linearen Liste miteinander verbindet. Dieses Feature wird häufig in die Definition des B⁺-Baumes mit aufgenommen.