Databases Reference
In-Depth Information
74
85
31
42
80
95
12 23
31
42
74
80
85 90
95
12
Donald
Abbildung 20.4:
Beispiel für einen B
+
-Baum
Wenn die Spalte
id
indiziert ist, muss nur der passende Einstiegspunkt in die
verkettete Liste gefunden werden; in diesem Fall ist das der kleinste Eintrag in
einer Indexseite, der mindestens den Wert
23
hat. Die Indexseiten können in der
Reihenfolge ihrer Verkettung durchlaufen werden, solange das Prädikat
id<=42
erfüllt ist. So kann jeder Datensatz, der zu einem der indizierten Werte 23, 24, ...,
24 gehört, mit einem weiteren Zugriff gefunden werden.
Die nächste Ebene im Index indiziert die Blätter. Seiten, die keine Blätter sind,
heißen
innere Knoten
. Jeder Eintrag in einem inneren Knoten enthält einen Wert
v
sowie eine Referenz auf eine Indexseite in Form einer RID. Die indizierten Werte
können also mehrfach im Baum auftreten: einmal in den Blättern und einmal in
einem inneren Knoten. Zum Wert
v
gehören im inneren Knoten zwei Referenzen
auf eine Indexseite:
Die Referenz links von
v
verweist auf ein Blatt, dessen Einträge alle kleiner als
v
sind.
Die Referenz rechts von
v
liefert ein Blatt mit Einträgen, die alle größer oder
gleich
v
sind.
Zu jedem Blatt gibt es also einen Eintrag in der untersten Ebene der inneren Kno-
ten. Die Knoten dieser Ebene über den Blättern werden von der nächsthöheren
Ebene indiziert. Auch wenn diese Ebene in unserem speziellen Fall aus genau
einer Seite besteht, werden die Knoten trotzdem als innere Knoten bezeichnet.
Die Knoten der Ebene i verwalten die Knoten der darunterliegenden Ebene i+1.
Dieses Spielchen treiben wir so weit, bis die ganze Ebene nur noch aus einem
einzigen Knoten besteht. Dieser Knoten wird auch als
Wurzel
bezeichnet.
