Home > Lernmodule > Modul 10

 

11 Der R-Baum: Eine räumliche Indexstruktur

Diese Lerneinheit beschreibt eine Indexstruktur, die besonders für mehrdimensionale Daten geeignet ist und räumliche Anfragen effizient unterstützt. Beispiele für solche Anfragen sind:

• „In welchem Polygon liegt Punkt p?“
• „Welche Polygone liegen in einem gegebenen achsenparallelen Rechteck q?“

Die naive Lösung, alle Polygone zu testen, scheitert oft an der großen Anzahl vorhandener Polygone und an der komplexen Berechnung für jedes Polygon. Die sog. „Filter and Refine“ Strategie vereinfachte letztere Berechnungen, indem zuerst sehr effizient das minimal umschließende achsenparallele Rechteck (Bounding Box) des Polygons getestet wird und anschließend erst die erfolgreich getesteten Kandidaten selbst.

Der R-Baum

Der Filterschritt kann dabei durch die Verwendung eines R-Baumes optimiert werden. Bei diesem handelt es sich um einen balancierten Baum, dessen Knoten mehrere Datensätze beinhalten kann. In jedem Blatt werden Referenzen auf die eigentlichen Geometrien, sowie deren Bounding Boxes gespeichert. Jeder Vaterknoten speichert für jeden seiner Nachfolger wieder die Bounding Box über alle seine Teilgeometrien.
Diskutiert werden die Algorithmen zum Suchen, Einfügen und Löschen von raumbezogenen Daten.
Besonders wichtig sind hierbei die Algorithmen zum Splitten übervoller Knoten des Baumes.
Abschließend stellen wir eine Variante des R-Baumes, den R*-Baum vor, welcher verbesserte Algorithmen für das Einfügen neuer Daten bietet.