The Spatial Database
A spatial database stores geometry such as points, lines, and polygons, and answers questions about location: which restaurants are within a mile, or does this delivery zone overlap that one. Plain number indexes cannot handle this because location is two dimensional.
Why ordinary indexes fail
A standard index sorts by a single value, which works in one dimension. Location has both latitude and longitude, so two nearby points may be far apart in any single sort order. Spatial databases need indexes that respect closeness in two dimensions.
Spatial indexes
The common answer is an R tree, which groups nearby shapes into bounding boxes arranged in a tree. A search prunes whole branches whose box does not overlap the query area, so it skips most of the data.
- Range queries find everything inside a box or radius.
- Nearest queries find the closest features to a point.
- Overlap queries test whether two shapes intersect.
Key idea
A spatial database indexes geometry with structures like R trees that prune by bounding box, so location queries skip most data instead of scanning it all.