How to design a proximity service

In this lesson, we’ll build the service behind one question: “what is near me?” Every maps app, ride-hailing app, and food-delivery app runs it millions of times a second. It looks like a one-line database query, and yet an ordinary index answers it only by scanning a band that wraps the whole planet. We’ll see why that happens, then work through the four standard fixes, which all attack the same problem the same way. By the end you’ll be able to size the corpus, price each indexing scheme by how many candidates it touches, choose between geohash, quadtree, S2, and H3 on their real trade-offs, and defend that choice in an interview.

Start with the contract. The service is one function. It takes a point, a radius, and optional filters, and returns the businesses inside that circle, ranked, each with its exact distance:

input     lat = 40.7580, lng = -73.9855, radius = 2000 m, category = restaurant
output    [{id, name, distance_m: 143}, {id, name, distance_m: 617}, ...]

The core problem: two dimensions, one sorted key

Three terms carry the topic:

• A disc is the region the user asked about: every point within r metres of the query point. The request is a circle, not a rectangle and not a list of rows.
• An index is a data structure kept beside a table so the database can find matching rows without reading them all.
• A B-tree is the classic index: a sorted tree that stores keys in one order and jumps straight to a range of that order. It is one-dimensional: it sorts by one value at a time.

Here is the whole difficulty in one sentence: a location is two numbers, and a B-tree sorts along one line. So every geospatial index is a scheme for flattening two dimensions into one while preserving locality, the property that points close on the map get keys close in the sorted order. Locality is what makes a range scan return your neighbours instead of strangers, and it is exactly what a naive flattening throws away. Hold onto that word; every scheme below lives or dies by how well it keeps it.

There are four standard flattenings. Know what each one is before we price them, because the rest of the lesson is a comparison:

flowchart TD
    P["2-D point (lat, lng)"] --> F["Flatten to one sortable key,<br/>keeping neighbours close"]
    F --> G["Geohash<br/>interleave lat/lng bits into a base32 string"]
    F --> Q["Quadtree<br/>recursive quadrants, splits where data is dense"]
    F --> S["S2<br/>cube projection + Hilbert curve, near-equal area cells"]
    F --> H["H3<br/>hexagons, all six neighbours equidistant"]

One split runs through all four. Geohash and S2 and H3 are fixed cell schemes that can be sharded and stored in any sorted structure. A quadtree adapts to density but is a bespoke in-memory tree. That single difference decides most of what comes later.

A few constants about the planet, used throughout: the equator is 40,000,000 m around, Earth’s surface is 510,000,000 km², and roughly 15,000,000 km² of it is settled land with mapped detail. Latitude runs pole to pole, half a lap, over 180 degrees, so one degree of latitude is 20,000,000 / 180 = 111,111 m everywhere. A degree of longitude is not constant: the meridians converge toward the poles, so a degree of longitude shrinks by cos(latitude). Keep that asymmetry in mind, because it causes one of geohash’s defects and a correction factor in the distance calculation.

Requirements

The functional side is ordinary. The non-functional constraints do the work, because each one eliminates a family of designs before we draw it.

Functional:

• search(lat, lng, radius, filters) returns businesses inside the disc, ranked.
• Radius is one of a small menu: 500 m, 2 km, 5 km, 20 km.
• Create, read, update, delete a business by its owner or an internal pipeline; read a single business by id.

Non-functional: these decide the design. Two terms first: p99 is the latency 99 of every 100 requests beat (the slow tail, not the average), and eventual consistency means a write becomes visible everywhere only after a bounded delay.

The last row governs everything, so read it twice. Every scheme below is a candidate generator: it narrows two hundred million points to a few hundred, and only then does an exact distance test narrow those to the answer. None of them is correct on its own, which is why “how many candidates” is the number we keep pricing.

One more property shapes the design and is not in the table: a business changes address maybe once a decade. The location index is derived, nearly immutable, and rebuildable from the source of truth. That removes concurrent writers, consistency protocols, and conflict resolution before they can start. Two facts now drive the sizing: how big the corpus is, and how dense it is where people actually search.

Back of the envelope

