R-Trees

When Points Aren't Enough

The quadtree gave us an adaptive grid — resolution that follows the data. But it left us with one assumption baked in: everything is a point. Real maps aren't just points. A road is a long thin line. A lake, a park, a delivery zone, a country border — these are shapes, with real extent, and they don't sit at a single coordinate. Ask a quadtree to index a highway and you hit its deepest weakness: the highway crosses dozens of the quadtree's cells, and since each cell is a separate box in the tree, the highway has to be stored in every single cell it touches. One object, copied over and over.

That's not a rounding error. On a realistic test — 200 road-shaped rectangles over a modest grid — space partitioning stored 1,364 entries for 200 objects: a 6.8× blow-up, each shape duplicated into roughly seven cells. Every duplicate is extra storage, and every update has to touch all the copies. For anything with extent, dividing space and forcing objects into the pieces is the wrong move.

So the R-tree makes the opposite bet. Don't divide the space — group the objects. Draw the tightest box around each object, then gather nearby boxes into bigger boxes, and those into bigger boxes still, until you have one box over everything. Each object lives in exactly one box, stored once, no matter how much space it spans. It's the same adaptive-tree instinct as the quadtree, turned inside-out: bottom-up from the data, instead of top-down from the space.

Two opposite ways to index a map full of shapes, side by side. On the left, space partitioning like a quadtree: a fixed grid is laid over the map, and a single road — a long thin rectangle — crosses many cells, so it must be stored again in every cell it touches, shown as the same road copied into cell after cell; a label notes this reached about seven copies per shape in a real test. On the right, the R-tree's approach: instead of dividing the space, it groups nearby objects into bounding boxes — minimum bounding rectangles — and the road sits in exactly one box, stored once. Those boxes are themselves grouped into bigger boxes, forming a small hierarchy of nested rectangles. The caption contrasts them: a quadtree divides the space and duplicates the shape; the R-tree groups the objects and stores each one once. The bottom line: to index things with real extent, stop dividing space and start grouping objects into boxes.

The MBR and the Bottom-Up Tree

The box around an object has a name: the minimum bounding rectangle, or MBR — the smallest axis-aligned rectangle that completely encloses it. A wiggly coastline, a diagonal road, a twelve-sided polygon all collapse to a simple rectangle the index can reason about with four numbers. The MBR is an approximation — that matters later — but it's a cheap, tidy handle on a messy shape.

Now stack them into a tree:

A leaf node holds a handful of objects, each with its MBR.
An internal node holds a handful of child nodes, each stored with the MBR that tightly bounds everything inside that child. So a parent's box is the union of its children's boxes.
The root is one box over the entire dataset.

Antonin Guttman introduced this in 1984 and described it exactly right: an R-tree is a B-tree generalized to space. It inherits the B-tree's best trait — it's height-balanced, every leaf at the same depth, kept that way by splitting nodes that overflow — so like a B-tree it stays a flat few levels even over millions of objects, and each node is sized to fill a disk page so a lookup is a handful of page reads. (That B-tree-for-disk lineage is why R-trees are what real databases reach for.)

Searching is the pruning move you already know from the quadtree, now on boxes: to find everything in a query region, start at the root and descend into every child whose MBR intersects your query — skipping any box that doesn't touch it, and everything beneath it. Follow the boxes down to the leaves, and test the objects you find there. Simple enough — except for one thing the quadtree never had to worry about.

The Overlap Problem

Here's the catch that shadows every R-tree, and it comes straight from the design. A quadtree's cells are carved out of space, so they're disjoint — no two cells share any area, and a point falls in exactly one. But an R-tree's boxes are drawn around objects, wherever the objects happen to be — so sibling boxes can overlap. Two bounding rectangles can cover some of the same ground.

And overlap is expensive, because of how search works. When your query point (or box) lands in a region where two sibling MBRs overlap, it intersects both — so you have to descend both branches to be sure you haven't missed anything. Every overlap is a fork in the search where one path becomes two. Pile up enough overlap and a query that should have walked one root-to-leaf path ends up wandering half the tree. This is the famous caveat: an R-tree has no good worst-case guarantee, precisely because of overlapping boxes — it's fast on well-built trees and real data, and it degrades toward a scan on badly-built ones.

