How "nearby" actually works?
A code-dependent life form.
Every time I type "sushi near me" into a maps app, I get a list of places in well under a second. I had never really thought about what happens behind that search. It feels simple. You have my location, you have a list of cafés, just find the close ones.
Then I read the first chapter of System Design Interview (II), "Design a Proximity Service", and realised the hard part is not the idea. It is doing it for hundreds of millions of places, thousands of times a second, without scanning the whole world on every request.
What we are building
Think of something like Yelp or the "nearby" tab in a maps app. The chapter keeps the scope tight:
Search: given a user's latitude, longitude and a radius, return businesses inside that radius.
Manage: business owners can add, update or delete a listing. These changes do not need to show up in real time. Next day is fine.
View: users can open a business and see its details.
On the non-functional side, search has to be fast, location data is personal (so privacy laws like GDPR and CCPA apply), and the system must handle spikes at busy hours like lunchtime.
The rough numbers the book uses:
100 million daily active users and 200 million businesses.
Each user searches about 5 times a day.
100M × 5 ÷ 100,000 seconds in a day (rounded) gives roughly 5,000 search queries per second.
The key takeaway: this is a read-heavy system. Writes are rare and can lag. That one fact shapes almost every decision later.
API & The Design
Only two groups of endpoints matter.
GET /v1/search/nearby?latitude=37.77&longitude=-122.41&radius=5000
GET /v1/businesses/{id}
POST /v1/businesses
PUT /v1/businesses/{id}
DELETE /v1/businesses/{id}
Radius is in metres and defaults to 5 km. Search results would be paginated in a real system, but the chapter keeps that out of the way.
Location-based service (LBS): handles search. It is stateless and read-only, so I can add servers at peak hours and remove them at night.
Business service: handles owner edits (low traffic) and business detail views (high traffic, easy to cache).
Database: a primary for writes and several read replicas for reads. A little replication lag is fine because updates are allowed to be slow.
Searching a map
My first instinct was a plain SQL query:
SELECT business_id FROM business
WHERE latitude BETWEEN :lat - :r AND :lat + :r
AND longitude BETWEEN :lng - :r AND :lng + :r;
This works on a laptop and falls apart at scale. A normal database index works on one dimension. Even with an index on each column, the database pulls a huge strip of rows for latitude, another huge strip for longitude, and then intersects them. Most of that work is thrown away.
The fix is to turn a 2D problem into a 1D one, so a regular index can do its job. The book groups the options into two families:
Hash based: evenly divided grid, geohash.
Tree based: quadtree, Google S2 (and R-tree, which it mentions briefly).
An even grid
Split the world into equal squares and store which square each business sits in. Simple, but the world is not evenly populated. One square in central London might hold thousands of restaurants while a square over the Pacific holds none. Fixed cells either become too big for cities or too wasteful everywhere else.
Geohash
Geohash was the idea that clicked for me. It keeps splitting the map into four and writes down which quarter you are in.
After enough splits you get a short string like 9q8yyk (hashed). The nice property: places that share a longer prefix are usually closer together. So a nearby search becomes a prefix lookup, which any database index handles well.
The length of the string decides the size of the cell. The chapter shows that only lengths 4 to 6 really matter for this kind of search:
| Geohash length | Cell size (approx.) | Used for radius |
|---|---|---|
| 4 | 39.1 km × 19.5 km | 5 km, 20 km |
| 5 | 4.9 km × 4.9 km | 1 km, 2 km |
| 6 | 1.2 km × 609.4 m | 0.5 km |
The rule is simple: pick the longest geohash whose cell still covers the search circle.
The boundary catch
This is where geohash gets tricky, and the book spends good time on it.
Close but different prefix: two cafés on either side of the equator or the prime meridian can be metres apart yet share no prefix at all.
Close but different cell: I might stand at the right edge of my cell while the best café is just across the line in the next one.
The fix is to fetch businesses from my cell plus its 8 neighbours, then filter by real distance. Neighbours can be computed in constant time, so this is cheap. And if there still are not enough results, I drop the last character of the geohash to widen the search.
Quadtree
A quadtree solves the density problem directly. Start with the whole world as one node. If a node holds more than a set number of businesses (the book uses 100), split it into four children. Repeat until every leaf is under the limit.
Things I found worth remembering:
It lives in memory, not in the database. Each LBS server builds its own tree at startup.
For 200 million businesses the book estimates about 2 million leaves and around 1.71 GB of memory. That fits on one server easily.
Building it takes a few minutes, so a new server cannot take traffic straight away. Roll out new servers a few at a time.
Updating the tree when a business changes is harder than updating a geohash row. Since next-day updates are acceptable, a nightly rebuild is a reasonable choice.
It is great for "give me the 10 closest places", because you can keep expanding until you have enough.
A quick word on Google S2
S2 maps the sphere onto a Hilbert curve, which keeps points that are close in the real world close on a 1D line. It shines for geofencing and covering odd-shaped areas. The book notes it is powerful but harder to explain in an interview, so geohash or quadtree is the safer choice there.
Comparing the options
| Approach | Idea | Strength | Weakness |
|---|---|---|---|
| 2D search | Range query on lat and long | Simplest to write | Slow at scale, two indexes to intersect |
| Even grid | Fixed squares | Easy to reason about | Ignores uneven density |
| Geohash | Recursive grid as a string | Prefix queries, easy updates | Fixed cell sizes, boundary cases |
| Quadtree | Tree that splits dense areas | Adapts to density, k-nearest | In memory, slow to build, harder updates |
| Google S2 | Sphere on a Hilbert curve | Geofencing, any region shape | Complex to explain and operate |
And the head-to-head that matters most:
| Geohash | Quadtree | |
|---|---|---|
| Where it lives | Database table or cache | Memory on each server |
| Cell size | Fixed per precision | Changes with density |
| Updating a business | Add or remove one row | Walk and edit the tree, mind locking |
| k-nearest search | Awkward | Natural |
| Startup cost | Nothing to build | A few minutes per server |
Storing and caching it
With geohash, the index table has one row per business:
geospatial_index
geohash -- (part of compound key)
business_id -- (part of compound key)
SELECT business_id FROM geospatial_index
WHERE geohash LIKE '9q8zn%';
The book compares this with storing a JSON list of IDs per geohash and prefers one row per business, because adding or removing a business is a single-row change with no locking.
Index table: small enough to keep whole. No sharding, just add read replicas for more read capacity.
Business table: large, so shard it by business ID.
Cache key: not raw latitude and longitude, since they change with every step a user takes. Use the geohash instead.
Two Redis caches: geohash to list of business IDs (precomputed for lengths 4, 5 and 6, roughly 5 GB), and business ID to business details.
This is why the "next day is fine" requirement matters so much. It lets the caches be refreshed by a nightly job instead of on every write.
Putting it all together
Here is the full journey of one search, from my phone to the result list:
Start from the read/write ratio. Knowing this is read heavy with relaxed freshness explained most of the design.
Indexes are one dimensional. Most geospatial tricks are just clever ways to flatten a map into a line.
Geohash is the simple default. Easy to store, easy to update, easy to cache. Just remember the neighbours.
Quadtree earns its place when density varies a lot or when you need the k nearest results.
Cache on what stays stable. A geohash stays the same while a user walks around. Raw coordinates do not.
If you ever need help or just want to chat, DM me on Twitter / X or LinkedIn.
