Geospatial Indexing: How 'Drivers Near Me' Actually Works

Type "find drivers within 2km of me" as SQL and the trap springs immediately:

SELECT * FROM drivers
WHERE lat BETWEEN 12.90 AND 12.94
  AND lng BETWEEN 77.58 AND 77.62;

A B-tree index can satisfy one of those range predicates. It narrows by latitude — every driver in that horizontal band around the entire city — then filters longitude row by row. Composite indexes do not fix this: B-trees order by one dimension, then the next, so nearby points in 2D are far apart in the index. Proximity search needs an index where spatial closeness becomes key closeness. Every real solution is a different way of flattening 2D into 1D while approximately preserving neighborhoods.

Geohash: the world as nested cells

Interleave the bits of latitude and longitude — one bit of each, alternating, each bit halving the world — and encode the result in base32. That is geohash. The property that matters: a shared prefix means shared containment. Every point whose geohash starts with tdr1w lies inside one ~5km × 5km cell; add a character and you subdivide into 32 child cells of ~1km.

Suddenly the unanswerable 2D query is a string prefix scan:

SELECT * FROM drivers WHERE geohash LIKE 'tdr1w%';

— which a plain B-tree executes beautifully. This is the whole trick, and it is why geohash-style encoding sits under Redis GEO commands, DynamoDB geo libraries, and half the "nearby" features you have used. In Redis:

GEOADD drivers 77.5946 12.9716 driver:42
GEOSEARCH drivers FROMLONLAT 77.60 12.97 BYRADIUS 2 km ASC

Under the hood: encode into a 52-bit interleaved integer, store in a sorted set, answer radius queries by scanning the handful of cell ranges that cover the circle.

The boundary problem. Two points a meter apart can straddle a cell edge and share no prefix — famously, points just across certain meridian lines share barely any characters. A rider standing at a cell boundary would see drivers to their east and miss closer ones to their west. The fix is mechanical but mandatory: query the target cell and its 8 neighbors, then distance-filter the union. Any geohash implementation without a neighbors step is a bug with a demo.

Second wrinkle: cells are lat/lng rectangles, so their physical width shrinks near the poles. Irrelevant for a city, real for a global product.

Quadtrees: adaptive where geohash is uniform

Geohash divides the world uniformly — dense downtown and empty ocean get the same cell size. A quadtree divides adaptively: start with one cell for the world, and whenever a cell exceeds a capacity (say 100 points), split it into four quadrants, recursively. Manhattan ends up in tiny leaves; Nevada stays one giant leaf. Nearby search walks down to the target leaf and expands outward through sibling leaves until it has enough candidates.

The trade: beautifully balanced query cost in skewed data, but it is an in-memory pointer structure you must build, rebalance as points move, and shard yourself. Geohash needs none of that — the "tree" is implicit in the string, computed from coordinates alone, no global structure to maintain. That is exactly why geohash-style flattening dominates in distributed systems: cell ID computation requires no coordination, and the cell ID doubles as a shard key.

The polished descendants fix geohash's cell-shape problems: Google's S2 projects the sphere onto a cube and subdivides along a space-filling curve, giving near-uniform cells and clean radius coverings. Uber's H3 uses hexagons — every neighbor is equidistant, which flattens the awkward corner-neighbor geometry of squares — and Uber built it explicitly for driver dispatch and per-cell surge pricing. PostGIS, meanwhile, uses R-trees (bounding-box trees) via GiST indexes: the right answer when your data is polygons and routes rather than points.

Designing the ride-matching path

Assemble the pieces for an Uber-style "match me with nearby drivers":

Ingest. Drivers report location every ~4 seconds. Millions of drivers means hundreds of thousands of writes per second of ephemeral state — this does not belong in your relational database. Keep the live index in memory (Redis GEO or an in-process index per city), sharded by city or by coarse cell. Persist trip history elsewhere, asynchronously.

The moving-driver update. Each ping is delete-from-old-cell, insert-into-new-cell on the index. Cheap trick that halves the load: skip the update when the driver has not left their current cell.

Query. Rider requests: compute the rider's cell, gather candidates from it plus neighbors (expand rings until you have ~20 candidates), exact-distance filter, then rank — not by straight-line distance but by ETA, which means a road-network lookup on the shortlist. Geometry generates candidates; routing picks the winner.

Hot cells. A stadium empties and one cell holds thousands of drivers and riders. Adaptive schemes shine here; with fixed-resolution cells you handle it by querying finer resolutions in dense areas — or accept the scan, since even a few thousand candidates filter in single-digit milliseconds.

Takeaways

Proximity search is an index-shape problem: B-trees answer one dimension, so every geo system flattens 2D into prefix-friendly cell IDs — geohash by bit interleaving, S2 and H3 with better-shaped cells, quadtrees adaptively in memory. Always search neighbor cells (the boundary problem is not optional), separate the ephemeral live index from durable storage, and generate candidates with geometry but rank with ETA. Cell IDs that need no coordination to compute are the property that makes the whole thing shard.