R-Baum

Ein Beispiel eines R-Baums

3-dimensionaler R-Baum mit würfelförmigen Seiten, visualisiert durch ELKI

Ein R-Baum (englisch R-tree) ist eine in Datenbanksystemen verwendete mehrdimensionale räumliche dynamische Indexstruktur. Ähnlich wie bei einem eindimensionalen B-Baum handelt es sich hier um eine balancierte Indexstruktur. Er kann als eine Struktur angesehen werden, die die Eigenschaften des eindimensionalen B-Baums mit dem mehrdimensionalen k-d-Baum kombiniert.

Die Knoten des Baums enthalten eine sortierte Menge von Koordinaten, die zum Beispiel mit Arrays oder Listen realisiert werden kann. Für die Verknüpfungen zwischen den Koordinaten können Zeiger verwendet werden.

Verwendungszweck

Ein R-Baum erlaubt die schnelle Suche in mehrdimensionalen ausgedehnten Objekten. Neben einfachen Punkten gehören dazu auch Polygone im zweidimensionalen Raum und geometrische Körper im dreidimensionalen Raum. Typisch sind aber auch hochdimensionale Objekte, wie sie in der Mathematik oder Bioinformatik vorkommen. Hochdimensional bedeutet hierbei, dass die Anzahl der unabhängigen Suchkriterien in der Größenordnung von 100 bis 1000000 liegt. Erfahrungswerte sagen aber, dass ein R-Baum nur bis etwa 10 Dimensionen gut funktioniert. Dies ist aber von den konkreten Daten abhängig, und es gibt R-Baum-Varianten, die hier Optimierungen enthalten.

Ein R-Baum kann effizient Bereichs-Anfragen, d. h. Rechtecks- bzw. Intervall-Anfragen, beantworten. Auch die Auswertung von nächste-Nachbar-Anfragen ist effizient möglich für geometrische Distanzen, die mit Rechtecken begrenzt werden können. Ein R-Baum ist dynamisch, d. h., er kann bei Änderungen effizient aktualisiert werden.

Typisches Einsatzgebiet eines R-Baum-Index sind Geodatenbanken. Hier werden z. B. Straßendaten, Grenzbereiche oder Gebäudedaten verwaltet. Diese werden als Polygone in der Datenbank gespeichert. Der R-Baum erlaubt später das effiziente Auffinden bestimmter Polygone anhand der Ortskoordinaten. Da hier Rechtecks-Anfragen, z. B. Kartenausschnitte, typisch sind, ist ein R-Baum dazu gut geeignet.

Weniger Vorteile bringt der R-Baum bei Unterraum-Anfragen, also Anfragen, bei denen nicht alle Dimensionen spezifiziert sind, denn hier entstehen sehr große Anfragebereiche, oder bei nicht-geometrischen Distanzen, die nicht in Rechtecksbereiche übersetzt werden können. Hier sind andere Indexstrukturen besser geeignet.

Algorithmus

Das Prinzip eines R-Baums als räumliche Indexstruktur wurde von Antonin Guttman vorgestellt. Ähnlich wie bei einem B+-Baum enthalten Blattknoten eines R-Baumes die zu indizierenden räumlichen Daten. Im Gegensatz zu diesem enthält er aber keine trennenden Schlüssel, sondern speichert in den Indexknoten rechteckige Datenregionen (minimal umgebende Rechtecke), die alle im Teilbaum darunter liegenden Datenregionen umfassen. In den Datenseiten können Datenpunkte, rechteckige Bereiche oder auch Polygone gespeichert sein. Letztere werden oft aber durch ein minimal umgebendes Rechteck approximiert.

Realisiert wird die Speicherung eines Rechtecks durch die Angabe von Intervallen für alle seine Dimensionen. Mithilfe eines R-Baumes können Punkt- oder Enthaltenseinanfragen wie „ist Punkt P in Figur F enthalten?“, „ist Figur F1 in Figur F2 enthalten?“ oder „welche Figuren sind in Figur F enthalten?“ beantwortet werden. Durch die verwendete Näherung (minimal umgebende Rechtecke) in den Blattknoten kann es zu Fehltreffern kommen, die durch Überprüfung der Anfrage an den konkreten Objekten aufgelöst werden müssen. Bei Polygonen spricht man bei der Berechnung auf den Rechtecken von einem „Filterschritt“, bei dem Test mit dem exakten Polygon von dem „Verfeinerungsschritt“. Die eigentliche Indexstruktur liefert hier also nur Kandidaten.

