Search tools and guides ⌘K
VII · Spatial structures

R-tree

A tree of bounding boxes.

1984 · Antonin Guttman · UC Berkeley
The story

Guttman's R-tree organises rectangles (or higher-dim hyperrectangles) by their bounding boxes. Internal nodes hold the union bounding box of their children. Spatial queries skip whole subtrees whose bounding boxes don't intersect the query. Standard in every spatial database.

How it works

Each node holds up to M entries; each entry is (bounding box, child or data). Insert chooses the path with smallest area increase; splits when full. Variants: R*-tree (better split heuristic), R+-tree (no overlap), Hilbert R-tree (space-filling curve order).

Where it lives

PostGIS (default index). MySQL spatial types. Oracle Spatial. SpatiaLite. Almost every "find nearby" feature on a mapping product.

The key insight

R-trees handle extents (boxes, polygons, lines), not just points. That's the difference between "find restaurants within 5km" and "find every road that intersects this neighbourhood".

More in Spatial structures
KD-tree Binary search, in higher dimensions. Quad-tree / Octree Recursive 4-way / 8-way subdivision. BVH · bounding volume hierarchy A tree of boxes for ray tracing. Z-order / Hilbert curve Linearise space, preserve locality.
Across the cabinet
I Dynamic array (vector) An array that grows itself. I Linked list A chain you can splice. I Stack Last in, first out. I Queue First in, first out. I Deque Both ends, equally. I Ring buffer A fixed-size queue that never allocates. II Binary search tree Sorted, but with shortcuts. II AVL tree Always height-balanced, to within one.
← All data structures