Datenbanken Online Lexikon TH Köln, Campus Gummersbach
Aktuelle Änderungen - Suchen:

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