Daten in R-Bäumen werden in Seiten organisiert, die eine variable Anzahl von Einträgen aufweisen können, bis zu einem vordefinierten Maximum und in der Regel über einer Mindestfüllung. Jeder Eintrag innerhalb eines Non-Leaf-Knotens speichert zwei Datenstücke: Eine Möglichkeit, einen Kinderknoten zu identifizieren, und die Begrenzungsbox aller Einträge innerhalb dieses untergeordneten Knotens. Blattknoten speichern die für jedes Kind erforderlichen Daten, oft einen Punkt- oder Begrenzungskasten, der das Kind und eine externe Kennung für das Kind darstellt. Für Punktdaten können die Blatteinträge nur die Punkte selbst sein. Für Polygondaten, das häufig die Speicherung großer Polygone erfordert, ist das gemeinsame Setup, nur das minimale Begrenzungsrechteck des Polygons zusammen mit einem eindeutigen Kennung im Baum zu speichern. Suche Im Bereich Suchen ist der Eingang ein Suchrechteck (Abfragekarton). Die Suche ist sehr ähnlich, um in einem B⁺-Baum zu suchen. Die Suche beginnt am Wurzelknoten des Baums. Jeder interne Knoten enthält einen Satz von Rechtecken und Hinweisen auf den entsprechenden untergeordneten Knoten, und jeder Blattknoten enthält die Rechtecke von räumlichen Objekten, denn der Zeiger auf ein räumliches Objekt kann dort sein. Für jedes Rechteck in einem Knoten muss festgelegt werden, ob es das Suchrechteck überlappt oder nicht. Wenn ja, muss der entsprechende Kinderknoten auch gesucht werden.

Suche nach Knoten

Die Suche erfolgt auf rekursive Weise, bis alle überlappenden Knoten durchquert wurden. Wenn ein Blattknoten erreicht ist, werden die vorhandenen Rechtecke gegen das Suchrechteck getestet und ihre Objekte in das Ergebnis eingefügt, wenn sie im Suchrechteck liegen. Bei der Prioritätssuche und der Suche nächstgelegener Knoten besteht die Abfrage aus einem Punkt oder einem Rechteck. Der Wurzelknoten wird in die Prioritätswarteschlange eingesetzt. Bis die Warteschlange leer ist oder die gewünschte Anzahl von Ergebnissen der Suche zurückgegeben wurde, wird der nächste Eintrag in der Warteschlange fortgesetzt. Die Knoten des R-Baums werden erweitert und dieser Vorgang mit ihren Kindknoten wiederholt. Einträge in den Blattknoten werden zurückgegeben, wenn in der Warteschlange angetroffen wird. Dieser Ansatz kann mit verschiedenen Entfernungsmetriken verfolgt werden, auf mit der Großkreisentfernung für geografische Daten. Um ein Objekt einzulesen, wird der Baum rekursiv vom Wurzelknoten ausgedehnt. Bei jedem Schritt werden alle Rechtecke im aktuellen Verzeichnisknoten untersucht, und ein Kandidat wird mithilfe einer Heuristik ausgewählt, z. B. das Rechteck, das die geringste Erweiterung erfordert. Die Suche steigt dann auf diese Seite ab, bis ein Blattknoten erreicht wird. Wenn der Blattknoten voll ist, muss er geteilt werden, bevor das Einfügen vorgenommen wird. Da wiederum eine umfassende Suche zu teuer ist, wird eine Heuristik eingesetzt, um den Knoten in zwei aufzuteilen.

Hinzufügen eines neu erstellten Knotens

Auf der vorherigen Ebene kann dieses Niveau erneut überlaufen, und diese Überläufe können sich bis zum Wurzelknoten ausbreiten. Wenn dieser Knoten auch überläuft, wird ein neuer Wurzelknoten erstellt und die Höhe des Baums wird um 1 vergrößert. Der Algorithmus muss entscheiden, in welchem Bereich des R-Baums sich der Teilbaum zum Einfügen befindet. Wenn ein Datenobjekt vollständig in einem einzelnen Rechteck enthalten ist, ist die Auswahl des Teilbaums klar. Wenn mehrere Knoten oder Rechtecke an der Erweiterung des R-Baums beteiligt sind, kann diese Auswahl erhebliche Auswirkungen auf die Effizienz des Baums haben. Die Objekte werden in den Teilbaum eingefügt, der die geringste Erweiterung benötigt.

Varianten

R*-Baum

Eine beliebte R-Baum-Variation ist der R*-Baum von Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider und Bernhard Seeger. Diese Variante versucht, durch eine weiterentwickelte Split-Strategie das Überlappen von Rechtecksregionen zu minimieren. Dadurch brauchen bei einer Suchanfrage meistens weniger Teilbäume durchsucht zu werden, und die Anfragen an den Baum werden dadurch effizienter. Zusätzlich können beim Überlauf einer Seite auch Elemente neu in den Baum eingefügt werden (re-insert), was eine Aufteilung (engl. "split") (und die damit unter Umständen steigende Höhe des Baumes) vermeiden kann. Dadurch wird ein höherer Füllgrad erreicht und dadurch ebenfalls eine verbesserte Effizienz. Der resultierende Baum ist aber stets auch ein R-Baum, die Anfragestrategie ist unverändert.

R⁺-Baum

