K-d tree

A k-d tree (k-dimensional tree) is a spatial index that divides space recursively with axis-aligned hyperplanes, creating a binary tree where each level splits on a different dimension. Unlike the R-tree, which groups objects into bounding boxes of arbitrary shape, the k-d tree produces clean, regular partitions that simplify nearest-neighbor search and range query logic.

The k-d tree excels in low-dimensional, static datasets where the data does not change frequently. In high dimensions or dynamic workloads, the tree degrades and the R-tree or quadtree becomes preferable. The k-d tree is a reminder that no spatial index is universal — the geometry of the data and the pattern of the queries together determine which structure is appropriate.