Why Normal Indexes Fail
A B tree index works on one ordered dimension, but a location has both latitude and longitude. Queries like find points within this region span two dimensions at once, so a one dimensional index cannot prune them well.
Spatial Index Structures
- An R tree groups nearby shapes into bounding boxes that nest inside larger boxes, so a region query skips boxes that do not overlap.
- A space filling curve such as a geohash maps two dimensions to one ordered key while keeping nearby points close in the ordering.
Common Queries
- Nearest neighbor finds the closest points to a location.
- Range finds everything inside a box or polygon.
- Distance filters by how far points are from a center.
Practical Notes
Earth is round, so accurate distance needs spherical math, not flat plane geometry. Spatial extensions add geometry types, the index, and functions that respect coordinate systems.
Key idea
Geospatial indexes like R trees and space filling curves prune two dimensional location data with bounding boxes so nearby and within queries avoid scanning every point.