Module 10 · Data structures for scale · Lesson 3 of 11
R-trees
The spatial index inside PostGIS, SQLite and most GIS systems: a balanced tree of nested bounding rectangles that indexes shapes, not just points. How queries prune by overlap, why splits minimise overlap.
Why it matters
Geohash and quad trees index points. Real geographic data is shapes: delivery zones, roads, parcels, flood areas, store footprints. "Which zones contain this point", "which roads intersect this rectangle" and "which parcels overlap this polygon" are queries over extents, and the structure that answers them inside nearly every spatial database is the R-tree. If your design includes a PostGIS query with a spatial index, you are using one, and being able to say how it works is what turns that into an informed choice.
The idea
An R-tree is a balanced tree, like a B-tree, in which each entry is a minimum bounding rectangle (MBR) plus a pointer. Leaves hold the MBRs of actual objects (a polygon's bounding box and its id); internal nodes hold the MBR enclosing all their children. A query with a search rectangle descends only into children whose MBR intersects it. Rectangles at the same level may overlap, which is the structural difference from quad trees and the reason good insertion heuristics matter.
Operations
- 1
Search
From the root, follow every child whose MBR intersects the query box. At leaves, collect candidates and test the exact geometry (the bounding box is a filter, not the answer). Point-in-polygon, intersects and within are all this pattern. - 2
Insert
Choose the subtree whose MBR needs the least enlargement to include the new box, descend, insert at a leaf, and enlarge ancestors' MBRs on the way up. If a node overflows, split it. - 3
Split
Divide the entries into two groups whose MBRs have minimal combined area and overlap. Heuristics (quadratic split, the R*-tree's reinsertion and axis-based split) exist because bad splits create overlapping regions that force queries to visit many subtrees. - 4
Bulk load
For a large static dataset, sort objects along a space-filling curve (Hilbert or Z-order) and pack leaves sequentially, which yields a tighter tree than repeated inserts. - 5
Nearest neighbour
Best-first search ordered by minimum distance from the query point to each node's MBR, stopping when the next MBR is farther than the k-th result found.
Where it lives
PostGIS implements spatial indexes with GiST, a generalised R-tree, so CREATE INDEX ON zones USING GIST (geom) makes ST_Intersects, ST_Contains and ST_DWithin queries fast; the planner uses the index for the bounding-box filter and then evaluates the exact predicate. SQLite's R*Tree module, Oracle Spatial, SQL Server spatial indexes and MongoDB's geospatial indexes are the same family. For most applications the right design is: store geometries in the database, index them with its R-tree, and ask spatial questions in SQL rather than building a structure in application memory.
R-tree versus quad tree versus geohash
| Geohash | Quad tree | R-tree | |
|---|---|---|---|
| Indexes | Points as cells | Points by adaptive regions | Rectangles (any shape's bounding box) |
| Overlap | None (grid) | None (disjoint quadrants) | Yes; minimised by heuristics |
| Balance | n/a | Depth follows density | Balanced like a B-tree; disk-friendly pages |
| Home | Any sorted store; Redis | Application memory | Databases and GIS engines; on disk |
| Best for | Nearby points at scale, moving objects | Uneven density, in-memory nearby search | Shapes, containment and intersection, persistent spatial data |
Performance realities
Overlap is the enemy: when many MBRs at a level overlap, a point query descends several subtrees. Large, thin or diagonal objects (a long road) have bounding boxes that overlap everything around them; splitting such geometries into segments tightens the index. Bounding boxes are coarse filters, so the exact geometry test after the index can still be expensive for complex polygons; simplify geometries or precompute at multiple resolutions. Like any B-tree family structure, it lives on disk in pages and benefits from the same caching.