W i l l k o m m e n   b e i   [ www.mauspfeil.com ]
 
 



 

Wörterbuch der Bedeutung
<<Zurück
Bitte wählen Sie einen Buchstaben:
A, Ä | B | C | D | E | F | G | H | I | J | K | L | M | N | O, Ö | P | Q | R | S | T | U, Ü | V | W | X | Y | Z | 0-9

Suchen:

(Groß-/Kleinschreibung wird nicht unterschieden)

Google


B*-Baum

*** Shopping-Tipp: B*-Baum

Der '''B*-Baum''' ist eine Variante des B-Baum 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 B+-Baum befinden sich die eigentlichen Daten hier auch nur in den Blattknoten.

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.

Eigenschaften des B*-Baums
{{Überarbeiten}} 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.

Anwendungen
Die bekanntesten Anwendungen des B*-Baums sind in Dateisystemen. Als Beispiele sind Reiser4 von Namesys, sowie HFS und HFS+ von Apple zu nennen.

Verwandte Themen
* 2-3-4-Baum und B+-Baum B+-Baum sind weitere B-Baum-Varianten. Kategorie:Suchbaum Kategorie:Datenbank en:B*-tree

Weblinks
Tools zum Ausprobieren von B*-Bäumen:
http://slady.net/java/bt - B-Baum Java Applet (nicht B*-Baum)




[Der Artikel zu B*-Baum stammt aus dem Nachschlagewerk Wikipedia, der freien Enzyklopädie. Dort findet sich neben einer Übersicht der Autoren die Möglichkeit, den Original-Text des Artikels B*-Baum zu editieren.
Die Texte von Wikipedia und dieser Seite stehen unter der GNU Free Documentation License.]

<<Zurück | Zur Startseite | Impressum | Zum Beginn dieser Seite