Embed Size (px)
Citation preview
Raumbezogene Zugriffsverfahren
• Das Grid-File• Der Lineare Quadtree
Motivation
• Bearbeitung einer mehrdimensionalen Suchanfrage soll in möglichst kurzer Zeit, zum Beispiel Punktsuche in einer Punktedatenbank, erfolgen.
Vorbereitung der Datenbank
Das Grid-File• Einteilung des n-dimensionalen
Datenraums mit orthogonalen Gitter
Das Grid-File
Zellen, denen die Dateneinträge (Punkte) zugeordnet werden
• Festlegung der maximalen Anzahl von Einträgen in einer Zelle
• Einteilung des n-dimensionalen Datenraums mit orthogonalen GitterEinfacheres Beispiel
Das Grid-File• Abspeicherung der Positionen der
Teilungslinien in zwei Vektoren:
x0 x1 x2
y0
y1
y2
x0
x1
x2
Xy0
y1
y2
Y
genauere Betrachtung
Das Grid-File• Abspeicherung der Zelleninhalte
in Buckets. Jede Zelle ist eindeutig einem
Bucket zugeordnet.
Das Grid-File
•Einem Bucket hingegen können aber mehrere Zellen zugeordnet sein.
• Die Buckets werden samt Inhalt auf einem Massenspeicher abgelegt.
Das Grid-File
• Zum Auffinden werden Pointer benötigt.
• Da jede Zelle einem Bucket zugeordnet ist, wird für jede Zelle ein Pointer zu ihrem Bucket angelegt.
Pointer
Pointer
Pointer
Pointer
• Die Pointer werden in einer Matrix ( „ Grid-Directory“) so abgespeichert, dass ihre Zeilen- und Spaltennummer mit der Zeilen- und Spaltennummer ihrer Zelle übereinstimmt.
P2,1 P2,2
P1,1 P1,2
1.2
2.22.1
1.1
• Ermittlung von Zeilen- und Spaltennummer der Zelle, in deren Bereich der Eintrag liegt.
• Das Auffinden von Einträgen umfasst also 3 Arbeitsschritte:1.2
• Aufsuchen des entsprechenden Pointers im Grid-Directory
1.2
P2,1 P2,2
P1,1 P1,2
• Das Auffinden von Einträgen umfasst also 3 Arbeitsschritte:
• Aufsuchen des Buckets, in dem der Eintrag liegt
1.2
P2,1 P2,2
P1,1 P1,2
• Das Auffinden von Einträgen umfasst also 3 Arbeitsschritte:
• Der Datenraum auch nicht.
• Hinweis: Die Zellen müssen nicht quadratisch sein.
• Einzelne Zellen können wieder als eigenständiger Datenraum aufgefasst werden, für den sich wieder ein Grid-File anlegen lässt.
• Grid-Files können auch n-dimensional sein
Aufbau eines Grid-Files und Abspeichern im Grid-File
• Die Größe der Buckets wird vor dem Aufbau des Grid-Files willkürlich festgelegt.
• Wird ein weiterer Eintag gemacht, so kann der Bucket überlaufen
• Im Folgenden sei die maximal mögliche Anzahl von Einträgen in einem Bucket zwei.
Aufbau eines Grid-Files und Abspeichern im Grid-File
• Einfacher Fall: Bucket enthält Einträge aus mehreren Zellbereichen: Für eine Zelle neues Bucket einrichten oder finden.
Aufbau eines Grid-Files und Abspeichern im Grid-File
• Einfacher Fall: Bucket enthält Einträge aus mehreren Zellbereichen: Für eine Zelle neues Bucket einrichten oder finden.
Aufbau eines Grid-Files und Abspeichern im Grid-File
• Schwieriger Fall: Einträge liegen im Bereich einer einzigen Zelle.
Teilung der Zelle, was eine weitere Teilung des gesamten Datenraumes bedeutet.
Aufbau eines Grid-Files und Abspeichern im Grid-File
• Schwieriger Fall: Einträge liegen im Bereich einer einzigen Zelle.
•
Teilung der Zelle, was eine weitere Teilung des gesamten Datenraumes bedeutet.
Richtig teilen
Löschen eines Eintrags
• Beim Löschen von Einträgen ergeben sich oft (fast) leere Buckets.
• Deswegen prüfen, ob die Buckets mit denen von benachbarten Zellbereichen vereinigt,
• oder Zellteilungen aufgehoben werden sollten.
Der Quadtree
• Aufteilen des Datenraums in der Mitte
• Es entstehen 4 Rechtecke: 0,1,2,3. 0
32
1
Der Lineare Quadtree
• Weitere Verfeinerung der Zellen:
Der Lineare Quadtree
• Somit entsteht eine Hierarchie wie in einer Baumstruktur.
Der Lineare Quadtree
• Mögliche Bezifferung der Quadranten:
11
00
2
2
3
3
00
00 01 02 03
01
02 03
10 11 12 13
10 11
12 13
20 21 22 23
20 21
22 2330 31 32 33
30 31
32 33
Der Lineare Quadtree
• Mögliche Bezifferung der Quadranten:
10
2 3
00 01
02 03
10 11
12 13
20 21
22 23
30 31
32 33
30300 301
302 303
Der Lineare Quadtree
• Beispiel: Quadtree der Tiefe 3
11
13
31
33
0
2
10
32
30
120 121
122 1230 2
10 11 13 30 31 32 33
120 121 122 123
Der Lineare Quadtree• Kein Quadrant hat mehr als 4 Einträge
11
13
31
33
0
2
10
32
30
120 121
122 123
Der Lineare Quadtree
• Die Blätter des Baumes erhalten dann Platz im Speicher für die abzuspeichernden Objekte.
0 2
10 11 13 30 31 32 33
120 121 122 123
Der Lineare Quadtree
• Für den Speicherzugriff werden Pointer mit den Nummern ihrer Blätter angelegt.
0 2
10 11 13 30 31 32 33
120 121 122 123
Der Lineare Quadtree• Es soll nun die Abspeicherung der Pointer in einem B+ Baum dargestellt werden.• Ein B+ Baum ist ein B-Baum, der durch die Art des Einfügens und Löschens
immer ausgeglichen ist.
12
B+-Baum
Der Lineare Quadtree
• Für die Sortierung der Pointer denkt man sich vor jede Nummer eine Null und ein Komma, z.B. 13 0,13 u.s.w., so dass z.B. gilt:
(0,)13 < (0,) 2oder
(0,) 102 < (0,) 11
Der Lineare Quadtree
• Für die Sortierung der Pointer denkt man sich vor jede Nummer eine Null und ein Komma, z.B. 13 0,13 u.s.w., so dass z.B. gilt:
13 < 2oder
102 < 11
Der Lineare Quadtree• Möglicher B+ Baum für unser Beispiel mit mehr als 2 (mit
Ausnahme der Wurzel) und weniger als 4 Einträgen pro Knoten:
0 10 11 120 121 122 123 13 2 30 31 32 33
31
2
10 121
Der Lineare Quadtree
• Weitere Möglichkeit:
0 10 11 120 121 122 123 13 2 30 31 32 33
10 121 2 31
122 123 13 2
Der Lineare Quadtree
• Die Pointer wurden dabei alle in der untersten Ebene abgespeichert.
0 10 11 120 121 30 31 32 33
10 121 2 31
Der Lineare QuadtreeEine Punktanfrage kann also in 3 Arbeitsschritten abgearbeitet werden:• 1.Berechne das Quadrat, in dem der gesuchte Eintrag liegt. Hierzu kann ein Hilfsgitter verwendet werden,
das überall gleichmäßig und mindestens so fein unterteilt ist wie das eigentliche Gitter. Dann wird einfach das entsprechende Quadrat des Hilfsgitters berechnet.
Tiefe : 3 Tiefe Hilfsgitter : 3
Der Lineare QuadtreeEine Punktanfrage kann also in 3 Arbeitsschritten abgearbeitet werden:• 1.Berechne das Quadrat, in dem der gesuchte Eintrag liegt. Hierzu kann ein Hilfsgitter verwendet werden, das überall mindestens so fein unterteilt ist
wie das eigentliche Gitter.• 2.Suche im B+ Baum den Pointer zu diesem Quadrat. Wenn kein Pointer die berechnete Nummer hat, kann der Pointer genommen werden, dessen
Nummer komplett in den Anfangsziffern der berechneten Nummer auftaucht. • 3. Hole die zum Quadrat abgespeicherten Daten aus dem Speicher.
Der Lineare QuadtreeEine rechteckige Bereichsanfrage kann durch eine Eigenart der gewählten Numerierung der Quadrate vereinfacht werden:
Die linke obere Ecke liege im Quadrat mit der Nummer A, und die rechte untere Ecke im Quadrat mit der Nummer B.
Der Lineare QuadtreeBeispiel:
A = 0
B = 31
11
13
31
33
0
2
10
32
30
120 121
122 123
Der Lineare QuadtreeDie Bereichsanfrage kann durch eine Eigenart der gewählten Numerierung der Quadrate vereinfacht werden:
Die linke obere Ecke liege im Quadrat mit der Nummer A, und die rechte untere Ecke im Quadrat mit der Nummer B.
Dann gilt für alle Quadrate, die den Suchbereich überlappen, das ihre Nummern zwischen A und B liegen.
Dies gilt auch beim Hilfsgitter.
Der Lineare QuadtreeEine Bereichsanfrage kann also in 4 Arbeitsschritten abgearbeitet werden:• 1. Berechne A und B (optional im Hilfsgitter).• 2. Berechne, welche Quadrate mit den Nummern zwischen A und B sich mit dem Suchbereich überlappen.• 3. Suche im B+ Baum die Pointer zu diesen Quadraten. Wenn kein Pointer die berechnete Nummer eines Quadrates hat, kann der Pointer genommen
werden, dessen Nummer komplett in den Anfangsziffern der berechneten Nummer auftaucht. • 4. Hole die zum Quadrat abgespeicherten Daten aus dem Speicher.
Der Lineare QuadtreeAbspeicherung• Die Abspeicherung von Objekten ist meist vergleichbar mit der beschriebenen Anfragetechnik. Allerdings gibt es Ausnahmen: • Der Inhalt eines Quadrates kann überlaufen. Dies hat eine Teilung des Quadrates zur Folge, wodurch 3 neue Quadrate entstehen, die wieder mit
Speicherbereichen und Pointern ausgestattet werden. • Das Einfügen von Pointern in den B+ Baum kann zum Überlauf eines Knotens führen. Die resultierende Umordnung wurde im Exkurs bereits
beschrieben.
Vielen Dank für die Aufmerksamkeit
Der Lineare Quadtree
• An dieser Stelle sei an einem Beispiel das Prinzip des B+Baums dargestellt :
7
2 3 7 9 10 13 15
Der Lineare Quadtree
• Wir setzen dabei die Anzahl maximal möglicher Einträge in einem Knoten auf vier.
7
2 3 7 9 10 13 15
Der Lineare Quadtree
• Wir fügen einen Eintrag mit dem Schlüssel 23 ein:
7
2 3 7 9 10 13 15
Der Lineare Quadtree
• Man stellt fest, das gilt 23 > 7 gilt. Somit ist zu prüfen, ob der Eintrag im rechten Teilbaum gemacht werden sollte.
7
2 3 7 9 10 13 15
Der Lineare Quadtree
• Das Blatt im rechten Teilbaum ist aber voll und muß daher geteilt werden.
7
2 3 7 9 10 13 15
Der Lineare Quadtree
• Das Blatt im rechten Teilbaum ist aber voll und muß daher geteilt werden.
7 13
2 3 7 9 10 13 15 23
Der Lineare Quadtree
• Dabei ist eine wichtige Eigenschaft des B+Baums festzustellen: er ist nach wie vor ausgeglichen!
7 13
2 3 7 9 10 13 15 23
Der Lineare Quadtree
• Somit kann also eine Suchanfrage an den B+ Baum immer in logarithmischer und konstanter Zeit bearbeitet werden!
7 13
2 3 7 9 10 13 15 23
Das Grid-File
• Nun soll untersucht werden, im Bereich von welcher Zelle sich ein gesuchter Eintrag befindet.
• Die Suche kann mit Hilfe der zwei Vektoren geschehen, sofern X- und Y-Koordinate bekannt sind.
? ?? ?
Das Grid-File
• Der Punkt habe die Koordinaten PX und PY.
PX , PY
x0
x1
x2
X • Nun wird anhand des X -Vektors untersucht, wieviele Gitternetzlinien links vom Punkt liegen,
• womit die Spaltennummer der Zelle ermittelt wäre.
Das Grid-File
Die gesuchte Zelle liegt in der 2ten Spalte des Datenraumes
• Es gelte als Beispiel: x0 < x1 <Px < x2.
PX , PY
x0
x1
x2
X
PX
Das Grid-File
Die gesuchte Zelle liegt in der 2ten Spalte des Datenraumes
• Es gelte als Beispiel: x0 < x1 <Px < x2.
x0 x1 x2
y0
y1
y2
PX
Das Grid-File
PX , PY
• Nun wird anhand des Y -Vektors untersucht, wieviele Gitternetzlinien unterhalb vom Punkt liegen,
• womit die Zeilennummer der Zelle ermittelt wäre.
y0
y1
y2
Y
• Achtung: die Zeilen werden von unten nach oben numeriert.
Das Grid-File
Die gesuchte Zelle liegt in der ersten Zeile des Datenraumes
• Es gelte als Beispiel: y0 < PY < y1 < y2.
PX , PY
PY
y0
y1
y2
Y
Das Grid-File
Die gesuchte Zelle liegt in der ersten Zeile des Datenraumes
• Es gelte als Beispiel: y0 < PY < y1 < y2.
x0 x1 x2
y0
y1
y2
PY
• Sie erhält als Nummer ihre Zeilen- und Spaltennummer.
• Somit ist die gesuchte Zelle gefunden .
x0 x1 x2
y0
y1
y2
PY
PX
1.2
Das Grid-File
• Auf diese Weise werden auch die übrigen Zellen numeriert.
x0 x1 x2
y0
y1
y2
1.2
Das Grid-File
2.22.1
1.1
• Da jede Zelle einem Bucket zugeordnet ist, wird für jede Zelle ein Pointer zu ihrem Bucket angelegt.
P2,2P2,1
P1,2P1,1
Aufbau eines Grid-Files und Abspeichern im Grid-File
• Schwieriger Fall: Die Einträge liegen nur im Bereich einer einzigen Zelle.
• Ein anderes Beispiel macht deutlich, das es Sinn macht, die Unterteilung so einzurichten, das möglichst viele bereits volle Zellen geteilt werden, damit für diese ggf. keine Unterteilung gemacht werden muß, wenn ihr Bucket überläuft.
Aufbau eines Grid-Files und Abspeichern im Grid-File
• Es entsteht eine Menge kaum gefüllter oder leerer Zellen, die kein eigenes Bucket haben sollten, um Speicherplatz zu sparen.
• Daher gilt es zu prüfen, ob der Zelleninhalt auch in einem Bucket der Nachbarzellen abgespeichert werden kann
