What's near you,
right now

Strip both products down and you get the same core request: given a point and a radius r, return every interesting thing inside that circle. For a proximity service the "things" are businesses; for Nearby Friends they're people. The query is identical. What differs is everything around it.

• Proximity search is read-heavy. The set of restaurants in a city changes maybe a few times a day. But it's read constantly, from every phone. So you build a precomputed index once, keep it on disk, replicate and cache it heavily, and optimize purely for fast reads. Staleness of a few minutes is fine — a new cafe can wait.
• Nearby Friends is write-heavy. Each phone reports its location every few seconds. With millions of users that's a firehose of writes, and each location is only interesting for a few seconds before it's replaced. There's almost nothing to "store" long-term; you need an in-memory pipe that ingests updates fast and pushes them out to the right people instantly.

Hold that contrast in your head for the whole chapter. Sections 2–5 build the read-heavy index. Section 6 flips to the write-heavy live case. The geometry is shared; the storage and dataflow are nearly opposites.

Your first instinct is right and reasonable: store every place with its latitude and longitude, draw a little box around the user, and ask for everything inside it.

A circle is awkward in SQL, so you approximate it with a square — a bounding box. If the user is at (lat₀, lng₀) and wants everything within roughly r, you query for rows where the latitude is between lat₀ − δ and lat₀ + δ and the longitude is between lng₀ − δ and lng₀ + δ. (Then you can throw out the corners later to make it a true circle.)

It returns the right answer. It's just slow, and the reason is subtle. A normal database index is a sorted list of one column. An index on lat can instantly find the latitude band — but within that band the matching rows are scattered all over the world by longitude, so the database still has to check every one of them against the longitude condition. An index on lng has the mirror problem. The database can use one of your two conditions to narrow things down, then grinds through the rest by hand. In a dense city that's a huge number of rows for every single query.

You might think "I'll just index both columns together." A combined (lat, lng) index sorts by latitude first, then longitude — so it's great at "this exact latitude, these longitudes," but a range on the first column already wrecks the ordering of the second. Two dimensions simply don't fold neatly into one sorted line. That mismatch is the entire motivation for the rest of this chapter: we need a way to turn a 2D neighborhood into something a 1D index can chew on.

Here's the trick, in plain English: chop the map into a grid of cells and give each cell a short code, arranged so that nearby places share a code prefix. Then "find things near me" becomes "find things whose code starts with the same letters as mine" — and matching a prefix is something a plain old string index does beautifully. That coding scheme is called geohash.

It's built by repeated halving. Split the world into a left half and a right half by longitude — write down a 0 or 1 for which half your point is in. Now split by latitude — another bit. Keep alternating: longitude, latitude, longitude, latitude, each split zooming you into a quarter of the previous cell. Group those bits five at a time and translate each group into one character (using 32 symbols: digits and most letters). The result is a string like dr5ru7.

The beautiful part: the length of the string is the precision. One character pins you to a giant region (~5000 km across); six characters narrow it to a city block (~1.2 km); nine characters get you to a few meters. Want a coarser search? Chop characters off the end. Want finer? Add more. And because the bits were assigned by zooming in, two points in the same neighborhood agree on their leading characters — dr5ru7 and dr5ru2 are neighbors; sharing dr5ru means they're in the same little cell.

To find everything near a point, you compute its geohash at the precision matching your radius, then ask the database for every row whose geohash starts with that prefix. One indexed prefix scan replaces the whole scattered bounding-box grind.

The boundary problem

There's one catch, and it bites everyone the first time. Two points can be just a few meters apart yet sit on opposite sides of a cell border — so their geohashes diverge early and share no useful prefix. Your coffee shop is right across the street, but it's in cell dr5rv while you're in dr5ru, and a pure prefix search misses it entirely.

The fix is to query the neighbors too. From a geohash you can compute the codes of the eight cells touching it (north, south, east, west, and the diagonals). Search your own cell plus all eight, and any point that's genuinely close — even one sitting just over a border — is guaranteed to be in one of those nine cells. Drag the pin below and watch the code grow as you zoom in, with the neighbor cells highlighted.