Im R-Baum und R*-Baum konnten sich die Suchräume überlappen. Das ist im R⁺-Baum nicht erlaubt (die Suchräume sind hier disjunkt). Umschließende Rechtecke werden falls notwendig an den Suchraumgrenzen „abgetrennt“. Hierbei können auch Objekte „zerschnitten“ werden, so dass ein Teil des Objekts sich im einen Suchraum und ein anderer Teil des Objekts sich im anderen Suchraum befindet. In solchen Fällen müssen Objekte dann mehrfach im Baum abgelegt werden. R+-Bäume lassen sich für statische Daten gut vorberechnen (insbesondere für Punktdaten, bei denen ein solches Zerschneiden entfällt). Bei Änderungen wird es jedoch aufwendiger, die Disjunktheit sicherzustellen.

Probleme von R-Bäumen

Wie jede Indexstruktur stellen R-Bäume einen Kompromiss dar. Die Verwaltung und Aktualisierung des Baumes erfordert zusätzliche Berechnungen, es wird auch zusätzlicher Speicher für die Indexseiten benötigt. Umgekehrt kann dafür der Baum (bei geeigneten Anfragen und Daten) oftmals die gesuchten Datensätze schneller auffinden. Nimmt man erhöhten Speicherverbrauch und erhöhte Rechenzeit bei Änderungen in Kauf, so kann man oft bessere Leistung bei Suchanfragen erzielen. So wird ein R⁺-Baum meist mehr Speicher benötigen als ein R- oder R*-Baum. Er liefert höhere Leistung bei der Suche, dafür benötigt er mehr Aufwand bei Änderungen.

R*-Bäume sind eine beliebte Wahl, da sie ohne zusätzlichen Speicheraufwand (gegenüber einem R-Baum; im Gegensatz zum R⁺-Baum der Objekte bei Bedarf mehrfach speichert) auskommen, und ihr Implementierungs- und Rechenaufwand nicht wesentlich höher ist als bei einem R-Baum. Genauer gesagt ist ein R-Baum im Speicher auch stets ein R*-Baum, sie unterscheiden sich nur bei der Einfüge- und Split-Strategie.

R-Bäume sind reihenfolgeabhängig, eine wichtige Maßnahme zur Optimierung sind daher „bulk loads“, bei denen der Baum nicht durch elementweises Einfügen aufgebaut wird, sondern versucht wird, direkt einen verbesserten Baum zu konstruieren. Hierzu werden oft die Elemente zunächst sortiert und dann der Baum bottom-up konstruiert. Wird ein R-Baum elementweise in einer ungünstigen Reihenfolge gefüllt, so kann er eine (geometrisch) unbalancierte Struktur aufweisen. Ein optimierter R-Baum hat zwar die annähernd gleiche Tiefe, seine Regionen überlappen sich aber weniger und überdecken den Datenraum daher gleichmäßiger.

In höheren Dimensionen tritt der sogenannte Fluch der Dimensionalität auf. Beim R-Baum führt das dazu, dass sich die entstehenden Rechtecksregionen zu immer größeren Teilen überlappen, wodurch die Suche immer größere Teile des Baumes verarbeiten muss. Dies reduziert die Leistung der Indexstruktur. Der X-Baum von Stefan Berchtold, Daniel A. Keim und Hans-Peter Kriegel stellt hier eine wichtige Variation des R-Baum-Konzeptes für höhere Dimensionalitäten dar. Eine wichtige Maßnahme hierbei sind sogenannte „Supernodes“, das sind vergrößerte Seiten, die vom X-Baum verwendet werden, um ungünstige Splits (mit einer hohen Überlappung) zu vermeiden. Im Extremfall kann er so auch zu einer linearen Datei degenerieren, was gewünscht sein kann.

Während ein R-Baum als dynamische Indexstruktur konzipiert ist, so kann sich seine Leistung durch systematische Einfüge- oder Löschoperationen verschlechtern. In solchen Fällen kann es sinnvoll sein, den Baum von Zeit zu Zeit durch einen bulk load neu aufzubauen, um ihn zu optimieren. Es gibt auch inkrementelle Optimierungsstrategien (wie die re-inserts im R*-Baum), mit denen ein Datenbanksystem in Leerlaufzeiten den Index verbessern kann.

Verfügbarkeit

Eine Referenzimplementierung des R*-Baums ist im Software-Paket ELKI des Lehrstuhls von Professor Hans-Peter Kriegel verfügbar, inklusive Implementierungen eines M-Baumes und anderen Vergleichsverfahren.

Ein R*-Baum findet sich auch beispielsweise in den Datenbanksystemen SQLite (für 2 bis 5 Dimensionen) und Oracle (für 2 bis 4 Dimensionen).

Bei PostgreSQL war der Indextyp „rtree“ bis Version 8.1 vorhanden, wurde dann jedoch von der Generalized-Search-Tree-Schnittstelle (GiST) abgelöst, da er keine nennenswerten Vorteile besaß.

Siehe auch

• Quadtree, K-d-Baum, UB-Baum, Bereichsbaum, Gridfile als Alternative

Weblinks

• Splitting Rules (englisch)
• R-Tree Demonstration (Java-Applet)