Two numbers drive the rest: the total corpus size (does sharding even come up?) and the density at a typical query point (how many candidate rows does each scheme touch?).

Corpus. One business row is about 300 bytes (id, name, address, two float64 coordinates, category, a 64-bit cell id, and metadata). Order of magnitude:

200,000,000 rows × 300 B  ≈  60 GB   (180 GB across 3 replicas)

Sixty gigabytes is the entire commercial geography of Earth, and it fits in RAM on one commodity box. Why that matters: it removes the sharding conversation entirely and leaves room for the real question, the index.

Traffic. 100 M daily active users at 5 searches each is 500 M searches/day, about 5,800/second, and roughly 14,468/second at a 2.5× daily peak. Nothing in the design is shaped by this number; we size a read fleet on it and move on.

Density. Candidates = area × density, so every later estimate needs a businesses-per-km² figure:

global mean   200,000,000 / 15,000,000 km²   =  13.3   per km²
Manhattan     60,000 / 59.1 km²              =  1,015  per km²
Wyoming       65,000 / 253,600 km²           =  0.26   per km²
skew          1,015 / 0.26                   ≈  3,904

Read that skew as the design constraint it is: the densest place has roughly 4,000× the density of the sparsest, so no single fixed grid is the right size for both. Queries do not happen at the global mean, which averages in farmland nobody searches from; they happen in towns. So we use 50 businesses/km² as the density at a typical query point for every candidate count below. It is an estimate, and moving it 10× in either direction changes no box in the design (shown at the end). With the corpus and the density fixed, we can lay out where the data lives.

Data model and architecture

The data splits into two stores, and that split is the design:

businesses   source of truth, relational, sharded by business_id
             business_id PK, name, address, lat, lng, category, attrs, updated_at

geo_index    derived, in memory, rebuildable, sharded by cell
             cell_id  ->  [business_id, ...]

The geo index holds no truth. It is an inverted index (the same structure a search engine uses to map a word to the documents containing it) where the key is a cell id and the value is a list of business ids. Because it holds no truth, we can drop it and rebuild it from businesses in minutes. That deletes three things you would otherwise have to design: a durable write path (losing the index loses nothing), a replica-agreement protocol (nothing to agree on), and a conflict story (nobody writes to it).

The update path is one-way. A business edit writes the relational row; a change-data-capture stream (a feed of committed row changes read off the database’s transaction log) picks it up and recomputes that business’s cell. Membership changes only when lat/lng changes, a few thousand times a day out of 200 M businesses. So the index is 99.99% static, a build artifact and not a database.

Put the two stores behind a request path and a shape emerges that never fans out across machines. The top row is a live search (left to right); the bottom loop keeps the index fresh offline. Notice that nothing on the read path writes anything.

flowchart LR
    C["Client"] --> LB["Load balancer"]
    LB --> S["Search service<br/>cell lookup + exact filter + rank"]
    S --> GI["Geo index replicas<br/>cell_id -> id list, in RAM"]
    S --> BC["Business cache<br/>id -> attributes"]
    BC --> DB[("Business DB<br/>source of truth, only writer")]
    DB --> CDC["CDC stream"]
    CDC --> B["Index builder<br/>offline"]
    B --> GI

The only store anyone writes to is the business DB. The geo index replicas and the business cache serve reads without touching it; the index builder does its work off the request path. The search service and load balancer are stateless and own nothing, so scaling them is just adding replicas.

Here is the one deliberate extravagance: every geo index replica holds the whole 60 GB index. That costs some memory and buys one thing worth the price: a search never crosses a network boundary to a second shard. That removes the fan-in tail that dominates most read paths in this book. When a request waits on ten machines, its latency is the slowest of the ten, so a rare slow response anywhere shows up in every request’s p99. With one full copy per replica there is no fan-in. Scale reads by adding identical replicas, and that is the entire scaling story. Now that the frame is set, let’s price the index people reach for first and see exactly where it fails.

Why a B-tree on (lat, lng) cannot do this

Every later scheme needs a number to beat, so we price the design people reach for first: a bounding box backed by a composite index.

