Why can’t you just index businesses on latitude and longitude columns?

Because a normal database index is one-dimensional — it sorts rows along a single axis. Put a B-tree on latitude and it can quickly hand you every business in a horizontal band of the world; put one on longitude and it gives you a vertical band. But "near me" is the small square where those two bands overlap, and the database has no single index that understands the intersection. It has to pull one enormous band — every business at your latitude, coast to coast — and then filter almost all of them out by longitude, or intersect two huge lists. At city scale that is millions of rows scanned to return a dozen. The fix is to collapse the two dimensions into one sortable key that keeps nearby points nearby, which is exactly what a geohash or a quadtree does.

What is a geohash and how does it work?

A geohash is a short string — like 9q8yy — that names a rectangular cell on the Earth’s surface. You build it by repeatedly halving: is the point in the east or west half of the world? Note one bit. North or south half of that? Another bit. Keep alternating longitude and latitude, and every bit shrinks the box around the point by half. Group the bits five at a time, encode each group as one base-32 character, and you get the string. The key property is that the prefix is the zoom level: 9q is a big region, 9q8yy is a roughly five-kilometre cell, 9q8yyk a smaller one — and because a longer shared prefix means a smaller shared box, two points with the same prefix are usually close. That turns "find nearby" into "find rows whose geohash starts with these characters," which an ordinary string index answers instantly. As the movable-type reference puts it, "at each level, each extra character identifies one of 32 sub-cells."

Why does a geohash proximity search need to check neighboring cells?

Because the prefix trick has a sharp edge: two points can be metres apart yet sit in cells that share almost no prefix, whenever they straddle a boundary in the grid. The movable-type reference gives the extreme case — "in France, La Roche-Chalais (u000) is just 30km from Pomerol (ezzz)" — two neighbors whose geohashes disagree from the very first character. So a search that only matches your own cell’s prefix will silently miss businesses that are genuinely close but happen to fall just across a cell line, and it returns no error while doing it. The standard fix is to compute the eight cells surrounding yours and query all nine: "a reliable prefix search for proximate locations will also search prefixes of a cell’s 8 neighbours." That is the difference between a correct nearby search and one that quietly drops results near every boundary.

Geohash vs. quadtree vs. S2 — which spatial index should you use?

All three turn 2-D coordinates into an indexable form; they differ in how they handle uneven density and how easy they are to operate. A geohash is a fixed grid encoded as a string — dead simple, works with any B-tree or sorted set (Redis builds its geo commands on exactly this), and is the right default for read-heavy search over data that rarely moves, which is what a business finder is. Its weakness is uniform cells: a dense downtown cell holds far more points than an empty rural one. A quadtree fixes that by subdividing only where it is crowded — each node splits into four children once it exceeds a capacity — so it adapts to density and answers k-nearest-neighbor naturally, at the cost of being a tree you must build in memory and update as points move. Google’s S2 maps the sphere onto a Hilbert space-filling curve, avoiding the rectangular distortion geohash has near the poles and giving very good locality — "if the S2CellIds of two cells are close together, then the cells are also close together" — but it is the most complex to reason about. For a static, read-heavy proximity service the deliberation usually lands on geohash for its operational simplicity.

How does a "nearby friends" feature differ from a proximity search?

A proximity search reads mostly-static data — businesses do not move — so you can precompute geohashes, cache aggressively, and treat it as a read-heavy problem. "Nearby friends" inverts that: every user is a point that moves continuously, so the workload becomes write-heavy, with a location update arriving every few seconds per active user. The design shifts accordingly. Each geohash cell becomes a pub/sub channel; a user subscribes to their own cell plus its eight neighbors (nine channels) over a long-lived WebSocket connection, and every location update is published to the sender’s cell, fanning out only to the handful of people watching it. Positions live in a TTL’d cache rather than a durable store, because a location three minutes stale is worthless anyway. It is the same geohash grid, but read as a routing key for live events instead of a filter for a stored query — and it costs far more writes.

Design a Proximity Service

Open a maps app, tap "restaurants near me," and a few of the 200 million businesses on Earth come back in under a second. This is the retrieval shape under Yelp, "find nearby drivers," and every store locator — built from zero: why a plain index on latitude and longitude quietly falls apart, geohash derived by hand (recursive halving, prefix as zoom, base-32) with the two boundary traps that make a naive query silently miss results and the eight-neighbor fix that catches them, an honest geohash-vs-quadtree-vs-S2 deliberation, the compound-row data model, the read path and why the user’s own coordinates are a terrible cache key — then "when the points move": nearby-friends over a pub/sub channel per cell and a WebSocket fleet, honest about the write volume it costs.

