77 132
54 69 88 99
40 43 52 59 62 70 74 75 82 84 87 89 90 97
...
...
Abbildung 7.2: B-Baum
• jede Seite entweder eine Blattseite ohne Nachfolger ist oder i+1 Nachfolger,
hat wobei i die Anzahl der Vergleichselemente ist, und
• alle Blattseiten auf der gleichen Stufe liegen.
Ein B-Baum zeichnet sich durch eine Reihe von charakteristischen Eigenschaf-
ten aus. Wenn n Datensätze in der Hauptdatei gespeichert sind, und ein Kno-
tenzugriff einen Seitenzugriff bedeutet, werden beim Suchen daher log
m
(n) Sei-
tenzugriffe benötigt (Länge des Pfades von der Wurzel zu einem Blatt).
Das heißt, dass das Balancierungskriterium zu einer nahezu vollständi-
gen Ausgeglichenheit führt. Einfügen, Löschen und Suchen sind mit O(log
m
(n))
realisierbar. Die Speicherplatzausnutzung beträgt mindestens 50 %, wird die
Wurzel außer Acht gelassen.
7.2.1 Der B
+
-Baum
Der B
+
-Baum ist die bekannteste Variante des B-Baums, und in vielen Sys-
temen im Einsatz. Im Gegensatz zum B-Baum sind die referenzierten Tupel
bzw. die TIDs nur in den Blättern gespeichert. Die Blätter sind untereinander
verkettet für den sequenziellen (Bereichs-) Durchlauf.
82 132
59 70 89 99
40 43 52 59 62 70 74 75 82 84 87 89 90 97
...
...
Abbildung 7.3: B
+
-Baum
7.2 B-Bäume und Varianten 199
Get Data Warehouse Technologien now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
