Data Warehouse Technologien

R1

R2

R3

R4

R5

R6

R7

R8

R9

R10

R11

R12

R1 R2 R3

R4 R5 R6 R7 R8 R9 R10 R11 R12

A

B

C

A B C

Abbildung 7.20: R-Baum

Der R-Baum realisiert eine noch bessere Anpassung der Bereiche an die

Daten als der KdB-Baum, wie in Abbildung 7.21 gezeigt.

7.5.5 Varianten von R-Bäumen

Ähnlich wie bei B-Bäumen gibt es für R-Bäume eine Reihe von Varianten. Ei-

nige werden wir kurz skizzieren.

Der R

+

-Baum vermeidet überlappende Rechteckregionen, indem im Falle

einer Überlappung Rechtecke aufgeteilt werden (Clipping). Diese Modifikation

hat mehrere Konsequenzen:

• Der Baum benötigt in der Regel mehr Rechtecke als ein einfacher R-Baum

und wird dadurch größer.

• Der minimale Füllgrad von Rechteckknoten kann nicht mehr garantiert

werden.

• Die Punktsuche benötigt aufgrund der fehlenden Überlappungen nur noch

genau einen Pfad von der Wurzel zu einem Blatt.

Für ausgedehnte Geo-Objekte werden diese durch das Aufteilen auf disjunkte

Rechteckregionen potentiell in mehreren Blättern gespeichert – dieser Effekt

spielt aber für Data-Warehouse-Anwendungen keine Rolle, da Punktdaten ge-

speichert werden (vgl. Abbildung 7.22).

220 7 Indexstrukturen