| |
9
Der Algorithmus teilt das Einheitsquadrat in vier Quadranten von gleicher Größe auf, welche
kanonisch nummeriert sind von null bis drei. (sieh Abb. 3.1)
Abbildung 3.1 Z-Ordering in Punktdatenbanksystemen
Wir notieren die Zahl des Quadranten und teilen diesen Quadranten in seine vier unter Quadranten.
Das wird rekursiv wiederholt bis eine bestimmte Grundauflösung erreicht wurde. Die feste Zahl der
rekursiven Wiederholung wird als Auflösungsniveau „g“ bezeichnet. Dann hören wir auf und nutzen die
erhaltene Reihenfolge von „g Ziffern“ (genannt Quadrantenreihenfolge) als Anordnungsschlüssell für
die
P
unkte ( wir ordnen lexikographisch). Jede Quadrantenreihenfolge bezeichnet eine Region des
Datenraumes, die wir als Element bezeichnen. Z.B. steht die Reihenfolge <00> für ein Element mit der
Seitenlänge 0.25, welches die untere linke Ecke in dem Datenraum berührt. Elemente bei der
Basisauflösung, welche durch die Quadrantenreihenfolge mit der Länge „g“ repräsentiert werden,
werden Zellen genannt. Wenn ein Element e1 in einem anderen Element e2 enthalten ist, dann ist die
dazugehörige Quadrantenreihenfolge Q(e2 ) ist ein Präfix von Q(e1 ). Je länger ein Quadranten-
reihenfolge ist, desto kleiner ist das dazugehörige Element. In dem Einheitsquadrat wird die Fläche
von einem Element durch eine Reihenfolge mit der Länge „l“ (1/4)l repräsentiert. In einem
Punkdatenbanksystem werden nur Zellen mit der Basisauflösung genutzt. Deshalb besitzen alle
Quadrantenreihenfolgen die gleiche Länge und wir können die Quadrantenreihenfolgen als Ziffern
interpretieren , die in einem Vierergruppensystem (Basis 4) vorkommen.
ie Interpretierung von
Reihenfolgen als Ziffern erleichtert ihr Management im Index und verändert nicht die Reihenfolge der
Punkte, weil die lexikographische Ordnung der weniger gleichen Beziehung von Ziffern entspricht. Die
Punkte werden in einer reihenfolgeerhaltenden und eindimensionalen Indexstruktur wie dem B+-Baum
[Kem 99]* gesteuert.
3.3.2 Anfrageablauf im Z-Ordeing
Wir nehmen an, eine Fensteranfrage mit einem spezifisierten Fenster. Der Datenraum ist unterteilt in
seine vier Quadranten. Jeder Quadrant wird auf Überlappung mit der Anfragefenster überprüft. Wenn
der Quadrant sich nicht mit dem Anfragefenstern überlappt, muss nichts getan werden. Wenn der
Quadrant komplett in dem Anfragefenstern eingeschlossen ist, müssen wir alle Punkte von der
0
1
3
2
0
1
3
20
22
23
212
210
211
212
|  |
|
| |
|
|
