Upload
kiefer-schlabach
View
111
Download
0
Embed Size (px)
Citation preview
FH-Hof
Der R-Baum
Richard Göbel
FH-Hof
Verallgemeinerte Suchanfragen
Form der Suchanfrage
al1 column1 au1
AND al2 column2 au2
. . .
AND ald columnd aud
Werte der relevanten Spalten sind total
geordnet (praktisch immer der Fall)
Weitere Analyse ausschließlich mit Zahlen
(o.B.d.A)
FH-Hof
1 2 3 4 5
1
2
3
4
5
X
Y
Einträge als Punkte im mehrdimensionalen Raum
. . . X Y . . .
. . . 2 1 . . .
. . . 2 3 . . .
. . . 3 2 . . .
. . . 4 3 . . .
. . . 4 5 . . .
FH-Hof
Suchbereich im mehrdimensionalen Raum
2 X 4 AND 2 Y 3
1 2 3 4 5
1
2
3
4
5
X
Y
FH-Hof
Grundlagen einer Indexstruktur
Form der Suchregion
Rechteck für zwei Dimensionen
Quader für drei Dimensionen
Hyperquader für vier oder mehr Dimensionen
Knoten der Indexstruktur repräsentieren
ebenfalls Regionen im mehrdimensionalen
Raum
Die Region eines Knoten enthält die Regionen
aller Kinder
Verwendung kompatibler Regionen für die
Knoten der Indexstruktur (Hyperquader)
FH-Hof
Beispiel für einen zweidimensionale Index
X
Y
FH-Hof
Basis für ein Suchverfahren
Start an der Wurzel der Indexstruktur
Suche an Kinderknoten fortsetzen deren Region
sich mit der Suchregion überlappt
Ausgehend von den Blattknoten wird die
Suchbedingung für die Einträge überprüft
FH-Hof
Wann überlappen sich zwei Regionen?
Region a:
al1 c1 au1 . . . ald cd aud
Region b:
al1 c1 au1 . . . ald cd aud
Notwendige und hinreichende Bedingung für
die Überlappung:
Jede Untergrenzen der Dimension einer Region
muss kleiner oder gleich der Obergrenze der
zugehörigen Dimension der anderen Region
sein.
al1 bu1 bl1 au1 . . . ald bud bld aud
FH-Hof
R-Baum
A. Guttman 1984:"R-Trees: A Dynamic Index Structure for Spatial
Searching”, Proc. ACM SIGMOD Conference, Boston,
pages 47 - 57, 1984
Viele Verbesserungen und Erweiterungen, z.B.:
1987: Sellis, Roussopoulos, Faloutsos: R+-Tree
1990: Beckmann, Kriegel, Schneider, Seeger: R*-tree
1996: Berchtold, Keim, Kriegel: X-Tree:
1997: Leutenegger, Edgington, Lopez: STR Tree
Packing
Verschiedene Implementierungen in
Datenbanksystemen in den letzten 10 Jahren
FH-Hof
Eigenschaften des R-Baums
Baum mit Verzweigungsgrad größer als 2
Knoten des Baumes werden Blöcken der
Festplatte zugeordnet
Der R-Baum ist vollständig balanciert
Algorithmen für das Einfügen und Löschen sind
ähnlich wie beim B-Baum
Suchverfahren entspricht dem allgemeinen
Suchansatz
FH-Hof
Einfügen eines Punktes
Bestimme mit Hilfe des Suchverfahrens ein
Blattknoten für den neuen Punkt.
Falls verschiedene Pfade existieren (aufgrund
von Überlappungen) dann wähle einen Pfad
aus.
Falls kein passender Nachfolger bei der Suche
gefunden wird:
Vergrößere den Hyperquader für den Nachfolger
für den die Vergrößerung minimal ist.
Falls ein Blattknoten nicht mehr ausreichend
Kapazität enthält:
Spalte den Knoten und ggf. Elternknoten auf.
FH-Hof
Löschen eines Punktes
Bestimme mit Hilfe des Suchverfahrens alle
Blattknoten für den zu löschenden Punkt
Lösche den Punkt aus einem Blattknoten.
Verkleinere bei Bedarf alle Hyperquader auf
dem Pfad zu dem betroffenen Blattknoten.
Unterschreitet der Blattknoten die minimale
Anzahl von Elementen, dann lösche diesen
Blattknoten:
verteile die Einträge auf Geschwisterknoten
oder füge die betroffenen Punkte neu ein
FH-Hof
Optionen für die Implementierung
Auswahl eines Pfades für das Einfügen
Aufteilen eines Knotens
Verteilen der Einträge für das Löschen eines
Knotens
Reorganisation eines Baums?
FH-Hof
Kriterien für die Optimierung eines R-Baums
Überlappungen:
Anzahl der Überlappungen minimieren
Volumen der Überlappungen minimieren
Volumen der Knoten minimieren
Abweichungen der Hyperquader von
Hyperwürfeln minimieren (gleiche Ausdehnung
aller Dimensionen)
FH-Hof
Lineares Verfahren zum Aufspalten eines Knotens nach Ang und Tan
Aufspaltung erfolgt bezüglich einer Dimension
Zunächst wird die Aufteilung für jede
Dimension getestet
Wähle die günstigste Dimension:
Differenz der Anzahl von Elementen in den
beiden neuen Knoten ist klein (Priorität 1)
Überlappung zwischen den beiden neuen Knoten
ist gering (Priorität 2)
Volumen der neuen Knoten ist gering (Priorität
3)
FH-Hof
Beispiel für das Verfahren nach Ang und Tan - Teil 1
FH-Hof
Beispiel für das Verfahren nach Ang und Tan - Teil 2
?
FH-Hof
Beispiel für das Verfahren nach Ang und Tan - Teil 3
FH-Hof
Beispiel für das Verfahren nach Ang und Tan - Teil 4
FH-Hof
Erweiterung der R-Baums für Regionen
In den Baum werden statt Punkte vollständige
Hyperquader eingefügt
Anpassung der Verfahren offensichtlich
Interessant für räumlich ausgedehnte Daten
Statt 2d Dimensionen werden nur d
Dimensionen benötigt
FH-Hof
Erzeugung eines „optimalen“ R-Baums
Analyse einer festen Datenmenge
Erzeugung eines R-Baums für diese
Datenmenge
Optimierung bezüglich eines vorher
festgelegtem Kriteriums
Typen von Verfahren:
Bottom-Up
Top-Down
FH-Hof
Bottom-Up-Verfahren
Ordne die einzelnen Punkte den Blättern eines
R-Baums zu
Erzeuge aus den Blättern schrittweise die
weiteren Knoten der Indexstruktur
Zuordnung von Punkten zu Blättern:
über Sortierfunktion (Interleaving, Hilbertkurve,
etc.)
Sort Tile Recursive
FH-Hof
Beispiel: Zuordnung über 2D-Hilbertkurve
FH-Hof
Sort Tile Recursive - Ansatz
Idee: Teile jede Dimension in etwa gleich viele
Teile auf (Gitterstruktur)
Beispiel:
Teile eine zweidimensionale Struktur zunächst in
(n/v) Segmente auf (v: Kapazität)
Sortiere die Einträge bezüglich der ersten
Dimension und verteile die Einträge auf die
Segmente
Teile entsprechend jedes Segment in (n/v)
Blattknoten auf (Sortierung bezüglich der
zweiten Dimension)
FH-Hof
Sort Tile Recursive - Beispiel