R-Baum

R-Baum ist eine Speicherstruktur, die vom B-Baum abgeleitet wurde und an die Bedürfnisse von Geoinformationssystemen angepasst wurde. Im Gegensatz zum B-Baum speichert der R-Baum seine Daten ausschließlich in den Blattknoten, die Zwischenknoten dienen als Zeiger (Directories) auf bestimmte Areale im realen Datenraum.
R-Baum ist eine balacierte Speicherstruktur, jedoch läuft die Balancierung nicht duch Vergleich der Daten (keine lineare Reihenfolge) sondern anhand der Anzahl im Directory enthaltenen Objekte.
Es gibt verschiede Varianten von R-Bäumen: R-Baum, R*-Baum und R+-Baum.

Aufbau R-Baum(Regeln zum Eifügen):

  1. Objekt ist vollständig in genau einem Directory-Rechteck enthalten
    • füge das Objekt in das Directory-Rechteck ein.
  2. Objekt ist vollständig in mehreren Directory-Rechtecken enthalten
    • füge das Objekt in das Directory-Rechteck mit kleinster Fläche ein.
  3. Objekt ist in keinem Directory-Rechteck vollständig enthalten
    • füge das Objekt in das Directory-Rechteck mit dem kleinsten Flächenzuwachs ein.

Variante R*-Baum: Beim R*-Baum wurden folgende Verbesserungen des R-Baumes vorgenommen:

  • Minimierung der Überlappung der Directory-Rechtecke
  • Minimierung der Fläche der Directory-Rechtecke
    • Die Minimierungne der Überlappung und Fläche der Directory-Rechtecke bringt den Vorteil mit sich, dass im Fall einer Geo-Anfrage an die Datenstruktur die Wahrscheinlichkeit sinkt mehrere Directories in die Abfrage einzubeziehen, was wiederum für bessere Performance sorgt.
  • Quadratische Directory-Rechtecke
    • Man hat herausgefunden, dass Anfragen in GIS eher quadratischer Natur sind somin wäre es für die Performance vorteilhafter, wenn die Directory-Rechtecke die gleiche Form hätten.
  • Maximierung der Speicherplatzausnutzung
    • Je kompakter der R-Baum, desto performanter die Anfragen

Variante R+-Baum: Beim R+-Baum handelt es sich um eine Variante der R-Bäume, bei den die Überlappung der Directories komplett vermieden wird (Clipping).
Das sogenannte Clipping kommt beim Teilen von Datenknoten im R+-Baum zum einsatz. Hat ein Knoten die Kapazität überschritten wird er vor der Teilung untersucht, ob die Teilung ohne Überlappung durchgeführt werden kann. Dabei zieht man verschiedene horizontale und vertikale Geraden durch das Directory-Rechteck und wählt diese Gerade aus die keine Überschneidung mit einem Geo-Objekt hat, anschließend wird der Directory dort geteilt.
Dies gelingt jedoch nicht immer. In diesem Fall teilt man das Directory an der Stelle wo die Gerade die minimale Überschneidung (Kosten) hat und speichert das überschneidende Objekt in beiden Directories. Dies ist zwar nicht im Sinne von R-Bäumen ist aber aufgrund des Perfomancevorteils fehlender Überlappungen vernachlässigbar.

Kategorie: Geodatenbanken, R