SELECT * FROM businesses
WHERE lat BETWEEN 40.7452 AND 40.7632
  AND lng BETWEEN -74.0056 AND -73.9819;
-- CREATE INDEX ON businesses (lat, lng)

A composite index is one B-tree sorted by lat first, and by lng only within a single lat value. Picture what happens the moment your predicate accepts many latitudes: the longitudes are no longer one sorted run, they are thousands of independently sorted runs stacked end to end, with no contiguous stretch holding all the longitudes you want. This is the leftmost-prefix rule: a range predicate on the leading column destroys the ordering of everything after it. So the index prunes on latitude only, and longitude degrades into a filter applied to every row the latitude scan produced.

Price a 1 km search at 40.76° N. The latitude band is 2 × 1,000 / 111,111 ≈ 0.018 degrees tall (north and south of the point). Rows exist only where people live, roughly a 130-degree inhabited band:

fraction of rows in band   0.018 / 130          ≈  0.0001385
rows scanned               200,000,000 × that   ≈  27,700
businesses actually wanted  π × 1² × 50          ≈  157
amplification              27,700 / 157          ≈  176×

Picture where those 27,700 rows physically are: the scan circles the globe, so they include every business in Madrid, Ankara, and Beijing sitting on the 40.76 parallel. Whether that is merely bad or outright fatal depends on the index:

A covering index contains every column the query needs, so no second lookup into the table is required; it turns 27,700 random reads into one 665 kB sequential read. Fast, but here is the catch: every filter you add (category, open_now) multiplies the 176× instead of reducing it, because those columns cannot join the index prefix either. The leading column is already a range, and everything after a range is unsorted.

The standard rescue is two single-column indexes combined with a bitmap AND (collect matching row ids from each index, intersect, fetch only the rows in both). Pricing the longitude side (a degree of longitude at 40.76° is 111,111 × cos(40.76°) ≈ 84,161 m, so its band spans ~13,200 rows of the full 360 degrees) gives ~40,900 index entries touched, read sequentially, then only 157 random heap fetches: about 16.7 ms total, 166× faster on the clock than the composite index. But look at the work per answer: it touches 260 entries against the composite’s 176, so it is more wasteful, and work-per-answer is the quantity every added filter multiplies. Both plans are one-dimensional; neither is a candidate against the low single digits a two-dimensional scheme buys.

That failure is exactly why two families of two-dimensional structures exist:

• An R-tree is a tree of nested bounding boxes; each node stores the smallest rectangle enclosing its children, and a search descends only into boxes overlapping the query, pruning in both dimensions at once. PostGIS runs the production one.
• A space-filling curve threads one continuous line through every cell of a grid so cells near each other on the map are usually near each other along the line. Numbering the cells along that line is the flattening into a single sortable scalar. Geohash, S2, and H3 all build one.

We’ll spend the rest of the lesson on the space-filling-curve family, starting with the one you can encode by hand.

Geohash

Start with the intuition, because geohash is just twenty questions played against the map. A geohash names a rectangle by repeatedly halving the world: is the point east or west, north or south, and so on. Each answer is one bit; a longer string means a smaller rectangle, and points sharing a prefix are usually near each other.

flowchart TD
    W["Whole world"] --> A["Split longitude: E / W  (1 bit)"]
    A --> B["Split latitude: N / S  (1 bit)"]
    B --> C["Split longitude again ..."]
    C --> D["Longer string = smaller cell<br/>shared prefix = nearby on the map"]

Do one by hand to make it concrete. Encoding lat = 40.7580, lng = -73.9855: longitude first, then alternate. West→0, north→1, east→1, south→0, west→0 gives 01100 = 12, which maps to d in geohash’s 32-character alphabet. The point continues to dr5ru7. Geohash uses base32, so 5 bits per character, not 4 and not 6. This is the single most common geohash mistake, so bank it now.

Now the general math. Because the bits alternate starting with longitude, after n = 5 × precision bits longitude has been halved ceil(n/2) times and latitude floor(n/2) times. Width divides the full 40,000,000 m circumference once per longitude halving; height divides only 20,000,000 m (latitude’s range is half a lap):

