Geospatial Indexing: Geohash, Quadtree, S2 & H3

"Find drivers near me" is a scaling trap

The naive query, WHERE lat BETWEEN ? AND ? AND lng BETWEEN ? AND ? or worse a full distance scan, cannot use a normal B-tree index effectively (two independent range predicates) and does not scale. Worse, distance on a sphere is not Euclidean. The real problem is turning a 2D nearest-neighbor query into a 1D or hierarchical key you can index, shard, and range-scan.

Geohash: nearby points share a prefix

Interleave the bits of latitude and longitude and encode them base-32 into a short string. The magic property: nearby points share a prefix. 9q8yy and 9q8yz are adjacent cells; truncating the string zooms out. This means a geohash stores trivially in any B-tree or a Redis sorted set and shards by prefix, and a proximity query becomes a prefix range scan. The flaw is boundary problems: two points a meter apart can straddle a cell edge and share almost no prefix. The fix is to query the target cell plus its 8 neighbors (a 3x3 ring) so you never miss a nearby point.

  geohash "9q8yy" and neighbors (query a 3x3 ring to avoid edge misses):
     9q8yw 9q8yx 9q8yz
     9q8yt [9q8yy] 9q8zn      <- center cell + 8 neighbors
     9q8ym 9q8yq 9q8yr

Quadtree, S2, and H3

Quadtree recursively subdivides space into four quadrants, but only where it is dense: a downtown block splits into fine cells while an ocean stays one coarse cell. This adapts to non-uniform density at the cost of maintaining a tree rather than flat key math.

S2 (Google) projects the sphere onto a cube and orders cells along a Hilbert curve, giving excellent spatial locality (nearby cells have nearby ids, so range scans are tight) and true spherical geometry, with 30 levels of precision. H3 (Uber) tiles the world in hexagons. Hexagons matter because every neighbor is equidistant (a square has 4 close and 4 diagonal neighbors), which makes movement, coverage, and radius queries cleaner: exactly what a rideshare or delivery system wants.

Cell size, hot cells, and moving points

The central tuning knob is cell size versus cell count. Finer cells hold fewer points (cheap scans) but a radius query must enumerate more cells; coarser cells mean fewer cells but more points per cell to scan and filter. Rule of thumb: pick a resolution near your typical query radius, query a ring of neighbor cells, then do a final exact-distance filter and sort on the small candidate set.

The failure mode that separates seniors from juniors is the hot cell. A dense downtown or a stadium at concert-end becomes a single cell with a huge point set: a hotspot on both writes and reads. Fixes: subdivide adaptively (quadtree, or drop to a finer S2/H3 resolution just for that cell), cap points per cell, shard hot cells separately so one node does not carry Manhattan, and cache popular cell results.

Interview nuance: for moving points, storage and refresh matter as much as the index. Keep cell_id -> set of driver_ids in Redis and refresh a moving driver on a short TTL so stale positions age out; the source of truth for a driver's live position is the fast store, not your durable DB.

Recap: encode points into a prefix-shareable or hierarchical cell key (geohash, S2, H3) so 2D proximity becomes an indexable/shardable range query, query the cell plus a neighbor ring to beat boundary misses, tune cell size to your query radius, and defuse hot cells by adaptive subdivision, per-cell caps, separate sharding, and caching.