Many spatial systems need to query objects by shape, such as points, rectangles, lines, and polygons.

An R-tree indexes objects by their minimum bounding rectangles. Queries use those rectangles to skip large parts of the dataset before running exact geometry checks.

R-trees are a strong fit for database-backed spatial queries. Their main trade-off is overlap: when bounding rectangles overlap heavily, a search may need to follow multiple branches.

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:

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 high-volume backend APIs.

A B-tree can help with one dimension:

That index can narrow a latitude range. It does not understand longitude at the same time, and it does not understand that a polygon overlaps another polygon.

A composite B-tree on (latitude, longitude) can help some bounding-box queries, but it still imposes a one-dimensional sort order. Spatial predicates such as intersects, contains, and nearest need an index that can reason about regions.

Spatial systems commonly use a two-stage filter:

For example, a complex polygon can be wrapped by a simple rectangle:

The rectangle may return false positives, but it should not return false negatives. Exact geometry filtering removes candidates whose bounding boxes overlap but whose actual shapes do not.

R-trees organize those bounding boxes efficiently.