Databases Reference
In-Depth Information
Hinweis
Die Ordnung eines B
+
-Baumes wird in der Literatur nicht einheitlich
definiert. Teilweise bezeichnet die Ordnung die maximale Anzahl von
Einträgen je Knoten, gelegentlich auch die Anzahl der Nachfolger.
20.8.4 Suchen
Bei der Suche in einem B
+
-Baum ist ein Wert gegeben. Die Suche ist erfolglos,
wenn der Wert in keinem Blatt des Baumes gefunden wird. Wenn es ein Blatt gibt,
das den Wert enthält, dann war die Suche erfolgreich, und ihr Ergebnis besteht
aus dem zugehörigen Datensatz.
3
Mit der Suche nach einem Wert
k
fangen wir in der Wurzel des B
+
-Baumes an.
Da die Werte in den Knoten aufsteigender Reihenfolge sortiert sind, können wir
leicht den größten Wert
v
suchen, der kleiner oder gleich
k
ist. Für den Ausgang
dieser Suche gibt es zwei Möglichkeiten:
Wenn die Suche in der Wurzel erfolgreich und
k
im Baum vorhanden ist, dann
gehört k zu dem Teilbaum, dessen Wurzel der rechte Nachfolger von
v
ist.
Die Suche ist in der Wurzel genau dann erfolglos, wenn
k
kleiner als alle Wer-
te der Wurzel ist. Wenn
k
sich überhaupt im Baum befindet, dann nur in dem
Teilbaum, dessen Wurzel der linke Nachfolger des minimalen Wertes der Wur-
zel ist.
Der erste Fall tritt im Beispiel aus Abbildung 20.4 ein, wenn wir den Wert 80 su-
chen. Der passende Wert in der Wurzel ist 74. Wenn 80 also im Baum enthalten
ist, dann in dem Teilbaum, der zum rechten Nachfolger der 74 gehört. Der zweite
Fall greift, wenn wir etwa den Wert 25 suchen. Da alle Werte in der Wurzel größer
als 25 sind, wählen wir den linken Nachfolger von 74.
Auf diese Weise haben wir einen Teilbaum ermittelt, in dessen Wurzel wir mit
dem gleichen Verfahren weiter suchen können. Wenn wir das Verfahren fortsetzen,
kommen wir irgendwann zu einem Blatt. Falls wir
k
dort finden, können wir auch
auf den zugehörigen Datensatz zugreifen. Wenn
k
sich nicht im Blatt befindet, ist
er sicher nicht im Baum vorhanden.
Eine vollständige Suche machen wir uns ebenfalls an Abbildung 20.4 klar. Wenn
wir den Wert 90 suchen, folgen wir in der Wurzel dem rechten Nachfolger der 85
und dann in der nächsten Ebene dem linken Nachfolger der 95. Wir landen im
Blatt mit den Werten 85 und 90 und finden den Wert, dessen zugehörige RID uns
zum gesuchten Datensatz führt.
Da wir jede Ebene des Baumes nur einmal besucht haben, ist die Anzahl der gele-
senen Seiten wieder sehr gering.
3
Natürlich können auch mehrere „Treffer“ gefunden werden. Der Algorithmus ändert sich aufgrund
dieser Möglichkeit aber nicht.
