Geospatial Indexing
Studies in this cluster, in series order. Each one keeps its own URL.
System design
Capacity, trade-offs, and request paths you can defend on a whiteboard.
Geospatial Indexing
6 studies- 1.Geospatial Indexing — Cells, Trees & Proximity at ScaleRide-hail, delivery, and maps live or die on nearby search. Index lat/lng with cells (geohash, S2, H3), adaptive trees (quadtree), or MBR trees (R-tree). Always fan out neighbors and filter true distance.
- 2.Geohash — Prefix Locality, Encoding, Precision & Edge CasesGeohash turns lat/lng into a base32 string (or interleaved int) whose shared prefixes mean spatial locality — until a cell border. Encode cheaply, pick precision from radius, fan out neighbors, then haversine-filter.
- 3.Quadtrees & Space Partitioning — Adaptive Cells, Density & UpdatesQuadtrees split a 2D region into four children when a capacity threshold is hit. Depth follows density — downtown deep, desert shallow. Cheap in-process; awkward as a durable cross-service shard key for moving objects.
- 4.R-Trees & R-star — MBRs, Bulk Load & Range/KNN QueriesR-trees index rectangles via nested minimum bounding rectangles. Databases (PostGIS GiST) use them for range, intersect, and kNN. Bulk-load static POIs; do not page-split a moving fleet — keep cells for membership.
- 5.S2 & H3 — Hierarchical Hex/Cell IDs (Uber/Lyft-Style Designs)S2 maps the sphere to Hilbert-ish cell IDs; H3 is a hex hierarchy with k-rings. Ride-hail and delivery key membership, shards, and heatmaps by those IDs. Pick hex for uniform rings, S2 for spherical coverings — this is public architecture, not one private paper.
- 6.Location Services — Nearby Search, Dispatch Shards & HotspotsIndexes are useless without ingest, cell shards, bounded fan-out, ranking, and airport-scale hotspot splits. Nearby is encode plus k-ring plus haversine; assignment needs CAS on the driver. Cells, not one global tree, carry the fleet.