R-Trees

Open a map app and search "coffee near me." Within milliseconds it returns a handful of cafés from a database of millions of places. How?

A naïve approach would scan every location and check its distance. For small datasets that works fine — but geography datasets contain billions of points, polygons, road segments, and building footprints. Scanning them all for every query would be catastrophically slow.

R-trees, introduced by Antonin Guttman in 1984, solved this with one elegant idea: group nearby objects into bounding rectangles, then group those rectangles into larger ones, building a hierarchy. A spatial query then descends the tree, pruning entire branches the moment their bounding box doesn't overlap the query region. Most of the index is never touched.

The key insight is that spatial data has locality — nearby things tend to stay nearby — and a good index exploits that locality to skip work. R-trees are the workhorse behind PostGIS, Oracle Spatial, SQLite's SpatiaLite, and virtually every GIS database on the planet.

Below is a small R-tree holding 16 rectangles (shown in blue). Click Draw query and drag on the canvas to define a query region (shown in orange). The tree will highlight the bounding boxes it inspects (yellow) and the rectangles it actually returns (green). Click Reset to start over.

<div class="toolbar">
  <button id="btnDraw" type="button">{{btn_draw}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
  <span id="info" class="info">{{info_initial}}</span>
</div>
<canvas id="canvas" width="560" height="360"></canvas>
<div id="results" class="results"></div>

* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; background: #fff; }
.toolbar { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.info { font-size: .85rem; color: #555; flex: 1; min-width: 160px; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; display: block;
         cursor: crosshair; touch-action: none; width: 100%; max-width: 560px; }
.results { margin-top: .5rem; font-size: .85rem; color: #333; min-height: 1.3em; }

// Code not found

Notice how the tree skips entire clusters the moment their bounding box misses the query region. With 16 rectangles the saving is modest; with millions of shapes the pruning makes the difference between milliseconds and minutes.

R-trees are a solved engineering problem — Guttman's 1984 paper described the complete structure — but their theoretical analysis is subtler than it looks.

• Query time: $O(\log n)$ average. If the bounding boxes at each level overlap little, a region query visits $O(\log n)$ nodes, just like a balanced binary search tree. Each node holds between m and M children (typical values: m=2, M=50), so the tree height is ⌈log_M n⌉.
• Worst case: $O(n)$. In degenerate cases — long thin rectangles, pathological insertion order — bounding boxes at the same level overlap heavily. A query that touches one box may then need to descend into all of them, collapsing to a linear scan.
• Insertion and deletion: $O(\log n)$ amortized. Inserting a rectangle chooses the child whose bounding box needs the least enlargement, then adjusts bounding boxes up the path to the root. Deletion finds the entry, removes it, and re-inserts orphaned entries.
• The overlap problem. Minimising overlap between sibling bounding boxes is the central challenge of R-tree design. The original algorithm uses greedy heuristics; later variants — R*-tree (Beckmann et al., 1990) and Hilbert R-tree — use more aggressive rebalancing and space-filling curve ordering to keep overlap low.
• Comparison to k-d trees. K-d trees partition space with axis-aligned hyperplanes rather than bounding boxes, which avoids overlap but handles extended objects (polygons, segments) awkwardly. R-trees store any rectangle natively.

In practice, a well-tuned R*-tree on geographic data achieves query performance close to the theoretical $O(\log n)$ bound, which is why it became the default spatial index in virtually every serious database.

Any system that needs to answer "what's near here?" efficiently leans on R-trees or their descendants:

• Geographic information systems (GIS): PostGIS, Oracle Spatial, and SpatiaLite index road networks, land parcels, and satellite imagery tiles using R-trees. Spatial joins ("which roads cross this flood zone?") become logarithmic instead of quadratic.
• Map and navigation apps: The tile selection and point-of-interest lookup in applications like Google Maps, OpenStreetMap, and Mapbox all rely on spatial indexes. Your "nearby restaurants" result comes back in under 100 ms for exactly this reason.
• Ride-sharing dispatch: Platforms like Uber and Lyft maintain a live spatial index of driver locations. Matching a rider to the nearest available driver is a nearest-neighbour query on a structure that updates thousands of times per second.
• Game engines and collision detection: Unity, Unreal Engine, and most physics engines use a variant called a dynamic AABB tree (axis-aligned bounding-box tree) — essentially a real-time R-tree — to quickly find which objects might be colliding before running expensive physics calculations.
• Computational biology: Protein structure databases index atoms in 3-D space with R-trees to find residues within a given distance of a query point.
• Astronomy: Star catalogs and sky-survey pipelines use R-trees to answer queries like "which known objects fall inside this telescope field of view?"

Learn how an R-tree prunes a spatial search and you understand the index inside nearest-neighbor search algorithms, spatial joins, and real-time collision pipelines alike.

R-trees rest on an almost embarrassingly simple idea: wrap groups of nearby shapes in bounding boxes, nest those boxes in bigger ones, and you get a hierarchy that lets a query skip huge swathes of the data in a single comparison.

Guttman published the original paper in 1984, and four decades later the R*-tree variant is still the default spatial index in every serious database. That longevity says something: the bounding-box hierarchy maps so naturally onto how spatial data is organised in the real world that no fundamentally different structure has displaced it.

The next time a map shows you coffee shops in your neighbourhood before you finish typing, an R-tree quietly pruned away millions of irrelevant locations in the background — and you never had to wait for the linear scan.