Watch the aspect ratio alternate: give both axes equal bits and you get a 2:1 cell (longitude started with twice the range), and the extra longitude bit at odd precision squares it back up. So precisions 5 and 7 are square; 4, 6, and 8 are twice as wide as tall. A 12-character geohash is ~3.7 cm wide, far past the coordinate’s own precision, so extra characters are noise. Two defects fall straight out of this construction, and neither can be tuned away.

Two structural defects

1. Cells are not equal area. Height is constant everywhere, but width scales with cos(latitude). Work one case: at 60° N, cos(60°) = 0.5, so a precision-6 cell there holds half the ground area (and, at fixed density, half the businesses) of its equatorial twin. That means cell occupancy, cache sizing, and shard balance all become functions of latitude, and near the poles the cell degenerates entirely.

2. Adjacency breaks at cell boundaries, so always query nine cells, not one. Take two points one metre apart on opposite sides of the prime meridian: they have opposite-sign longitudes, so they differ on the very first bit and share zero characters. This happens at every boundary at every level. We can quantify how often a single-cell lookup is wrong: a disc of radius r fits inside a w × h cell only if the query point is at least r from all four edges, with probability max(0, (w−2r)/w) × max(0, (h−2r)/h).

precision 5, r = 500 m   (3,883/4,883)² = 0.633   ->  37% of queries wrong
precision 6, r = 500 m   height 610 < 2r = 1,000  ->  disc never fits, 100% wrong

Read the second line carefully: at precision 6 a 500 m disc cannot fit in one cell at any position. That is why the query is always the centre cell plus its 8 neighbours, and why geohash libraries ship a neighbours() function. The nine-cell rule fixes correctness; now we have to pick precision without paying too much for it.

Picking precision, and the 32× cliff

With the nine-cell rule, a 3×3 block guarantees coverage out to min(cell width, cell height) from the query point, even from the worst corner. So the rule is to choose the finest precision whose min(w, h) is at least r (finest, because smaller cells waste fewer candidates). To measure the waste, define overfetch as map area scanned over map area asked about:

Look at the jump from 2 km to 5 km, because it exposes the real defect. A 2 km radius fits precision 5 (4,883 ≥ 2,000). A 5 km radius misses by 117 m (4,883 < 5,000), so it drops to precision 4, and one character is 5 bits, five halvings, so the cell area jumps 2⁵ = 32×. A 2% increase in requested radius costs 32× the scan. That quantization is geohash’s real defect, worse in practice than the equal-area complaint.

The fix is to stop letting character boundaries set the block size. Stay at the finer precision and query a (2k+1) × (2k+1) block with k = ceil(r / min(w, h)) rings; 3×3 is just k = 1. At 5 km, precision 5 needs k = 2, a 5×5 block of 25 small cells (596 km²) instead of 9 cells that are 32× bigger, about 11.5× fewer candidates for one line of code. Working in bits instead of characters, the resolution ladder steps by 2 instead of 32. Geohash’s grid is fixed at every level, though, and the next scheme asks what happens if the grid can follow the data.

Quadtree: adaptivity, and what it costs

Geohash’s fixed grid cannot follow density; a quadtree can. The idea: every node covers a square, and when a node holds more than a fixed bucket of points it splits into four quadrants. A node that has not split is a leaf holding points; a split node is internal and holds only pointers to its four children.

flowchart TD
    R["Root: whole map"] --> N1["NW"]
    R --> N2["NE  (>100 points -> split)"]
    R --> N3["SW"]
    R --> N4["SE"]
    N2 --> M1["NW"]
    N2 --> M2["NE"]
    N2 --> M3["SW"]
    N2 --> M4["SE"]

The appeal is that it puts resolution where the data is. With a bucket of 100 and mean leaf occupancy of 70, the tree is about 2.86 M leaves, ~0.95 M internal nodes, and ~11 levels deep if points were uniform. Memory is ~4.95 GB, but the 200 M point entries are 97% of that, so the tree structure itself is almost free.

