B*-Baum
aus Wikipedia, der freien Enzyklopädie
Der B*-Baum 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 (k,k*) verfügt die Wurzel des Baumes über einen bis 2k Einträgen und jeder Knoten über (4/3)*k bis 2k Einträge. Jeder Blattknoten hat (4/3)*k* bis 2k* Einträge.
Bezeichnet 2k die Maximalzahl der Elemente pro Knoten, muss ein Knoten mindestens (4/3)*k Elemente und maximal 2*k Elemente enthalten. Die Knoten werden folglich immer zu mindestens 2/3 gefüllt, im Gegensatz zum normalen B-Baum, welcher mindestens zu 1/2 gefüllt ist. 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
| Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf bitte mit ihn zu verbessern und entferne anschließend diese Markierung. |
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 nicht mehr zusammen mit ihrem (Schlüssel-)Index 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. Sicherlich ist die CPU-Zeit auch relevant, bewegt sich aber im Vergleich zur Plattenzugriffszeit in einer so geringen Größenordnung, dass sie ihr die Relevanz raubt.
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. Als Beispiele sind Reiser4 von Namesys, sowie HFS und HFS+ von Apple zu nennen.
[Bearbeiten] Verwandte Themen
- 2-3-4-Baum und B+-Baum sind weitere B-Baum-Varianten.
[Bearbeiten] Weblinks
Tools zum Ausprobieren von B*-Bäumen:
- http://slady.net/java/bt - B-Baum Java Applet (nicht B*-Baum)
