Geospatial Indexing

Overview

Geospatial indexing organizes location data so that "find everything near this point" is fast, instead of scanning every row and computing distance. The core trick is to reduce two dimensions (latitude, longitude) to a one-dimensional key that preserves proximity, so nearby places end up near each other in the index. Geohash, quadtrees, and Google's S2 are the dominant schemes.

🧠 Mental model: Imagine folding a paper map into ever-smaller labeled squares. A geohash is the label: the more letters it shares with your square, the closer it is. To find neighbors, you just look at squares whose labels start the same way - no need to measure distance to every city on Earth.

Key Concepts

The central idea is a space-filling curve that maps 2-D coordinates to a 1-D sortable key while keeping nearby points close in that ordering.

Geohash recursively divides the world into a grid and encodes each cell as a base-32 string. Longer strings mean smaller, more precise cells, and a shared prefix means physical proximity. A radius query loads the target cell plus its 8 neighbors (to handle points near an edge) and filters precisely.

Quadtree recursively splits a region into four quadrants, subdividing only where data is dense. This adapts to skew - a dense downtown gets fine cells while an empty desert stays coarse - at the cost of a tree that must be rebalanced as data shifts.

S2 (Google) projects the sphere onto a cube and uses a Hilbert curve for excellent locality; H3 (Uber) uses hexagons, whose uniform neighbor distances simplify "expanding ring" searches.

Scheme	Cell shape	Adapts to density?	Notes
Geohash	Rectangle	No (fixed grid)	Simple, prefix = proximity, easy to shard
Quadtree	Square	Yes	Handles skew; needs rebalancing
S2	Spherical quad	No	Great locality via Hilbert curve
H3	Hexagon	No	Uniform neighbors, clean ring queries

Because a geohash prefix is a normal string, it plugs directly into ordinary database indexing and into sharding: shard by geohash cell so each node owns a bounded region.

Trade-offs

Fixed grids (geohash, S2) are simple, stateless, and trivially shardable, but they waste resolution in empty areas and can create hotspots where population is dense. Quadtrees adapt to density and avoid that waste, but they hold mutable tree state that must be rebalanced and replicated, which is harder under heavy write load like live driver locations. There is also an edge effect in every grid scheme: the nearest point may sit just across a cell boundary, so you must always query neighboring cells, not just the target cell.

Interview Tips

For "find nearby," say "encode locations with a geohash and query the cell plus its 8 neighbors, then rank by exact distance."
Choose a quadtree/H3 when density is highly uneven (cities vs. countryside); choose plain geohash for simplicity.
Shard by geo cell so each node owns a region - this is how ride-sharing spreads location write load.
Always mention the edge-of-cell problem; forgetting neighbor cells is a classic correctness miss.

Summary

Geospatial indexing maps 2-D coordinates to a 1-D proximity-preserving key for fast nearest-neighbor queries.
Geohash encodes cells as base-32 strings where a shared prefix means physical closeness.
Quadtrees adapt to data density; S2 and H3 offer better locality and cleaner neighbor queries.
Grid keys plug straight into normal indexes and shard cleanly by cell.
Always query neighboring cells to avoid missing points just across a boundary.