Why B Trees Fall Short
A B tree orders keys along a single dimension, which works poorly for two dimensional location data. A query like find points within this map rectangle has no single sort order that groups nearby points. Spatial indexes solve this, most commonly with an R tree.
How An R Tree Works
An R tree groups nearby objects and represents each group with its minimum bounding rectangle, the smallest axis aligned box enclosing all members. These boxes nest into a tree.
- Leaf nodes hold bounding boxes of actual geometries.
- Internal nodes hold bounding boxes that enclose their children.
- Boxes of sibling nodes may overlap, which the search must tolerate.
Searching
To find objects intersecting a query window, the engine descends only into nodes whose bounding box overlaps the window, pruning huge regions. Because boxes can overlap, multiple branches may be explored, but most of the tree is still skipped. Candidates that survive the box test then get an exact geometry check.
Key idea
An R tree nests minimum bounding rectangles so spatial queries descend only into overlapping boxes, pruning most of the data before exact geometry checks.