Geohash uses a fixed grid: every cell at a given precision is the same size, whether it covers downtown Manhattan or the open ocean. That's wasteful — empty cells cost you nothing useful, and one cell over a dense city can still hold thousands of points. A quadtree fixes this by subdividing the map adaptively, putting fine detail only where the points actually are.

The rule is simple. Start with one big square covering everything. Drop points into it. The moment a square holds more than some capacity N (say 100), split it into four equal quadrants — northwest, northeast, southwest, southeast — and hand each point down to the quadrant it falls in. Any quadrant that overflows splits again, recursively. Sparse areas stay as one big square; busy areas grow a deep little tree of tiny squares. The leaves end up holding roughly equal numbers of points regardless of how lumpy the map is.

To answer "what's near me," you walk the tree from the root, descending only into squares that overlap your search circle and skipping every branch that can't possibly intersect it. In a city you visit a handful of small leaves; over the ocean you skip whole continents in one comparison. Drag a query box below and watch which nodes light up.

The tradeoffs versus geohash: a quadtree adapts to density automatically and keeps leaves balanced, but it lives in memory as a pointer structure, so it's harder to shard across machines and harder to update — a flurry of inserts in one spot can force repeated splits, and big rebalances mean rebuilding subtrees. Geohash strings, by contrast, drop straight into any ordinary database index and update trivially. Many real systems use geohash for the durable, shardable store and a quadtree (or an in-memory grid) for a hot region.

Geohash and quadtrees are the two you'll reach for most, but they're not the only answers — and knowing the alternatives shows you the tradeoffs sharply.

• Google S2 (Hilbert curve). Geohash flattens 2D to 1D with a grid, but its zig-zag ordering has ugly jumps — adjacent cells can be far apart in the string. S2 instead threads a single continuous space-filling curve (the Hilbert curve) through every cell. The magic of that curve is that it almost never jumps: points close on the line are close on the map, and vice versa. S2 also wraps the curve around a sphere, so it doesn't distort near the poles or the date line the way a flat grid does. The price is more complexity.
• R-tree. Instead of cutting space into a fixed grid, an R-tree groups nearby objects into bounding rectangles, then groups those rectangles into bigger rectangles, and so on up. It's the workhorse inside PostGIS and many spatial databases, and it shines when objects have extent (roads, regions, polygons), not just points. The catch: rectangles can overlap, so a query may have to descend several branches, and heavy updates can degrade the structure.
• Even grid / uniform hash. The simplest option — fixed-size square cells, like geohash without the clever codes. Trivial to build and update, but it shares geohash's blind spot: a uniform grid can't adapt to density, so dense cells stay overloaded while empty ones waste space.

The three axes you're trading along are always the same: update cost (how cheap is it to move a point?), accuracy / distortion (does the index respect true distance, including the curve of the Earth?), and even distribution (do cells hold roughly equal load, or do hotspots form?). No index wins on all three; you pick by which one your workload punishes most.

Now flip everything. In Nearby Friends the data isn't a static map of businesses — it's millions of people moving, each phone reporting its position every few seconds. A precomputed disk index is the wrong tool: by the time you've written a location to disk and rebuilt an index, the person has already moved. This is a streaming problem, not a storage problem.

The dataflow looks like this. Each phone keeps a long-lived connection open to the backend — a WebSocket, the persistent two-way channel from Chapter 10's callback discussion — and pushes its location up the moment it changes. A location-update service receives that stream. For every update, it figures out which of your friends are within your radius and pushes the change down to whoever needs it.

Two pieces make this scale. First, pub/sub channels, one per user. When you open the app, you subscribe to a channel for each friend you care about. When a friend's location service receives a new position, it publishes to that friend's channel; everyone subscribed gets the update pushed instantly, and the publisher doesn't need to know or care who's listening. Second, the locations themselves live in an in-memory store with a TTL — Redis is the canonical choice. A location is written with a short expiry (say 30 seconds); if the phone stops reporting, the entry simply evaporates, which is exactly the "went offline" behavior you want, for free. You never run a delete.

