Databases Reference
In-Depth Information
nach wie vor mit einem Table-Scan bearbeitet werden.
2.
Wenn Datensätze hinzugefügt werden, müssen die Seiten reorganisiert wer-
den. Wenn der neue Datensatz der Reihenfolge der Orte entsprechend etwa zu
Seite P
i
gehört und P
i
bereits voll ist, müssen Daten in der Seite P
i+1
verscho-
ben werden, um Datensätze aus der Nachbarseite P
i
aufzunehmen. Möglich
sind dann in Folge auch Reorganisationen von P
i+2
bis P
n
. Da diese Reorgani-
sationen wieder Transporte zwischen der Platte und dem Arbeitsspeicher nach
sich ziehen, können selbst einfache Einfügeoperationen dramatische Laufzei-
ten haben.
Wenn wir mit mehr als einem Index arbeiten wollen, nutzt das RDBMS nicht die
Datenseiten, sondern extrahiert und kopiert die Werte, die es indiziert. Wenn wir
also einen Index für die Spalte
ort
der Tabelle
personen
aufbauen, durchsucht
das RDBMS alle Datensätze und kopiert die Werte der Spalte
ort
. Damit wir unse-
re Datensätze - ähnlich wie die Seiten im Buch - wiederfinden, wird der indizierte
Wert zusammen mit der RID (siehe Abschnitt 20.2) gespeichert. In unserer redun-
danten Datenstruktur verwalten wir also Paare aus Werten und RIDs. Damit der
Index nicht immer aufs Neue erzeugt wird, sollte er auf die Festplatte geschrie-
ben werden. Die Paare werden zu so genannten
Indexseiten
zusammengefasst,
die dann wie die Datenseiten zwischen Cache und Festplatte transportiert wer-
den.
Wir können für die gleiche Tabelle mehrere Indexe anlegen; es kann einen für die
Spalte
ort
und einen anderen für
id
geben. Jedem der beiden Indexe entspricht
eine andere Menge von Indexseiten. Die Organisation der Datensätze wird davon
nicht berührt.
Da die Indexseiten nur einen Teil der Informationen der zugehörigen Datensätze
enthalten, referenzieren Indexseiten in der Regel erheblich mehr Datensätze, als in
einer einzigen Datenseite enthalten sind. Bereits aufgrund dieser Eigenschaft wer-
den bei der sequentiellen Suche im Index längst nicht mehr so viele Datensätze in
den Arbeitsspeicher transportiert wie beim Table-Scan.
Wir können die Einträge in den Seiten eines Index jetzt auch sortieren und zu ei-
nem gesuchten Wert mit Hilfe der binären Suche in dieser sortierten Liste schnell
passende Indexpaare und dann auch die zugehörigen Datensätze finden. Die Pro-
bleme bleiben aber die gleichen, wie bei einer Sortierung der Datenseiten: So-
bald es Änderungen im Datenbestand gibt, muss der Index reorganisiert werden.
Wenn ein neuer Datensatz eingefügt wird, muss der zugehörige Indexeintrag ein-
sortiert werden. Wenn es auf der Indexseite, in die der Eintrag gehört, keinen Platz
mehr gibt, muss ein Teil des Datenbestandes auf der Festplatte verschoben wer-
den; unter Umständen eine langwierige Operation.
Für speicherresidente Daten gibt es eine Vielzahl von Datenstrukturen (siehe
[Knu98]), die eine effiziente Suche ermöglichen. Bei Daten, die auf Festplatten lie-
gen, sieht die Sache schon anders aus. Bayer und McCreight [Bay72] entwickelten
Anfang der 1970er-Jahre mit dem B-Baum eine Datenstruktur speziell für externe
