Quadtree und k-d-Baum

Kurz: Quadtree und k-d-Baum teilen den Raum rekursiv in Bereiche, damit man Punkte in der Nähe einer Position schnell findet, ohne alle zu prüfen.

Genauer: Beide sind räumliche Indexstrukturen. Sie beantworten „Welche Punkte liegen in diesem Rechteck?” oder „Welcher Punkt ist am nächsten?” in etwa O(log n) statt O(n).

Im Detail

• Quadtree: Teilt eine Fläche in vier gleiche Quadranten, die bei Bedarf weiter geteilt werden. Beliebt in Spielen (Kollisionsprüfung), Kartenkacheln und Bildkompression. Die 3D-Variante heißt Octree.
• k-d-Baum: Ein binärer Baum, der abwechselnd nach einer Koordinate teilt (x, dann y, dann z, …) am Median. Gut für Nächste-Nachbarn-Suche in niedrigen Dimensionen.
• Grenze: In sehr vielen Dimensionen (etwa 20+) verlieren sie ihren Vorteil („Fluch der Dimensionen”). Dann nutzt man Vektorindizes mit Näherungsverfahren.
• Verwandt: R-Bäume für Rechtecke (PostGIS), Geohash für Karten.
• Bewegte Objekte: Müssen aus dem Baum entfernt und neu eingefügt werden, was teuer sein kann.

Siehe auch: Binärsuche