You might ask: why tolerate overlap at all? You can banish it — clip every object at the box boundaries and file each piece in both boxes — and that's a real variant, the R+-tree. But look what you did: one object is now stored in several places again. That's the quadtree's replication problem, back from the dead. Overlap and replication are the two poles, and every spatial structure sits somewhere between them: the space-partitioning grid banishes overlap and pays in replication; the plain R-tree stores each object exactly once and pays in overlap. No free lunch — only which price you choose. The standard R-tree takes the overlap, and spends its energy keeping it small.

How much does it matter? Take the exact same 400 objects and build two R-trees — one that splits nodes carefully to keep boxes apart, one that splits them carelessly. The careful tree leaves total overlap of about 0.37; the careless one, about 13 — thirty-six times more. Now run the identical small query on each: the careful tree visits about 9 nodes; the careless one visits 36 — four times the work, for the very same result. The trees have the same objects, the same shape on paper. The only difference is overlap, and overlap decided everything. That's why the entire art of the R-tree lives in two decisions.

The overlap problem that defines the R-tree, shown as a good split versus a bad split of the same objects. On the left, a well-chosen split: the objects are divided into two bounding boxes that barely touch, so a query point lands inside just one box and the search follows a single branch. On the right, a poor split: the same objects are divided into two boxes that overlap heavily, their shared region shaded red, so a query point in that overlap falls inside both boxes and the search must descend both branches at once. Measured numbers sit beneath: the good split left about 0.37 units of total overlap area, the bad split about 13, roughly thirty-six times more; and a small query visited about 9 tree nodes with the good split versus 36 with the bad one, for the very same answer. The bottom line: overlapping bounding boxes are the R-tree's tax — they force a query down more than one path, so every design choice fights to keep overlap small.

Two Hard Choices: Insert and Split

Everything about an R-tree's quality — how little its boxes overlap — comes down to two moments.

Where do I put a new object? (ChooseSubtree.) Descending to insert, at each node you pick the child to go into. The rule is least enlargement: choose the child whose MBR would have to grow the least to swallow the new object (ties broken by smallest area). Growing a box as little as possible keeps boxes tight and keeps them from sprawling across their neighbors. The R*-tree refines this near the leaves to pick the child that adds the least overlap, not just the least area.

A node just overflowed — how do I split it? (Split.) When a node exceeds its capacity, it splits into two, and how you divide the entries is the single most important decision in the whole structure. Split them into two groups that stay compact and apart, and overlap stays tiny; split them carelessly and you get two big boxes smeared across each other. Guttman gave a quadratic split — find the two entries that would waste the most space if kept together, seed the two groups with them, then hand each remaining entry to the group whose box grows least. It's the difference between the 0.37 and the 13 from a moment ago.

This split problem is so central that it spawned a better R-tree: the R*-tree (Beckmann and colleagues, 1990). Its trick is forced reinsertion — when a node overflows, instead of immediately splitting, it pulls out a fraction of the entries and reinserts them from the top, letting them find better homes. That one idea, borrowed from the way a B-tree rebalances, produces markedly tighter, less-overlapping trees, and the R*-tree is what most modern implementations actually use.

(One more trick for when the data is static — you're indexing a fixed set of shapes, not a live feed. Instead of inserting one at a time, you bulk-load: sort all the objects, tile them into leaf-sized groups, and build the tree bottom-up in one pass — the Sort-Tile-Recursive (STR) method. It packs the leaves full and produces a near-optimal, low-overlap tree far faster than a million individual inserts. It's how you'd load a country's worth of road geometry.)

Feel it directly: drop objects, choose how the tree splits, and watch the overlap — and the cost of a query — grow or shrink with your choice.

Drop rectangles — objects with real size — and watch the R-tree group them into bounding boxes, splitting a box into two whenever it overflows. Flip the split strategy between a smart (min-overlap) split and a naive one, and watch the shaded overlap between sibling boxes balloon or shrink. Then drop a query box and see the search light up every bounding box it has to open: with a tidy tree it follows one path; with an overlap-riddled one it fans out into many. The meter makes the lesson unmissable — the same objects, the same query, but overlap decides how much of the tree you touch.