Its adaptivity is real and measurable. Each level quarters the area, so Manhattan versus Wyoming (a 3,904× density ratio) is log(3,904) / log(4) ≈ 6 extra levels, automatically, which no single geohash precision can express. And yet you still would not run it online, for three reasons:

• It is a bespoke in-memory server, not a database, not a Redis type. Snapshotting, warm restart, and replica catch-up are all yours to build.
• A leaf split is a structural change. Concurrent readers need a lock or a copy-on-write path down the spine.
• A cell id is not a shard key. Sibling leaves must stay reachable from a common parent, so the tree cannot be cut into independent pieces.

So a quadtree is right when the point set is static and lives in one process (this workload) and wrong the moment the points move (the Nearby Friends service). We want its adaptivity without giving up a shardable, sortable cell id, and that is exactly what the modern schemes deliver.

S2 and H3: repairing geohash’s geometry

The modern answer keeps a flat, shardable cell scheme and fixes geohash’s geometry. S2 and H3 each repair one of geohash’s two defects, and the repairs turn out to be mutually exclusive.

S2 fixes the equal-area defect. It projects the sphere onto a cube (every surface point pushed out to the nearest of six faces) then grids each flat face, so cells no longer stretch with latitude. Over each face it runs a Hilbert curve, a continuous path that visits every square while keeping nearby squares nearby, and numbers cells in visit order. There are 6 × 4^L cells at level L; level 13 gives ~402 M cells of ~1.27 km² each. Two properties matter:

• Bounded distortion. The largest-to-smallest cell area ratio is about 2.08 at a given level, bounded, unlike geohash’s 1/cos(latitude), which diverges toward the poles.
• The id is an integer. A 64-bit S2 cell id’s numeric order is the Hilbert order, so containment is a prefix test and proximity is usually an integer range. It drops into any B-tree or sorted set with no special support.

What S2 keeps is the square’s awkward neighbour geometry: a square’s four edge neighbours sit at distance s but its four corner neighbours at √2·s ≈ 1.41s, 41% further. A k-ring (cells within k steps) is therefore a square, and a square approximates a disc poorly.

H3 fixes that with hexagons, where all six neighbours share an edge and sit at exactly the same distance, so there is no diagonal case. For a hexagon of edge length a: area 2.598 a², inradius (centre to edge midpoint, the largest disc that fits inside) 0.866 a, and neighbour spacing 1.732 a. H3 resolutions divide by 7 per level (seven hexagons roughly tile into one), from a base of 122 cells. Resolution 9, used in every example below, is 0.1036 km² with a ≈ 199.7 m.

Hexagons cost you one thing: they do not nest. Seven only approximately tile into one, so a resolution-9 cell is not exactly contained in a resolution-8 cell, and roll-up aggregations leak at the edges. That makes the trade a single line: S2 keeps exact containment and gives up uniform adjacency; H3 does the reverse. Both still exist because neither buys both. To turn “k steps” into “metres covered,” we need one more piece of geometry.

The k-ring and the radius it covers

A filled k-ring holds 1 + 3k(k+1) cells: 7, 19, 37, 61 for k = 1..4. But a k-ring is a hexagon and the request is a disc, so “k steps” is not yet a distance. The conversion is the inscribed radius: the largest disc, centred on the origin cell, the k-ring is guaranteed to contain. The nearest uncovered point is a vertex tucked into a notch in the jagged boundary, and on the triangular lattice hexagon centres sit on, its exact value is:

The exact value is never below 1.5·k·a, so that expression is a safe lower bound, and inverting it gives the formula you ship:

k = ceil(r / (1.5 a))

Here is why you cannot eyeball k. For a 1 km search at resolution 9, 1.5a ≈ 299.6 m, so k = ceil(1000 / 299.6) = 4. It is tempting to pick k = 3: three rings of cells spaced 346 m apart is well over a kilometre. But the exact inscribed radius at k = 3 is 5.000 × 199.7 = 998.5 m, 1.5 metres short of the requested kilometre. A k = 3 query silently drops businesses in a thin crescent on every request; nothing errors, and no test written against a city centre catches it. The safe bound picks k = 4 and is correct by construction.

