25
FH-Hof Der R-Baum Richard Göbel

FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

Embed Size (px)

Citation preview

Page 1: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

FH-Hof

Der R-Baum

Richard Göbel

Page 2: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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)

Page 3: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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 . . .

Page 4: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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

Page 5: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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)

Page 6: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

FH-Hof

Beispiel für einen zweidimensionale Index

X

Y

Page 7: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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

Page 8: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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

Page 9: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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

Page 10: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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

Page 11: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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.

Page 12: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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

Page 13: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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?

Page 14: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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)

Page 15: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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)

Page 16: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

FH-Hof

Beispiel für das Verfahren nach Ang und Tan - Teil 1

Page 17: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

FH-Hof

Beispiel für das Verfahren nach Ang und Tan - Teil 2

?

Page 18: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

FH-Hof

Beispiel für das Verfahren nach Ang und Tan - Teil 3

Page 19: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

FH-Hof

Beispiel für das Verfahren nach Ang und Tan - Teil 4

Page 20: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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

Page 21: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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

Page 22: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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

Page 23: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

FH-Hof

Beispiel: Zuordnung über 2D-Hilbertkurve

Page 24: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

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)

Page 25: FH-Hof Der R-Baum Richard Göbel. FH-Hof Verallgemeinerte Suchanfragen Form der Suchanfrage a l1 column 1 a u1 AND a l2 column 2 a u2... ANDa ld column

FH-Hof

Sort Tile Recursive - Beispiel