B*-Baum
aus Wikipedia, der freien Enzyklopädie
In der Informatik ist der B*-Baum eine Daten- bzw. Indexstruktur, die z. B. im Reiser4-Dateisystem zum Einsatz kommt. Er ist eine Variante des B-Baumes, bei dem die Bedingung an die Elementzahl der Knoten dahin abgeändert wird, dass sie mindestens zu 2/3 gefüllt sein müssen. Ebenso wie beim B+-Baum befinden sich die eigentlichen Daten hier auch nur in den Blattknoten.
Inhaltsverzeichnis |
[Bearbeiten] Aufbau und Speicherplatzausnutzung
Bei einem B*-Baum der Ordnung 
verfügt die Wurzel des Baumes über bis zu 2k Einträge und jeder Knoten über (4 / 3)k bis 2k Einträge. Jeder Blattknoten hat 
bis 
Einträge.
Bezeichnet 2k die Maximalzahl der Elemente pro Knoten, muss ein Knoten mindestens (4 / 3)k Elemente und maximal 2k Elemente enthalten. Die Knoten werden folglich immer zu mindestens 2/3 gefüllt, im Gegensatz zum normalen B-Baum, dessen Knoten mindestens zu 1/2 gefüllt sind. Dies garantiert eine bessere Speicherplatzausnutzung sowie eine geringere Worst-Case-Höhe des Baumes, also die Höhe für den Fall minimal gefüllter Knoten. Nachteilig ist, dass ein Überschreiten der Maximal- bzw. Minimalzahl der Elemente je Knoten nach den Operationen Einfügen und Löschen häufiger auftritt als bei B-Bäumen, und dass sich das Beheben der Überschreitung im Mittel weiter durch den Baum zieht.
[Bearbeiten] Eigenschaften des B*-Baums
B*-Bäume sind ein plattenorientierter (Sekundärspeicher) abstrakter Datentyp, im Gegensatz beispielsweise zu Binär-Bäumen, die einen hauptspeicherorientierten abstrakten Datentyp realisieren.
Die Besonderheit von B*-Bäumen liegt darin, dass sie die eigentlichen Nutzdaten zusammen mit ihrem (Schlüssel-)Index nicht mehr in allen Knoten (innere Knoten des Baumes) und Blättern (unterste oder oberste, äußerste Ebene des Baumes) des Suchbaumes ablegen, sondern nur noch in den Blättern. Dadurch entsteht ein höherer Verzweigungsgrad.
Im Vordergrund der B-Bäume und B*-Bäume steht die (Such-)Geschwindigkeit.
Bei der Suche nach einem Element innerhalb des Suchbaumes müssen alle Ebenen des Suchbaumes durchlaufen und an den Knoten entsprechende Vergleiche durchgeführt werden, damit schließlich das Element (hoffentlich) gefunden wird.
Da bei B- und B*-Bäumen die Daten im Sekundärspeicher liegen ist ein Zeitfaktor entscheidend: der Plattenzugriff. Daher steht bei der Optimierung der Suche nach einem bestimmten Element innerhalb des Suchbaumes die Plattenzugriffzeit im Vordergrund.
In B*-Bäumen werden die eigentlichen Nutzdaten von ihren Metadaten getrennt. Im Suchbaum werden also nur noch die Indizes gespeichert. Die Nutzdaten liegen zusammen mit ihren zugehörigen Indizes in den äußersten Blättern. Dadurch entsteht zwar Redundanz, der Speicherverbrauch wird jedoch durch die Nutzdaten dominiert, nicht durch die Indizes und Zeiger auf Unterbäume. Daher entsteht nur ein geringer Mehrverbrauch.
Dadurch ist die Suche auf den Index-Knoten mit weniger Zugriffen auf den langsamen Sekundärspeicher möglich, eventuell kann der Index (oder Teile davon) sogar im Hauptspeicher gehalten werden. Ein Zugriff auf den Sekundärspeicher ist dann erst für das Laden der Nutzdaten erforderlich.
[Bearbeiten] Anwendungen
Die bekanntesten Anwendungen des B*-Baums sind in Dateisystemen (z. B. Reiser4, HFS und HFS+ von Apple).
Weiterhin sind B*-Bäume die heute gebräuchlichste Index-Struktur in allen bekannteren Datenbanksystemen wie Oracle, MS-SQL, MySQL-InnoDB. Wobei MySQL-Tabellen im MyISAM-Format indexsequentielle Datenbanken verwenden.
[Bearbeiten] Verwandte Themen
- 2-3-4-Baum und B+-Baum sind weitere B-Baum-Varianten.