System design · Systems. The source ↗

A free, interactive, animated visual explainer of Design a Proximity Service — built to be understood, not skimmed.

Questions

Why can’t you just index businesses on latitude and longitude columns?: Because a normal database index is one-dimensional — it sorts rows along a single axis. Put a B-tree on latitude and it can quickly hand you every business in a horizontal band of the world; put one on longitude and it gives you a vertical band. But "near me" is the small square where those two bands overlap, and the database has no single index that understands the intersection. It has to pull one enormous band — every business at your latitude, coast to coast — and then filter almost all of them out by longitude, or intersect two huge lists. At city scale that is millions of rows scanned to return a dozen. The fix is to collapse the two dimensions into one sortable key that keeps nearby points nearby, which is exactly what a geohash or a quadtree does.
What is a geohash and how does it work?: A geohash is a short string — like 9q8yy — that names a rectangular cell on the Earth’s surface. You build it by repeatedly halving: is the point in the east or west half of the world? Note one bit. North or south half of that? Another bit. Keep alternating longitude and latitude, and every bit shrinks the box around the point by half. Group the bits five at a time, encode each group as one base-32 character, and you get the string. The key property is that the prefix is the zoom level: 9q is a big region, 9q8yy is a roughly five-kilometre cell, 9q8yyk a smaller one — and because a longer shared prefix means a smaller shared box, two points with the same prefix are usually close. That turns "find nearby" into "find rows whose geohash starts with these characters," which an ordinary string index answers instantly. As the movable-type reference puts it, "at each level, each extra character identifies one of 32 sub-cells."
Why does a geohash proximity search need to check neighboring cells?: Because the prefix trick has a sharp edge: two points can be metres apart yet sit in cells that share almost no prefix, whenever they straddle a boundary in the grid. The movable-type reference gives the extreme case — "in France, La Roche-Chalais (u000) is just 30km from Pomerol (ezzz)" — two neighbors whose geohashes disagree from the very first character. So a search that only matches your own cell’s prefix will silently miss businesses that are genuinely close but happen to fall just across a cell line, and it returns no error while doing it. The standard fix is to compute the eight cells surrounding yours and query all nine: "a reliable prefix search for proximate locations will also search prefixes of a cell’s 8 neighbours." That is the difference between a correct nearby search and one that quietly drops results near every boundary.
Geohash vs. quadtree vs. S2 — which spatial index should you use?: All three turn 2-D coordinates into an indexable form; they differ in how they handle uneven density and how easy they are to operate. A geohash is a fixed grid encoded as a string — dead simple, works with any B-tree or sorted set (Redis builds its geo commands on exactly this), and is the right default for read-heavy search over data that rarely moves, which is what a business finder is. Its weakness is uniform cells: a dense downtown cell holds far more points than an empty rural one. A quadtree fixes that by subdividing only where it is crowded — each node splits into four children once it exceeds a capacity — so it adapts to density and answers k-nearest-neighbor naturally, at the cost of being a tree you must build in memory and update as points move. Google’s S2 maps the sphere onto a Hilbert space-filling curve, avoiding the rectangular distortion geohash has near the poles and giving very good locality — "if the S2CellIds of two cells are close together, then the cells are also close together" — but it is the most complex to reason about. For a static, read-heavy proximity service the deliberation usually lands on geohash for its operational simplicity.
How does a "nearby friends" feature differ from a proximity search?: A proximity search reads mostly-static data — businesses do not move — so you can precompute geohashes, cache aggressively, and treat it as a read-heavy problem. "Nearby friends" inverts that: every user is a point that moves continuously, so the workload becomes write-heavy, with a location update arriving every few seconds per active user. The design shifts accordingly. Each geohash cell becomes a pub/sub channel; a user subscribes to their own cell plus its eight neighbors (nine channels) over a long-lived WebSocket connection, and every location update is published to the sender’s cell, fanning out only to the handful of people watching it. Positions live in a TTL’d cache rather than a durable store, because a location three minutes stale is worthless anyway. It is the same geohash grid, but read as a routing key for live events instead of a filter for a stored query — and it costs far more writes.

Design a Proximity Service

Questions

Related explainers