Quadtree

Themengebiet:

Datenbanken

Quadtree-Prinzip

Bedeutung:
1. Eine baumartige Datenstruktur, die verwendet wird, um die Speicheranforderungen eines Rasters zu reduzieren, indem zusammenhängende, homogene Flächen als eine einzige Einheit codiert wird. Die gesamte Rastermatrix wird rekursiv unterteilt in vier jeweils gleich große Viertel. Die Unterteilung wird fortgesetzt, bis alle Quadranten homogen bezüglich eines ausgewählten Attributes sind oder bis die Grundauflösung der Daten erreicht ist. Dabei werden nur die Gegenden weiter unterteilt, in denen Objektinformationen vorliegen. Die Daten werden gemäß dieser Partitionierungsstrategie mit Bezug auf die Teilungsebene, die ein Quadrant erreicht hat, codiert. Er dient z.B. der flächenhaften Strukturierung von Rasterdaten sowie als Zugriffsmechanismus in Datenbanksystemen. Ein Quadtree realisiert durch die sukzessive Viertelung ein hierarchisches Datenmodell der 1:4-Beziehung.

2. Ein räumlicher Index, der einen räumlichen Datensatz in homogene Zellen gleichmäßig abnehmender Größe aufspaltet. Jede Verkleinerung der Größe ist ein Viertel der Fläche der vorangehenden Zelle. Der Prozess der Viertelung geht solange, bis das gesamte Gebiet mit seinen Objekten partitioniert ist. Durch Traversieren der Baumstruktur sind schnelle Zugriffe auf Daten möglich.

Zum Begriff:
Korrekturen/Ergänzungen schreiben
Letzte Änderung: 09.10.2001