Open Yelp, ask for coffee shops within a mile, and results come back instantly. Under that simple request is a genuinely hard database question: how do you efficiently find all points near a given point when you have tens of millions of points and a globe to spread them across. A plain database index does not help here, because "near" is a two-dimensional idea and ordinary indexes are one-dimensional.
The core problem
Suppose every place is a row with a latitude and longitude. To find places near you, the brute-force approach computes the distance from you to every single place and keeps the close ones. That is a full scan on every search. It works for a thousand rows and dies at ten million. You need a way to prune, to look only at places that could plausibly be near, without touching the rest.
The difficulty is that a normal B-tree index on latitude, or on longitude, only orders one axis. You can quickly find places in a latitude band, but they could be on the other side of the planet by longitude. Two-dimensional proximity needs a two-dimensional index.
Key design decisions
Turn 2D location into a 1D key with a space-filling curve. The clean trick is geohashing. You recursively divide the world into a grid and encode a location as a short string where each added character narrows the box. Nearby places usually share a prefix. So "find things near me" becomes "find things whose geohash starts with the same prefix as mine", which a normal string index handles beautifully. The precision of the prefix controls the search radius.
Handle the edge cases of grid cells. Geohashing has a known catch: two points can be physically close but sit in adjacent cells with different prefixes, right across a boundary. The fix is to query your cell plus its eight neighbors, then filter by true distance. You accept a little extra reading to avoid missing a place that is close but on the wrong side of a line.
Or use a purpose-built spatial index. Databases offer quadtrees and R-trees, and Postgres with PostGIS gives you a GiST index over geometry that answers "within this radius" or "inside this box" directly. These structures partition space so a query descends only into regions that overlap your search area. Geohash-in-a-string-index and a real spatial index solve the same problem; the choice is about your stack and your scale.
Filter, then refine. Whatever the index, it gives you candidates in a bounding region, not an exact answer. You still compute real distances on that small candidate set, sort by distance, and apply the other filters people actually want: open now, rating, price, category. The index makes the candidate set small; the refinement makes the answer correct.
Scaling the reads
Proximity search is read-heavy and the data changes slowly, so it caches well. Popular areas (a downtown at lunchtime) get hammered, so caching results per geohash cell for a short window absorbs a lot of load. Sharding by geographic region keeps each shard's index small and keeps a query for one city off the machines serving another continent.
How the real systems do it
Yelp, Uber, and similar location services lean on geospatial indexing. Uber's H3 library uses hexagonal cells instead of rectangles because hexagons have uniform distance to all neighbors, which makes proximity and coverage math cleaner. The common pattern everywhere is the same two-step: use a spatial index to cut the world down to a handful of candidate cells, then compute exact distances and business filters on that small set. The heavy lifting is always about pruning the search space before you ever measure a distance.
What carries into an interview: proximity is a 2D problem, ordinary indexes are 1D, and the whole game is mapping location to a key that groups nearby things together so you can prune first and measure second.
I wrote the full breakdown, with geohash internals and the query flow, here: https://www.systemdesign.academy/interview/design-yelp
Top comments (0)