Being right costs 61 cells against 37. At resolution 9 that is 6.32 km² scanned for a 3.1416 km² disc, an overfetch of 2.01×. Line up all three schemes at the same 1 km radius to see how far we have come:

geohash on character boundaries   9 cells, precision 5     ->  68.3×
geohash with the (2k+1) fix       25 cells, precision 6    ->   5.9×
H3 resolution 9, k = 4            61 cells                 ->   2.0×

Two reasons H3 wins, both geometry and not engineering: a hexagon is closer to a disc than a rectangle, and the ladder steps by 7 instead of 32, so a radius is never forced onto a cell several times too big. Remember, though, that none of this returns an answer alone: cells narrow 200 M points to 61 cells, and an exact distance test narrows 61 cells to the answer. Which raises the question the whole lesson has deferred: where does the time actually go?

The search itself

Walking one request end to end shows something surprising: the spatial work, the part every section above obsessed over, is not where the latency goes.

flowchart TD
    Q["lat, lng, r, filters"] --> K["Pick k or precision<br/>from r and cell size"]
    K --> C["Fetch cell id lists<br/>9 geohash cells, or 61 H3 cells"]
    C --> H["Hydrate candidates<br/>id -> full row, from business cache"]
    H --> F["Exact distance filter<br/>+ category, open_now"]
    F --> R["Rank and truncate to limit"]
    R --> O["Response with distance_m"]

Only the first two steps touch the grid, and they are nearly free. Nine cell lookups plus 335 distance tests, each a single ~100 ns memory reference, is about 34 µs against a 100 ms budget.

The cost is hydration, turning each bare id into a full row. That is a network call to a cache (~0.5 ms each), not a memory reference. Do it serially and 335 candidates cost 335 × 0.5 ms ≈ 167 ms, blowing the budget by 1.7× on their own. Do it as one batched multi-get (MGET or equivalent) and all 335 cost 0.5 ms. So the entire latency story is whether the candidate list leaves the process as one request or 335. The hot path is a business_id -> attributes cache, an ordinary key-value problem and not a geospatial one.

Four details that are easy to get wrong:

1. Use the equirectangular approximation, not haversine, for the exact filter. Treat a small patch as flat and correct longitude for latitude: dx = dlng × 111,111 × cos(lat), dy = dlat × 111,111, d = sqrt(dx² + dy²). Over a few kilometres it is accurate to well under a metre and skips four trig calls per candidate. Compute cos(lat) once for the query point, not once per candidate.
2. Filter before you rank, and rank on the hydrated row. Ranking (distance, rating, sponsorship) is a business decision that does not belong in the index.
3. Cache the cell lists, not the query results. A result keyed by (lat, lng, r, filters) is effectively unique per user and dead on arrival; a cell list keyed by cell_id is shared by everyone in that cell. Cache what is shared.
4. Size that cache with the right density. The 50/km² is the density at a query point, not the mean over settled land. Using it here is a trap: pricing 20 M cells at 37 ids each implies 750 M businesses against a corpus of 200 M, so the number refutes itself. The mean list length is not an assumption; it is forced by the corpus. Settled land over a precision-6 cell is ~20.1 M populated cells, so 200 M / 20.1 M ≈ 9.93 ids per cell, and at ~112 bytes per entry the cache is about 2.25 GB, not the 6 GB you get from the query-point density.

Once you know hydration is the cost, the honest move is to admit you do not have to write any of this yourself.

The pragmatic answer: Redis GEO or PostGIS

You do not write any of the above. Two products already implement it, and the real task is knowing which to pick and where each one stops.

• Redis GEO stores a 52-bit geohash as the score in a sorted set and implements GEOSEARCH ... BYRADIUS as exactly the neighbour scan plus an exact filter. At ~150 bytes per member it is about 30 GB. Its ceiling: the geo commands are single-key, so the whole set lives on one node and one core services each search. Replicas scale reads and nothing scales the key.
• PostGIS is PostgreSQL’s geospatial extension. It puts a GiST index (acting as the R-tree) on a geography column and answers ST_DWithin: nested bounding boxes that split where data is dense, no fixed grid. At ~40 bytes per entry the whole index is ~8 GB and stays in page cache.

