Quadtree

Quadtree ist eine Baumstruktur, bei der der reale Datenraum (Kartenausschnitt) in gleich große Areale eingeteilt wird, den im Baum ein Knoten zugeteilt wird. Es gibt zwei Varianten von Quadtrees: PR-Quadtree (Point-Region-Quadtree) und linearer Quadtree, welcher eine Erweiterung des PR-Qauadtree darstellt.

Aufbau eines PR-Quadtree:

  1. teile den Datenraum in vier gleich große Quadrate ein
    • erzeuge für jedes Quadrat einen Knoten im Baum und hänge diese an die Wurzel (bzw. am jeweiligen Knoten) an
  2. kontrolliere jedes der Quadrate auf die Anzahl der Inhalte, hat Eins mehr als einen Inhalt, führe Schritt 1. für das jeweiligen Quadrat aus.

Nachteile von PR-Qaudtree: Da der PR-Quadtree nur ein Inhalt pro Datenknoten darstellt ist es, nicht effizient für GIS nutzbar, außerdem ist der PR-Quadtree nicht nicht balanciert, was weitere Performance-Probleme mit sich birngt.

Aufbau linearer Quadtree: Linearer Quadtree versuchen die Nachteile von PR-Qaudtrees auszugleichen. Dabei wurde die Kapazität pro Datenknoten erhöht (je nach Verwendungszeck) und die Zwischenknoten wurden durch einen B-Baum ersetzt. Mit Hilfe des B-Baumes ist der lineare Quadtree balanciert und hat mit der erhöhen Kapazität auch einen größeren Nutzen für GIS. Wenn man sich jedoch den linearen Quadtree in der Praxis anschaut kommt es oft vor, dass einige Datenknoten recht überfüllt sind wo hingegen andere Knoten nur ein Geo-Objekt enthalten. Schaut man sich eine Karte an erkennt man auch sofort wieso es dazu kommt. Somit gibt der lineare Quadtree zwar den Eindruck balanciert zu sein (von der Struktur), jedoch kann die Balancierung der Datenmengen nicht gewährleistet sein.

Allgemein zu Quadtree: Quadtrees finden in den modernen GIS eher selten eine Verwendung. Da die meisten GIS auf geografischen Koordinatensystemen basieren, kann hier aufgrund seiner starren Struktur der Quadtree nicht verwendet werden.

Kategorie: Geodatenbanken, Q

Quelle: Geodatenbanksysteme in Theorie und Praxis von Thomas Brinkhoff