R-Trees
Practice this topic in a realistic system design interview
Spatial search gets harder when the objects are not just points. Restaurants may be points, but delivery zones are polygons, roads are lines, and buildings are shapes that cover an area. Checking every shape for every query does not scale.
An R-tree speeds this up by wrapping each object in the smallest rectangle that contains it, then using those rectangles to skip large parts of the data. Only the remaining candidates need the more expensive exact geometry checks.
R-trees are a strong fit for database-backed spatial queries, which is why many spatial databases use R-tree-like indexes. The main trade-off is overlap: if many rectangles overlap, a search may have to follow several branches instead of skipping most of the tree.
This chapter explains how R-trees index shapes, how search and node splitting work, the common variants, and how databases use them in practice.
1. The Problem with Spatial Data
Suppose a food delivery service stores restaurants and delivery zones. Each restaurant has a location, but each delivery zone may be a polygon.
Common queries include:
- Which restaurants are visible in this map viewport?
- Which delivery zones contain this customer location?
- Which stores are within 2 km of this point?
- Which roads or neighborhoods intersect this polygon?
The brute-force approach checks every object:
This is O(n) per query. With millions of shapes, it is too slow for interactive maps, marketplace search, or busy backend APIs.
Why a B-Tree Is Not Enough
A B-tree can help with one dimension:
That index can narrow a latitude range. But it does not understand longitude at the same time, and it cannot tell whether one polygon overlaps another polygon.
A composite B-tree on (latitude, longitude) can help some bounding-box queries, but it still stores data in a single sorted order. Spatial operations such as intersects, contains, and nearest need an index that understands regions.
The Bounding Box Pattern
Spatial systems often use a two-stage filter:
- Use cheap bounding rectangles to find possible matches.
- Run exact geometry checks only on those possible matches.
For example, a complex polygon can be wrapped by a simple rectangle:
The rectangle may return extra matches, but it should not miss real matches. Exact geometry filtering removes objects whose rectangles overlap but whose actual shapes do not.
R-trees organize those bounding boxes efficiently.