For 200 M static points at 14,468 peak QPS, PostGIS is the right default: the 8 GB index caches entirely, and its query planner beats anything you would hand-write. When you outgrow Redis GEO, the escape hatch is that a search carries its own location, so region is a natural shard key (one instance per continent, routed by coordinate, scattering to two only near a boundary). Build an S2 or H3 index only when you need cells as a join key: when traffic, demand forecasts, delivery zones, and surge pricing must all aggregate on the same grid. That is a data-platform reason, not a latency reason. With the design chosen, look at what can still break it in production.

Bottlenecks and failure modes

Storage, write throughput, and consistency are all absent here, each one removed by an earlier decision. What remains:

A proximity service fails mostly by returning quietly wrong answers, none of which raise an error rate. Those are the ones an interviewer wants to hear you name:

Which assumptions are load-bearing

An assumption is load-bearing if getting it wrong changes the set of boxes in the design, not just the number of machines inside them. Five here are load-bearing, and each one, if false, points to a different design:

• Points are static. This removes the entire write path. If points moved continuously you get Nearby Friends: an in-memory store with a time-to-live, sharded by owner id, and no offline builder.
• The corpus is 60 GB and fits in RAM. This gives full replicas instead of shards, and so no partitioner, no scatter-gather, no fan-in tail. At 6 TB you must partition by cell, every search fans out, and the p99 becomes the slowest of n responses.
• The answer must be exact. This makes cells a filter, forcing the nine-cell query and the k formula. If approximate answers were fine, you return a cell’s contents unfiltered and the whole geometry vanishes.
• Radius varies. This makes precision selection a derivation. With one fixed radius you precompute a neighbour list per cell and the query is a single lookup.
• A day of staleness is acceptable. This keeps the builder offline. A one-second requirement turns it into an online mutation path with locking and replica divergence.

Everything else is tunable (density skew, edit rate, cache hit rate, cell resolution) and moving it changes machine counts, not architecture. The most-used and most-suspicious number, 50 businesses/km², is explicitly not load-bearing. Move it 10× either way: at one tenth the density the candidate list shrinks and search speeds up; at ten times it you cap the per-cell list, a tuning constant already in the design. Density cannot change the ratio of scanned to returned rows, because it multiplies both sides, so the 176× B-tree amplification, the 32× cliff, and the 2.01× overfetch are all density-independent. The one place density is not free is cache sizing, which is exactly why the mean list length there is taken from the corpus and not this figure.

Conclusion

• A B-tree is one-dimensional and a location is two-dimensional. Every geospatial scheme flattens two dimensions into one sortable key while preserving locality; a (lat, lng) composite index does not, and pays 176× amplification.
• Geohash interleaves lat/lng bits into a base32 string, 5 bits per character. Its cells scale with cos(latitude) and break adjacency at boundaries, so a search is always the centre cell plus its 8 neighbours, and precision quantized in 32× steps forces a (2k+1) block.
• Quadtrees adapt to density (six levels deeper over Manhattan) but have no shard key and split under contention, right only for static, single-process data.
• S2 keeps exact containment (integer ids, bounded 2.08× distortion) but square neighbours; H3 uses hexagons with equidistant neighbours and a gentler ladder of 7, cutting overfetch to ~2× at 1 km, but its cells do not nest exactly.
• Cells are only a candidate generator; an exact distance test is always the last gate. The spatial work is microseconds, so the latency lives in hydration: batch it.
• Start with PostGIS or Redis GEO. Build S2/H3 only when the cell id becomes a join key across systems.

One line to remember: a cell is only ever a candidate generator, so pick the scheme that touches the fewest candidates and let an exact distance test have the final word.

Further reading

• Redis GEO commands: the sorted-set geohash implementation described above.
• PostGIS spatial indexing: GiST R-tree indexes and ST_DWithin.
• S2 Geometry: the cube projection and Hilbert-curve cell ids.
• Uber H3: the hexagonal grid, k-rings, and resolution ladder.
• Related: Nearby Friends takes this index and makes the points move; Google Maps lays a road graph over the same cells.