Finding What's Nearby

Geohashes, quadtrees and H3, static places vs moving drivers, and ranking by ETA.

"Restaurants within 2 km", "the nearest available driver", "friends nearby", "stores that deliver to this address": proximity queries search by location, and an ordinary index can't do them well. Two separate indexes on latitude and longitude each return a huge strip of the map, and the database has to intersect them. You need a spatial index that keeps nearby points together.

Two very different workloads

Pin down which one you have first — they lead to different designs:

500k active drivers ÷ 4 s per update = 125,000 location writes/sec

That write rate is why driver locations live in memory, not in a disk-based database.

The spatial indexes

Geohash

Recursively split the world into a grid and encode each cell as a string; every extra character makes the cell 32× smaller. Nearby points usually share a prefix, so a proximity search becomes a prefix lookup in an ordinary B-tree or key-value store.

length 5  ≈ 4.9 km × 4.9 km
length 6  ≈ 1.2 km × 0.6 km
length 7  ≈ 153 m × 153 m

Edge problem: two points across a cell boundary can be metres apart yet share no prefix. Always search the target cell plus its 8 neighbours, then filter by exact distance.

Quadtree

A tree where each node covers a square and splits into four children once it holds too many points (say 100). Dense downtowns get small cells and empty deserts stay as one big cell, so every leaf holds a similar number of points. Great for static places held in memory; awkward when points move constantly, because nodes keep splitting and merging.

Hexagonal grids (H3)

Uber's H3 covers the globe in hexagons at 16 resolutions. Every hexagon's neighbours are the same distance from its centre, which makes "cells within k rings" a good approximation of a circle, and makes per-cell aggregation (drivers per cell, demand per cell) clean. It's widely used for dispatch and pricing.

Database built-ins

You often don't need to hand-roll any of this:

PostGIS (R-tree style GiST indexes): ST_DWithin(location, :point, 2000) — accurate, transactional, fine for millions of places.
Redis GEO (geohash in a sorted set): GEOADD drivers -73.98 40.75 driver:42, then GEOSEARCH drivers FROMLONLAT -73.98 40.75 BYRADIUS 2 km ASC COUNT 20 — ideal for fast-moving objects.
Elasticsearch geo_distance queries — when location is combined with text search and filters.

The query flow

Client -> [Location Service] -> (Geo index: cells around point)
[Location Service] -> [Filter: exact distance + attributes] -> [Rank] -> Client

Convert the user's position into a cell and its neighbours (or a radius query).
Fetch candidates from those cells.
Compute the exact distance (haversine) and drop those outside the radius.
Apply other filters (open now, cuisine, vehicle type), rank (distance, rating, ETA) and return the top results.

Adaptive radius: if the 2 km search returns too few results (rural areas), widen it and search again. If it returns thousands (Manhattan), cap the candidates per cell.

Handling moving objects

Clients send updates every few seconds. Accept them through a lightweight ingestion path; drop stale or out-of-order updates by comparing timestamps.
Keep only the latest location in the hot index, with a short TTL so drivers who disconnect disappear. Send the full history to a log (Kafka → storage) for trip records and analytics.
Reduce update frequency when nothing changes: a parked driver doesn't need to report every 4 seconds.
Shard by region or cell so each index shard handles one area's drivers; a query near a shard boundary asks both shards.

[!TIP] Distance isn't travel time The closest driver by straight-line distance may be across a river. Use the spatial index to get ~20 candidates, then rank them by ETA from a routing service. That two-step pattern — cheap geometric filter, expensive accurate ranking — is the one to describe.

Scaling

Read-heavy static places: replicate the geo index, cache popular searches by (cell, filters), shard by geography if one machine can't hold it.
Write-heavy moving objects: in-memory indexes partitioned by region; avoid a single global sorted set.
Hot spots: stadiums and airports concentrate points in a few cells. Finer cells (or quadtree splitting) in dense areas keep cells balanced.

Privacy

Location is sensitive. Store only what you need, round positions shown to other users ("0.3 km away", not exact coordinates), and expire raw location history on a schedule.

[!INTERVIEW] What a strong answer sounds like "Driver locations come in every 4 seconds — about 125k writes per second — so they go to Redis GEO sets sharded by city, with a 30-second expiry per driver. To match a rider, we query a 3 km radius for the 20 nearest available drivers, then rank those by ETA from the routing service. If fewer than 5 come back, we widen to 6 km. Restaurants are static, so they live in Postgres with PostGIS, and search results are cached per geohash cell and filter."