What an R tree indexes
An R tree is a balanced tree built for rectangles and other shapes, not just points. Each node stores a minimum bounding rectangle that tightly encloses all the boxes of its children. Searching descends only into nodes whose bounding rectangle overlaps the query window.
Unlike a quadtree, an R tree groups objects by what is near them, so sibling rectangles can overlap. Good insertion and split heuristics try to keep that overlap and the total covered area small.
Why it fits real maps
- It indexes extended objects like roads, lakes, and delivery zones, not only single coordinates.
- It stays balanced like a B tree, so depth grows slowly as data grows.
- It supports containment, intersection, and nearest queries on shapes.
The cost of overlap
When bounding rectangles overlap heavily, a single point query may have to follow several branches. Quality of the index depends almost entirely on the split algorithm that decides how to partition entries.
Key idea
An R tree organizes shapes under nested bounding rectangles, trading possible overlap for the ability to index regions rather than just points.