Give space a one-dimensional address
Number map cells so neighbours get nearby IDs. Cover the circle with a few, fetch their rows, then drop anything beyond 2 km.
Geohash plays twenty questions with the map
East half? 1. North half? 1. Alternate, five bits per base32 character. Bandra becomes te7…, and every prefix is its parent cell.
Near means same prefix?
Bad: Scan only your cell
Points 110 m apart in Goregaon share only te7, a 156 km cell.
Good: Cell + 8 neighbours
Cells as big as the radius keep the circle inside the 3×3.
One grid size is always wrong somewhere
A quadtree splits a square in four only when it overflows, giving 0.625 km leaves in a dense core and 5 km in the outskirts.
Geohash cuts degrees: a 5-character cell is 4.9 km wide at the equator, 2.4 km in Helsinki.
The fix
S2 puts a cube around the Earth. Cells vary ≈ 2× in area; each is one ID range.
Squares have two neighbour distances. Hexagons have one.
That’s why Uber buckets surge demand into H3 hexagons. A ring of neighbours is a fair stand-in for a circle.
125k/s
location writes from live drivers
Assume 500,000 drivers pinging every 4 s. Keep only the latest position, in Redis GEO sharded by city, and stream every ping to a log.
Remember
Map 2D to 1D with cells: cover the circle, fetch the cells, filter by true distance. Redis GEO for live drivers, PostGIS for polygons, H3 for surge, S2 for global range scans.