Geospatial indexing and proximity

“Find drivers near me” looks like a WHERE clause and is not one. A B-tree orders one dimension; nearness lives in two — index latitude and you get a thin useless stripe of the planet; add longitude and the intersection is still wrong at any scale. Space needs structures of its own, and they all share one idea: turn 2-D proximity into 1-D order.

Grids — geohash and friends

Geohash interleaves the bits of latitude and longitude into one sortable string: each added character quarters the cell, and — the payoff — shared prefixes mean shared neighbourhoods. Suddenly a plain B-tree works: index the geohash, and “nearby” becomes a prefix range scan. Two honest defects ship with it. Edges: two points a metre apart can straddle a cell boundary and share no prefix — so every real query checks the cell and its eight neighbours, never the prefix alone. And skew: fixed cells mean Manhattan’s cell holds a million points and Montana’s holds three.

Trees and hexagons

Where density is wildly uneven, adaptive structures earn their complexity: a quadtree splits any cell that exceeds capacity into four — busy cities subdivide deeply, empty plains stay coarse; the R-tree generalises to rectangles and powers “shapes near/containing X” inside PostGIS-style databases. And when the job is analytics over space — surge zones, coverage, supply/demand per area — Uber’s H3 hexagons (this chapter’s reading) fix the squares’ subtle lie: hexagons have six neighbours all at equal distance (squares have eight at two different distances), so “adjacent zones” and gradient-style computations stop being biased by grid geometry.

The moving-object problem

A food-delivery city updates hundreds of thousands of driver locations every few seconds — and here is the trap: treating that as a database problem. Persistent geo-indexes hate hot updates (every move is a delete+insert somewhere). The production shape instead: live location in memory — a hash of cell → driver set, updated in place, rebuilt from the stream on restart (it is a derived view, last chapter’s mindset; losing it loses nothing) — while trips and history land durably elsewhere. Queries then read like this: compute candidate cells for the radius → union their driver sets → exact distance filter on that shortlist → rank. Coarse cells first, precise maths on dozens instead of millions.

Sharding space

Shard by grid cell and the city-centre cell melts — the hot-key problem wearing a map. Shard by coarse region with capacity-aware splits (busy regions get more shards), keep queries region-local, and accept the cross-border query as the scatter-gather it honestly is. The atlas chapter’s ride-matching design is this chapter plus a lock — worth reading them together.