R-tree

An R-tree (Rectangle tree) is a spatial index structure that organizes multi-dimensional data using nested bounding boxes. Unlike the B-tree, which assumes one-dimensional ordering, the R-tree approximates spatial objects with minimum bounding rectangles and recursively partitions space until each leaf contains a manageable number of entries. The R-tree is the dominant spatial index in PostGIS, Oracle Spatial, and SQLite's SpatiaLite extension.

The R-tree solves the nearest-neighbor problem — "which objects are near this point?" — by pruning the search space at each level of the tree. But it is not the only spatial index. The k-d tree divides space with axis-aligned hyperplanes, trading update efficiency for query simplicity. The R-tree favors dynamic workloads; the k-d tree favors static datasets. The choice between them is not a matter of performance tuning but a claim about the geometry of the data itself.