R-Baum

 

Eine der größten Anforderungen an Geo-Anwendungen besteht darin, auf räumlichen Anfragen möglichst schnell zu antworten. Die Mehrdimensionalität dieser Anfragen verhindert jedoch die Verwendung der gebräuchlichen Indexstrukturen (z.B. B-Bäume, vgl. [BM72]). Es sind also räumliche Zugriffsmethoden erforderlich, welche speziell auf das Geo-Anforderungsprofil räumlicher Anfragen zugeschnitten sind.

Als wichtigste räumliche Anfragen sind die folgenden drei Typen zu nennen. Dabei sei eine Menge von 3D-Objekten sowie eine 3-dimensionale Anfrage-Box gegeben.

1. Bestimme alle Objekte, die vollständig in der Anfrage-Box enthalten sind.
2. Bestimme alle Objekte, welche die Anfrage-Box schneiden.
3. Bestimme alle Objekte, die einen bestimmten Punkt enthalten.

Im GEOTOOLKIT existiert zur Unterstützung räumlicher Anfragen die Klasse gtAccessPath, welche als abstrakte Schnittstellenklasse für diejenigen räumlichen Indexstrukturen dient, die im GEOTOOLKIT zur Verfüngung gestellt werden. Momentan ist dies nur die Klasse gtRTree, in der ein R-Baum modelliert wird - an einer Version eines Octrees wird jedoch momentan gearbeitet.

 

Der R-Baum etabliert eine räumliche Ordnung auf einer Menge geometrischer Objekte im 3-dimensionalen Raum. Diese Objekte werden innerhalb des R-Baumes bezüglich ihrer Lage im Raum, welche durch ihre Bounding-Box bestimmt ist, abgelegt. Der hierarchische Aufbau eines R-Baumes ist vergleichbar mit dem eines B-Baumes, da jeder Knoten im R-Baum die Bounding-Box seiner Söhne enthält. Ein Beispiel für den Aufbau eines R-Baumes ist in Abb. 4.5 angegeben.

Wie man sieht, sind zwar Überschneidungen der Bounding-Boxen erlaubt, die Vorschriften zum Aufbau eines R-Baumes sehen jedoch vor, diese zu minimieren, so daß die oben angegebenen räumlichen Anfragen mit Hilfe eines R-Baumes im allgemeinen in logarithmischer Zeit ausgeführt werden können.

Eine hohe Effizienz räumlicher Zugriffe ist für das GEOTOOLKIT von großer Wichtigkeit, da die darauf aufsetzenden GIS-Prototypen - wie schon angesprochen wurde - zur Verwaltung sehr großer Mengen räumlicher Daten herangezogen werden. Aus diesem Grund wurde erst kürzlich eine Optimierung der GEOTOOLKIT-Implementierung des R-Baumes durch MICHAEL WAGNER ([Wag98]) vorgenommen.

Nachdem nun die wichtigsten Grundlagen zu Geo-Informationssystemen allgemein und speziell dem GEOTOOLKIT diskutiert wurden und in Kapitel 3 ein Überblick der in der Literatur zu findenden Repräsentationsmodelle für topologische Beziehungen - mit einer Anpassung an den im Rahmen dieser Arbeit betrachteten 3-dimensionalen Raum - erfolgte, soll in den nächsten beiden Kapitel die Integration einer topologischen Komponente in das GEOTOOLKIT beschrieben werden.