R*-Baum

R*-Baum
Ein Beispiel eines R-Baums

Ein R-Baum (eng. R-tree) ist eine in Datenbanksystemen verwendete räumliche (man sagt auch mehrdimensionale) Indexstruktur.

Inhaltsverzeichnis

Verwendungszweck

Ein R-Baum erlaubt die schnelle Suche in mehrdimensionalen Daten. Dazu gehören 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 - 1.000.000 liegt.

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.

Realisierung

Ähnlich zu einem B*-Baum enthalten Blattknoten eines R-Baumes die zu indizierenden räumlichen Daten. Im Falle von zweidimensionalen Daten sind dies Polygone. Die Indexknoten enthalten rechteckige Datenregionen (minimal umgebende Rechtecke), die alle im Teilbaum darunter liegenden Datenregionen umfassen.

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 Polygonen aufgelöst werden müssen.

R*-Baum

Eine verbesserte Variante ist der R*-Baum. R*-Bäume haben dieselbe Struktur wie R-Bäume, verwenden jedoch einen weiterentwickelten Algorithmus zum Unterteilen minimal überdeckender Rechtecke.

Im R-Baum konnten sich die Suchräume noch ü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.

Dies führt zu einem besseren Laufzeitverhalten beim Aufteilen und Suchen sowie zu einem höheren Füllgrad der Indexknoten, also zu einer besseren Speicherausnutzung. Entscheidend ist jedoch die größere Robustheit gegen Entarten der Baum-Struktur.

Siehe auch

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

Literatur

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Baum (Familienname) — Baum ist ein Familienname. Herkunft und Bedeutung Der Familienname kann vom Baum als der Pflanze herrühren oder ein jüdischer Familienname in Anspielungen auf Abraham als Stammvater sein. Bekannte Namensträger Inhaltsverzeichnis A B C D E F G H I …   Deutsch Wikipedia

  • Baum — is a German surname meaning tree and may refer to:* Antoine Baum (Antoine Baumé), (1728 1804), French chemist * Bernie Baum, American song writer * Eric Baum, American computer scientist and artificial intelligence researcher * Edgar Schofield… …   Wikipedia

  • Baum (Begriffsklärung) — Baum (westgermanisch boum „Baum“, „Baumstamm“) bezeichnet: Baum in der Botanik die Wuchsform einer Pflanze Baum (Familienname), Namensträger siehe dort. Baum (Graphentheorie), in der Graphentheorie einen speziellen Graphen und in der Informatik… …   Deutsch Wikipedia

  • Baum-Wolfsmilch — (Euphorbia dendroides) Systematik Familie: Wolfsmilchgewächse (Euphorbiaceae) …   Deutsch Wikipedia

  • Baum-Hasel — Systematik Eurosiden I Ordnung: Buchenartige (Fagales) Familie …   Deutsch Wikipedia

  • Baum (Steuerelement) — Baum, der ein Verzeichnis mit Unterverzeichnissen darstellt (im Dateimanager Konqueror Ein Baum (engl: Tree view oder treeview) ist ein Steuerelement einer grafischen Benutzeroberfläche, das eine hierarchisch gegliederte Liste darstellt und… …   Deutsch Wikipedia

  • Baum'e — Bau m[ e] , a. Designating or conforming to either of the scales used by the French chemist Antoine Baum[ e] in the graduation of his hydrometers; of or relating to Baum[ e] s scales or hydrometers. There are two Baum[ e] hydrometers. One, which… …   The Collaborative International Dictionary of English

  • Baum-Strelitzie — (Strelitzia nicolai) Systematik Monokotyledonen …   Deutsch Wikipedia

  • BAUM, OSCAR — (1883–1941), Czechoslovak author who wrote in German. Baum was a member of the Prague circle of max brod and franz kafka . Losing his sight as a boy, Baum was trained at the Vienna Institute for the Blind as an organist and pianist and… …   Encyclopedia of Judaism

  • Baum der Sibyllen (Étampes) — Baum der Sibyllen in Étampes Als Baum der Sibyllen wird ein Fenster bezeichnet, das sich in der Kirche Notre Dame du Fort in Étampes, einer Stadt im Département Essonne in der Region Île de France, befindet. Das Bleiglasfenster entstand um… …   Deutsch Wikipedia

  • BAUM, HERBERT — (1912–1942), German Communist and anti Nazi fighter. Baum was a member of the German communist youth movement from 1932 and led a clandestine Jewish communist cell in Berlin from 1936. In 1937 he and his wife Marianne organized a political circle …   Encyclopedia of Judaism

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”