The Spatial Toolkit, and What Databases Actually Ship

You now have three answers to "how do I index a map," and they divide the work cleanly:

Geohash — a fixed grid flattened into a string. Dead simple, lives in any database or cache, shards across machines by prefix. Best for points and quick proximity when you value simplicity and distribution above all.
Quadtree — an adaptive grid that subdivides space where points are dense. Great for points and range queries when it fits in memory.
R-tree — an adaptive tree of bounding boxes that groups the data. The only one of the three that indexes shapes with real extent — roads, polygons, regions — and it's the structure built for disk. Its cost is the overlap you just met.

And here's the punchline that ties this whole section together: the R-tree is what production databases actually run. PostGIS — the spatial workhorse of the Postgres world — indexes geometry with GiST, which is an R-tree under the hood. SQLite ships an R*Tree module; Oracle Spatial uses the same structure. When you write a "find everything near here" query against a real spatial database, an R-tree is doing the work.

One crucial detail about how they use it, and it's the pattern from Geospatial Search: The Problem come back around: a spatial index doesn't index the shapes — it indexes their bounding boxes. So a query runs in two steps. First the filter: the R-tree quickly finds every object whose box overlaps your query box — fast, approximate, a few page reads. Then the refine: an exact geometry test runs only on that short list of candidates, throwing out the ones whose box overlapped but whose actual shape doesn't. Filter, then refine — the R-tree is the filter; the exact test is the refine. It's the same two-phase shape we've seen since the very first spatial lesson.

The spatial-index toolkit, three structures compared as answers to the same problem, plus what production systems actually use. Geohash: a fixed grid encoded as a string; simple, string-native, distributes trivially; best for points and quick proximity. Quadtree: an adaptive grid that subdivides space where points are dense; great for points and range queries in memory. R-tree: an adaptive tree of bounding boxes that groups the data; the only one of the three that indexes shapes with real extent — roads, polygons, regions — and the standard in real spatial databases, though its boxes can overlap. A row underneath names the real systems: PostGIS uses GiST, which is an R-tree; so do SQLite's R*Tree module and Oracle Spatial. And all of them run the same two-step play from the geospatial lesson: the index quickly finds the objects whose bounding boxes intersect the query, then an exact geometry test refines that shortlist — filter, then refine. The bottom line: geohash to distribute, quadtree for points in memory, R-tree for real shapes — and the R-tree is what the databases ship.

What to Remember

⭐ The R-tree groups objects instead of dividing space. It wraps each object in a minimum bounding rectangle (MBR), gathers nearby MBRs into bigger MBRs, and builds a height-balanced tree bottom-up — a B-tree generalized to space, sized for disk pages. Each object is stored once, so shapes with extent index cleanly (where a space grid replicated them ~7×).
⭐⭐ Overlap is the R-tree's defining tension. Because boxes are drawn around objects, sibling boxes can overlap — and a query in an overlap region must descend every box it touches. Same objects, a careless split left 36× more overlap and made a query visit 4× more nodes. There's no good worst case; quality is everything.
⭐ Two decisions control that quality: ChooseSubtree (insert into the child that enlarges least) and Split (divide an overflowing node to minimize overlap — Guttman's quadratic split). The R*-tree improves both with forced reinsertion and is what most implementations use.
⭐ The R-tree is the production spatial index. PostGIS's GiST, SQLite's R*Tree, Oracle Spatial — all R-trees. They index bounding boxes, then filter-then-refine: the index finds candidate boxes, an exact geometry test confirms.
Pick by the job: geohash to distribute, quadtree for points in memory, R-tree for real shapes — and it's what the databases ship.

Every structure so far — geohash, quadtree, R-tree — lives on one machine (or needs real effort to shard). But planet-scale systems index the whole Earth across thousands of servers, and they want the distributability of a geohash and smarter geometry than a flat grid. The answer is to go back to the space-filling curve and make it far better — a curve that hugs locality, wrapped around a sphere, with a hierarchy of cells. That's S2 and H3, the global grids behind Google and Uber — and they're next.