Design nearby / proximity search (Yelp, ride-hailing)
"Find restaurants within 2km" or "show drivers near me." The whole challenge is one question: how do you index location so "what's close to this point?" is fast, when a plain database can only index one column at a time and the earth is two-dimensional? This case study introduces geospatial indexing — geohashing and quadtrees — and the read-heavy vs write-heavy split between a Yelp (static places) and an Uber (moving drivers).
📖 Walk me through it — plain English
Here's why this is hard. A database index is great at "find rows where city = Tokyo" — one column, sorted, binary-searchable. But "find rows within 2km of (lat, lng)" involves two numbers at once (latitude and longitude), and "near" isn't a range on either one alone — a point can be close in latitude but far in longitude. Indexing each column separately and intersecting is slow and clumsy.
The trick is to turn the 2-D location into a single 1-D string such that places that are near each other get strings that share a prefix. That's a geohash: it chops the world into a grid of cells, gives each cell a short code, and nearby cells share leading characters. Now "find nearby" becomes "find rows whose geohash starts with the same prefix as mine" — which is just a normal prefix lookup a database does fast. You've converted a hard 2-D problem into the easy 1-D problem you already know how to index.
The second half is the difference between Yelp and Uber. Yelp's restaurants barely move, so you index once and the system is almost all reads — easy. Uber's drivers move every few seconds, so the location index is being rewritten constantly; the hard part shifts to handling a torrent of writes without melting. Same indexing idea, opposite load profile — and a great place to show you read the workload before choosing a design.
Step 1 · The core problem & the geohash idea
A geohash encodes a (latitude, longitude) into a short string by repeatedly splitting the world in half. Is the point in the east or west half? Record a bit. North or south of that? Another bit. Each split halves the region; more characters = a smaller, more precise cell. The payoff property: two nearby points share a long common prefix. A 5-character geohash is roughly a 5km cell; 6 characters ≈ 1km; 7 ≈ 150m. So you pick a precision matching your search radius and query by prefix.
The query. To find everything near point P: compute P's geohash at your chosen precision, then fetch all rows whose geohash shares that prefix — they're in the same cell. One catch, and interviewers love it: a point near a cell edge has close neighbors in the adjacent cell with a different prefix. The standard fix is to query your cell plus its 8 neighboring cells (a 3×3 block), then filter by exact distance. Naming the edge problem and the 8-neighbor fix is the detail that separates a memorized answer from an understood one.
The alternative structure is a quadtree: recursively split a region into four quadrants, splitting a quadrant further only where points are dense. It adapts to clustering (a dense city subdivides finely; empty ocean stays one big cell), whereas a fixed-precision geohash uses uniform cells. Geohash is simpler and rides on any string index; a quadtree handles wildly uneven density better. Either is defensible — say the tradeoff.
Step 2 · Yelp — static places, read-heavy
Restaurants almost never move, so write the geohash once into an indexed column and you're done. The system is overwhelmingly reads: precompute aggressively, cache hot areas (downtown queries repeat constantly), and add read replicas. A query is "geohash my location + 8 neighbors, fetch matching places, filter by exact distance, rank by rating/distance." This is the easy mode — and recognizing that lets you spend your time on the harder variant.
Step 3 · Uber — moving drivers, write-heavy
Now every driver pings their location every few seconds. With a million online drivers that's hundreds of thousands of writes per second into the location index — the load profile flips entirely. The senior moves:
- Keep the live index in memory, not on disk — driver locations are ephemeral (a 3-second-old position is worthless), so an in-memory geospatial store (e.g. Redis geo) absorbs the write churn without disk I/O.
- Shard by geohash region so each server owns a geographic area and its writes — the load spreads with the map. Watch for hot regions (rush-hour downtown) and split them finer.
- Don't persist every ping. The index is a fast, lossy view; you only durably log what you need (trips, billing). Distinguishing "must be durable" from "can be lost" is exactly the cache insight from two lessons ago.
- Accept staleness. A rider seeing a driver's position a few seconds old is fine. You explicitly trade freshness for surviving the write rate.
Pitfalls
Querying only your own geohash cell misses near neighbors just across the boundary. Always query the 3×3 block of neighboring cells, then filter by true distance.
Persisting every driver ping to a relational table melts under write load. Moving objects belong in an in-memory, lossy index, not durable storage.
A 5km cell is wrong for a 100m "drivers on this block" query. Match geohash precision to the search radius, or you scan far too much.
Sharding by region concentrates rush-hour downtown on one node. Split dense regions finer (the quadtree instinct) so no shard melts.
Takeaway: proximity search is "turn 2-D into 1-D so a normal index works." A geohash maps location to a string where nearby points share a prefix — query your cell plus its 8 neighbors and filter by exact distance; a quadtree is the density-adaptive alternative. Then read the workload: static places (Yelp) are a read-heavy cache-and-replicate problem; moving objects (Uber) flip to write-heavy, demanding an in-memory, region-sharded, deliberately-lossy index. Spotting that the same index has two opposite load profiles is the whole signal.
→ Going deeper: the geohash-prefix trick echoes the trie prefix walk in autocomplete; the in-memory lossy index is the distributed cache insight; region sharding and hot shards come from scaling primitives.