Entwurf des Data Warehouse
Der R-Baum ist ein Indextyp, der die Untersuchung räumlicher Daten unterstützt. Er ist ferner ein erweiterter B-Baum zur Behandlung von Punkten, Regionen, usw.Wie B-Baum ist ein R-Baum ein höhenbalancierter Mehrwegebaum. Jedoch werden einige Informationen im R-Baum unterschiedlich gespeichert verglichen mit dem B-Baum. Zusätzlich zum Speichern eines Tupel oder einer Objekt-ID in Blättern speichert ein R-Baum auch begrenzende Daten für indexierte Objekte. Solche Objekte werden durch möglichst kleine Rechtecke, sog. minimale begrenzende Rechtecke, die die Objekte einschließen, repräsentiert. Die Suchanfragen beziehen sich auf diese Rechtecke. Daher sind die Hauptoperationen im R-Baum Punkt- sowie Gebietsanfragen.
Es gibt verschiedene Anfragenklassen, z.B.:
- Intersection Queries (Durchschnitt der Anfragen mit anderen Objekten)
- Containment Queries (Enthaltensein in oder Überlappung mit anderen Objekten)
- Nearest neighbor Queries (nächste Nachbarobjekte)
Abbildung 10 illustriert sechs 2D-Objekte A - F, die durch entsprechende Rechtecke repräsentiert werden. Die Informationen über diese Objekte werden in den Blättern eines R-Baumes gespeichert. Die 1. Gruppe A - D wird wiederum vom Rechteck X eingeschlossen, und die 2. Gruppe E, F vom Rechteck Y. Die beiden werden in Datensätzen des Zwischenknotens gespeichert.
Die Anwendung eines R-Baumes hat einige Vorteile gegenüber Bitmap-Indexierung:
Das Durchsuchen im R-Baum dauert jedoch länger als in einer Bitmap-Tabelle, falls die Rechtecke groß sind. Deshalb wird ein R-Baum häufig verwendet, wenn die verdichteten Regionen groß sind, der Kosten von Bit-Operationen hoch ist und Änderungen häufiger vorkommen. Dagegen benutzt man vorzugsweise die Bitmap-Strategie, wenn die Dimensionen geringe Kardinalität haben, die Anfragen wenige beschränkte Dimensionen haben und die Daten unverdichtet sind.
[Next] [Previous] [Up] [Top] [Contents] [Index]