Spatial Index
Spatial indexes (R-tree, K-D tree, GeoHash) optimize 2D/3D spatial queries (range, nearest-neighbor, containment).
Purpose
To understand geospatial query optimization and design LBS and GIS systems.
Mechanism
The R-tree organizes spatial objects by MBR (minimum bounding rectangle) into a balanced tree; queries filter quickly via rectangle intersection. GeoHash encodes coordinates into 1D strings indexed by B-Tree. PostGIS uses GiST R-trees.
Use cases
- LBS query optimization
- GIS system design
- Spatial range queries