Distance is computed on each update, not on a query, because there are far more readers (friends watching) than there are updates from any one person — so doing the work once at write time and fanning the result out is cheaper than recomputing on every read. Below, dots wander, a radius follows "you," and friends slide in and out of your subscription set as they cross the line.

The read-heavy and write-heavy halves want different homes. For the proximity service, you store places in a geo-indexed database — Postgres with PostGIS, or any store that indexes geohash strings — replicated and cached hard, since the data is mostly static and read constantly. For Nearby Friends, locations live in Redis, which has built-in geo commands (GEOADD / GEOSEARCH) layered on the same sorted-set primitive, plus the TTL and pub/sub you need.

Either way, one machine can't hold the planet, so you shard by region — and the natural shard key is the geohash prefix itself, because it already groups nearby points together. Cells starting dr* go to one node, 9q* to another. The headache, exactly as in Chapter 8's sharding, is that the world is wildly uneven:

• Dense cities vs empty oceans. A shard covering Manhattan might hold a thousand times the data of one covering the Pacific. Splitting purely by a fixed grid creates brutal hotspots. The fix is to shard by load, not by area — give a busy city several shards and let a sparse region share one.
• Cache the popular queries. "Restaurants near Times Square" is asked constantly; the answer barely changes. Cache results keyed by cell so the millionth person asking gets a memory hit, never touching the index.
• Cross-cell queries at the seams. A query near a shard boundary must hit two nodes and merge — the same neighbor-cell logic from the boundary problem, now at the infrastructure level.

The shape is familiar: shard to spread load, replicate for read capacity and failover, cache the hot answers, and pick a shard key (geohash prefix) that keeps neighbors together while balancing by real traffic rather than raw geography.

Every grid-based index shares one truth: the cell is a coarse filter, never the final answer. A cell tells you "these points are roughly in the neighborhood," and that's all. Three loose ends always need tidying.

• Cell borders. As we saw, two points either side of a line can be meters apart with different codes. Always query the eight neighbor cells too, so nothing close gets dropped just for sitting over a seam.
• Variable radius. A user might want results within 500 m or within 20 km. You can't bake one cell size in. Pick the geohash precision (or quadtree depth) whose cell is at least as big as the requested radius, search that level plus neighbors, and you're guaranteed to cover the circle. If a search returns too few results — say, out in the countryside — widen the radius and retry at a coarser precision.
• Rank by actual distance. The cells give you a candidate set that's a bit too generous (a square-ish region, not a true circle). The final step is to compute the real great-circle distance from the user to each candidate, throw out anything beyond r, and sort by closeness. The index does the cheap, coarse cut over millions of rows; the exact math runs only on the handful that survived.

That two-stage shape — coarse filter on the index, exact distance on the survivors — is the heartbeat of every proximity system. The index's job is to make the candidate set small; precise geometry's job is to make the answer correct. Here's the whole chapter as the order in which you'd actually build it:

1. 1Frame read vs write. Proximity search is read-heavy (precompute + cache); Nearby Friends is write-heavy (stream + expire).
2. 2Reject the naive bounding box. A 1D index can use only one of lat/lng; 2D "near" needs a spatial index.
3. 3Geohash the points. Interleave lat/lng bits into a base32 string; nearby = shared prefix; store it in a normal index.
4. 4Quadtree where it's dense. Subdivide adaptively so leaves hold ≤ N points; keep it in memory for hot regions.
5. 5Know the alternatives. S2/Hilbert for distance fidelity on a sphere; R-trees for shapes with extent.
6. 6Stream live locations. WebSocket up, per-user pub/sub channels, Redis with TTL, distance on update.
7. 7Shard by region, balance by load. Geohash prefix as shard key; give cities more shards; cache hot cells.
8. 8Coarse-filter, then rank. Query cell + neighbors, then compute real distance and sort the survivors.

Here's the fold at the heart of Section 3. We bisect the longitude range and the latitude range alternately: each step asks "is the point in the upper half of this dimension?", emits a 1 if so (and keeps that half) or a 0 if not, then moves to the other dimension. Pack the bits five at a time and look each group up in a 32-symbol alphabet. The whole point: this turns a 2D proximity question into 1D string-prefix matching. Flip between the languages — the shape is identical.