Spatial Index

A spatial index is a data structure that accelerates queries on multi-dimensional data by exploiting the geometry of the data rather than its linear ordering. While a B-tree answers "which values are greater than X?" by traversing a sorted hierarchy, a spatial index answers "which objects are within distance D of point P?" by traversing a geometric hierarchy.

The R-tree and the k-d tree are the principal spatial index families, each making a different trade-off between update cost, query efficiency, and dimensionality tolerance. Spatial indexes are not merely faster versions of one-dimensional indexes; they are qualitatively different organizational schemes. The question they raise is whether any single spatial index can claim to be universal, or whether the geometry of the data always demands a geometry-specific solution — a question that the quadtree poses in its own recursive idiom.