Databases Reference
In-Depth Information
lichkeit besteht darin, die Daten zu sortieren. Betrachten wir die folgende einfache
Tabelle:
create table personen(
id int generated always as identity primary key,
name varchar(20),
ort varchar(20)
)
Wenn wir die Daten jetzt auf der Platte etwa nach der Spalte
ort
sortieren, können
wir annehmen, dass die Daten unserer Tabelle
personen
auf die Seiten P
1
, . . . , P
n
verteilt sind. Außerdem ist der Wert von
ort
für alle Datensätze aus der Seite P
i
lexikographisch kleiner oder gleich den Datensätzen aus der Seite P
i
+
1
. Innerhalb
der Seiten sind die Datensätze ebenfalls sortiert. Für die Suche in einer sortierten
Liste gibt es sehr effiziente Verfahren wie die binäre Suche (siehe auch [Knu98]),
die wir uns jetzt genauer ansehen wollen.
Wenn das RDBMS etwa die folgende Abfrage ausführen soll:
select
*
from personen
where ort='Entenhausen'
wird zunächst die Seite P
n
=
2
untersucht.
Werden wir auf der Seite fündig, hat die Suche bereits ein Ende.
Wenn der kleinste Wert der Spalte
ort
für die Datensätze dieser Seite kleiner
als
'Entenhausen'
ist, untersuchen wir die Seiten P
1
, . . . , P
n
=
2
1
.
Wenn der größte Wert der Spalte
ort
für die Datensätze dieser Seite größer als
'Entenhausen'
ist, fahren wir mit P
n=2+1
, . . . , P
n
fort.
Wenn keiner der drei Fälle eintritt, ist der Wert nicht vorhanden.
In diesen halbierten Seitenlisten machen wir genauso weiter: Wir betrachten die
mittlere Seite und halbieren weiter, wenn wir nicht fündig geworden sind. Auch
bei der binären Suche müssen Seiten in den Arbeitsspeicher gelesen werden, man
kann aber nachweisen, dass die Anzahl gelesener Seiten proportional zu log n und
damit weitaus geringer als n ist.
Das Verfahren hat jedoch zwei gravierende Nachteile, die es für den Einsatz im
RDBMS disqualifizieren:
1.
Die Daten können nur nach einer einzigen Spalte (oder einer Kombination von
Spalten) sortiert werden. Weil die Daten nicht nach der Spalte
id
sortiert sind,
müssen Abfragen wie
select
*
from personen
where id=4711
