Unter der Haube - Grundkurs Datenbanksysteme - page 313

Speichermedien. Im Laufe der Zeit wurden einige Varianten entwickelt, deren be-
kanntester Vertreter der B + -Baum ist - bis heute die Standard-Datenstruktur zur
Indizierung von Datenbeständen. Wie diese Art Baum aufgebaut ist und welche
Algorithmen ein schnelles Suchen, Löschen und Einfügen ermöglichen, erfahren
wir im folgenden Abschnitt.

B + -Bäume

20.8

Mit Hilfe der naiven Indizierungsverfahren, die wir bisher gefunden haben, kön-
nen wir Daten zwar sehr schnell, also in log n Verarbeitungschritten finden, wenn
es aber um das Einfügen neuer Datensätze geht, müssen wir im schlechtesten Fall
damit rechnen, dass alle Indexseiten in den Arbeitsspeicher gelesen werden.
B + -Bäume sind eine Datenstruktur, bei der wir diese Kröte nicht schlucken müs-
sen: Für jede der vier Operationen

Suchen
Ändern
Löschen
Einfügen
reichen garantiert log n Verarbeitungsschritte. Die Basis des Logarithmus ist dabei
so groß, dass es in der Praxis reicht, eine Handvoll Seiten zu lesen oder zu schrei-
ben. Wir analysieren zunächst die Struktur dieser Bäume, erarbeiten uns dann die
Algorithmen zum Suchen und Einfügen von Einträgen und überzeugen uns an
einem konkreten Beispiel von der Effizienz der Datenstruktur.

20.8.1 Idee
Einen ersten Überblick über die Struktur eines B + -Baumes gibt uns Abbil-
dung 20.4.
Die Werte der indizierten Spalte finden wir sortiert in der untersten Ebene einer
baumförmigen Struktur. Die Indexseiten, die zur untersten Ebene gehören, wer-
den auch Blätter genannt. Die Abbildung repräsentiert die Wirklichkeit nur unge-
nügend, da eine typische Indexseite Hunderte von Einträge enthält. Die Einträge
in einem Blatt sind sortiert. Jeder der Einträge referenziert - wie gehabt - einen
Datensatz. In der Abbildung ist das exemplarisch für den Datensatz mit der ID 12
dargestellt. Der Pfeil zum zugehörigen Datensatz (12, 'Donald') repräsen-
tiert die RID, die zusammen mit dem Wert 12 im Blatt steht. Uns fällt auf, dass die
Blätter wie bei einer verketteten Liste miteinander verknüpft sind. Die Verkettung
hilft dem RDBMS bei der Bearbeitung von Abfragen wie

select * from personen where id>=23 and id<=42