Geospatial indexes and quadtrees
A B-tree indexes one ordered axis. The Earth has two — and they interact. The entire craft of geo-indexing is collapsing a 2-D continuous surface into 1-D discrete keys without losing the property that "nearby in space" stays "nearby in the index."
1. Clarify the contract
Treat the prompt as a product contract before a box diagram. The index must:
- Insert / remove a point (lat, lng, id) — and update it when an object moves.
- Answer radius queries ("everything within R of (lat,lng)") and bounding-box queries.
- Stay efficient under skewed density — Manhattan and the Pacific Ocean share one index.
- Never miss an object that is genuinely within R, including one sitting just across a cell boundary.
- Keep both query and update cost bounded and predictable.
What it need not do: return results in distance-sorted order (that's a cheap post-sort on the small candidate set), compute road-network or travel-time distance (that's a routing engine, C19's job), or be a general GIS engine handling arbitrary polygons. We index points and answer proximity; everything else is downstream.
2. Put numbers on it — the precision/fanout U-curve
This is the load-bearing calculation of the whole case, so derive it explicitly. A radius query has exactly two costs, and they pull in opposite directions as cell size changes:
cost(cellsize) = cells_read + candidates_filtered
- cells_read grows as cells shrink: covering a fixed query area A with cells of area c needs roughly A / c cells (plus a neighbour ring — see §6). Smaller c → more cells.
- candidates_filtered grows as cells grow: each cell you touch drags in ρ · c points (density ρ per m²), and you must compute exact distance for every one to discard those outside R. Bigger c → more dead candidates.
So total work is A/c + ρ·c·(A/c) ≈ A/c + ρ·A in the naive read — but the real lever is that you don't read exactly A; you read a grid of whole cells that covers A, and that over-read is what the candidate term punishes. Make it concrete. Query radius R = 500 m → query area A = πR² ≈ 0.785 km². Urban density ρ = 5000 indexable points per km² (a dense ride-hail city). Walk the cell size down and tabulate the two terms plus a unit-cost blend (assume reading a cell costs ~10× exact-distance-filtering one point, since a cell read is a key lookup + network round trip):
| Cell edge | Cell area | Cells to cover A (+ring) | Candidates pulled (ρ·area read) | Blend: 10·cells + candidates |
|---|---|---|---|---|
| 5 km | 25 km² | ~4 | ~125,000 | 125,040 |
| 1 km | 1 km² | ~9 | ~22,000 | 22,090 |
| 500 m | 0.25 km² | ~16 | ~7,000 | 7,160 |
| 150 m | 0.0225 km² | ~64 | ~1,400 | 2,040 ← min |
| 40 m | 0.0016 km² | ~640 | ~700 | 7,100 |
| 10 m | 0.0001 km² | ~10,000 | ~600 | ~100,600 |
The blended cost is U-shaped: at 5 km cells you drown in candidates, at 10 m cells you drown in cell reads, and the minimum sits near a cell edge ≈ the query radius (here ~150 m for a 500 m query). That is the rule of thumb to state in the interview: pick a cell size on the order of your typical query radius, then verify against measured density. There is no globally correct precision — only one that minimises this sum for your ρ and R. And because ρ varies wildly across the map, a single fixed precision is necessarily wrong somewhere, which is the entire argument for adaptive trees (§6).
Geohash length → cell size
A geohash encodes lat/lng by bit-interleaving into a base-32 string; each extra character adds 5 bits and shrinks the cell ~32× in area (alternating ~8× / ~4× per char between the two axes). The prefix length is the precision knob, which is why the table below is worth memorising — it lets you pick a length directly from a target radius:
| Geohash length | Cell width × height (mid-latitudes) | Good for |
|---|---|---|
| 4 | ~39 km × 20 km | city / region buckets |
| 5 | ~5 km × 5 km | neighbourhood, coarse radius |
| 6 | ~1.2 km × 0.6 km | "nearby drivers" mid-radius |
| 7 | ~150 m × 150 m | tight urban proximity (our optimum above) |
| 8 | ~38 m × 19 m | building-level, dense venues |
So our 500 m-radius urban query lands at geohash length 7. The prefix structure also gives a free win: all points in a cell share a string prefix, so a cell read is a scan(prefix*) on any ordered KV store or B-tree — no special index type required.
3. Data model & API
Keep the surface small; it should express the operation, not the cell layout:
| API / operation | Why it exists |
|---|---|
insert(lat, lng, id) | Compute cell key(s) for the point; append id to those cells. |
query_radius(lat, lng, R) → [id] | Cover the disk with cells (+ neighbour ring), read, exact-filter. |
update(id, lat, lng) / remove(id) | Re-cell on meaningful movement; the write path for C20's moving objects. |
The on-disk model is deliberately just two relations: a forward map id → (lat, lng, cell) and an inverted index cell → set<id>. The cell key is the partition key — which is exactly how this index shards across machines (see lesson 07, and §6 on rebalancing).
4. Linearized design
Follow a radius query through the system; the bottleneck surfaces on its own:
- Choose the discretization at index-build time: fixed geohash grid (uniform density) or a quadtree / S2 cell hierarchy (skewed density). This is the one irreversible decision.
- On insert, encode the point to its cell key at the chosen precision and append the id to that cell's set in the inverted index.
- On query, compute the set of cells whose union covers the search disk — and crucially the neighbour ring around it (§6), because the query point may sit near a cell edge.
- Read those cells (each a prefix scan or a cell-ID point lookup), union their id sets — these are candidates, not answers.
- Exact-filter: compute true great-circle (haversine) distance for each candidate, keep those ≤ R. This is the candidates_filtered term from §2 — and the first place CPU is spent.
- Adapt: if any cell's candidate count blows the budget, split it (quadtree) or shard it; if cells are mostly empty, coarsen.
5. Deep dives
(1) Geohash (uniform grid) vs quadtree (density-adaptive)
Geohash lays a uniform grid: cell size depends only on prefix length, not on what's in the cell. Because bits are interleaved, walking the keys in sorted order traces a Z-order (Morton) space-filling curve — a 1-D ordering that keeps most spatial neighbours close in key space, which is what makes prefix scans return spatially-clustered points. Strengths: trivial encode/decode, prefix = precision, no tree to maintain, and the keys shard cleanly. Weakness: it ignores density. A length-7 grid over Manhattan has cells holding tens of thousands of points (read one and you over-fetch massively) while the same grid over Wyoming has near-empty cells (you read a wide ring of nothing). One global precision can't be right for both — exactly the §2 U-curve sitting at different minima in different places.
Quadtree makes precision local. Start with one cell covering the world; whenever a leaf exceeds a bucket cap (say 64 points), split it into four quadrants and push points down. Dense regions recurse deep; empty regions stay shallow (the ocean leaf in the diagram). Now every leaf holds a bounded candidate count by construction, so the §2 candidate term is capped everywhere. The cost: the tree is mutable state that must be maintained under inserts/deletes, splits/merges create write amplification, and the structure is harder to shard than flat string keys. This is the classic DDIA Ch. 3 R-tree family trade-off (R-trees do the same density-adaptive bounding-box nesting for arbitrary rectangles).
| Workload | Pick | Why |
|---|---|---|
| Roughly uniform density, read-heavy, want simple sharding | Geohash grid | O(1) encode, prefix scans, no tree upkeep; over-fetch is tolerable when density is flat. |
| Highly skewed density (global app: cities vs ocean) | Quadtree / S2 hierarchy | Bounded candidates per leaf everywhere; precision follows the data, not a guess. |
(2) Neighbour expansion is mandatory, not optional
The seductive bug: "my query point is in cell X, so I'll just read cell X." Wrong. A point sitting 5 m inside the eastern edge of X has its true nearest neighbours across that edge, in the cell to the east — which your single-cell read never touches. You'd return an answer that's correct for the cell and wrong for the world. The fix is to always read the center cell plus its 8 neighbours (the Moore neighbourhood) when the query radius can reach beyond one cell, then exact-filter the union. More generally: cover the disk with the smallest set of whole cells that fully contains it, which is always ≥ the cells the disk's center sits in.
This is why the failure-mode "boundary miss" and the contract clause "never miss a point within R" are the same requirement, and why neighbour expansion is the non-negotiable correctness step — the §2 fanout cost already budgeted for it (the "+ring" in the table).
(3) Planar grids break near the poles and at ±180° — why S2 exists
Treating (lat, lng) as a flat Cartesian grid embeds two lies. First, longitude wrap: longitude is cyclic, so −179.9° and +179.9° are 22 m apart in reality but maximally far apart as numbers. A planar neighbour computation near the antimeridian reads the wrong cells and a radius query straddling it silently returns nothing across the seam. Second, pole distortion: a degree of longitude is ~111 km wide at the equator but shrinks toward 0 at the poles, so fixed-degree cells are huge near the equator and slivers near the poles — your carefully-tuned §2 precision is meaningless once latitude is high. S2 (Google) sidesteps both by projecting the sphere onto the six faces of a cube and recursively quadtree-subdividing each face into cells that are near-equal-area on the sphere, addressed by a 64-bit cell ID along a Hilbert curve. No wrap seam, no pole singularity, uniform cell area worldwide, and the cell ID is still a sortable integer that shards and range-scans like a geohash. (Uber's H3 makes the analogous choice with hexagons, which have uniform neighbour distances.)
6. Trade-offs
| Choice | Buys | Costs | Choose when |
|---|---|---|---|
| Fixed geohash grid vs quadtree | Simple keys, prefix scans, easy sharding | No density adaptation — over/under-fetch where density differs | Roughly uniform density; read-heavy; you want flat string keys |
| Coarse vs fine precision | Fewer cell reads (coarse) | More candidate filtering (coarse) / more cell reads (fine) | Set cell edge ≈ typical query radius (the §2 U-curve minimum) |
| Planar lat/lng vs S2/H3 spherical cells | Trivial math (planar) | Pole distortion + ±180° wrap bugs (planar) | Planar only if regional + mid-latitude; spherical if global |
| Index moving users vs static places | Fast query either way | Moving objects make index maintenance a write firehose | Static places: index freely. Moving: see C20's write path |
| Exact distance in-index vs post-filter | Fewer false positives (in-index) | Complex index; cells stop being simple sets | Almost always post-filter — exact-distance on a small candidate set is cheap |
The sharpest of these is grid vs tree, because it's the one you can't cheaply reverse. A flat geohash grid is so much easier to operate — stateless encode, prefix scans, partition by key prefix, rebalance hot cells by splitting the prefix range — that you should default to it and only adopt a quadtree/S2 hierarchy when measured density skew makes a single precision genuinely untenable. The dense-cell hot-shard problem this creates (a downtown cell whose id set is enormous and read constantly) is DDIA Ch. 6's partitioning-and-rebalancing problem in spatial clothing: split the hot cell into finer sub-cells and spread them across nodes, exactly as you'd split a hot key range (lesson 07).
7. Failure modes
| Failure | Mitigation |
|---|---|
| Boundary miss (point just across a cell edge omitted) | Always read center + neighbour ring, then exact-filter (§5.2) — non-negotiable. |
| Dense-cell hot shard (a downtown cell dominates reads) | Split to finer precision and spread sub-cells across nodes (DDIA Ch. 6 rebalancing). |
| Longitude wrap / pole distortion | Normalize longitude to (−180,180]; for global scope use S2/H3 spherical cells (§5.3). |
| Moving-object churn (re-cell on every GPS tick) | Only re-index on a meaningful cell change; debounce sub-cell jitter (C20). |
| Coarse precision = giant candidate set | Re-tune cell size toward the §2 minimum; cap with a secondary ranking limit. |
8. Interview Q&A
- Why can't you just use a B-tree on a "location" column? (senior answer) A B-tree orders one axis; proximity is 2-D, so points close in space aren't close in any single-key order — DDIA Ch. 3's multi-dimensional indexing problem. You tile the surface into cells and reduce "nearby" to "read a few cells + exact-filter," which a space-filling curve (Z-order for geohash, Hilbert for S2) makes range-scannable on an ordinary ordered store.
- How do you choose cell size? (senior answer) Minimise cells_read + candidates_filtered — a U-shaped curve. Too coarse drowns in candidates, too fine drowns in cell reads; the minimum sits where cell edge ≈ typical query radius. For a 500 m urban query that's geohash length 7 (~150 m). Then verify against measured density, because the optimum shifts with ρ.
- Why must you read neighbour cells, not just the cell the point is in? (senior answer) A point near a cell edge has its true nearest neighbours across that edge. Reading only the home cell silently misses them. So cover the disk with the smallest set of whole cells containing it — in practice center + 8 neighbours — then exact-filter. That's the difference between "correct for the cell" and "correct for the world."
- Geohash vs quadtree — when each? (senior answer) Geohash for roughly uniform density and simple sharding: O(1) encode, prefix = precision, no tree to maintain. Quadtree (or S2) when density is skewed: splitting where it's dense bounds the candidate count in every leaf, at the cost of mutable tree state, split/merge write amplification, and harder sharding.
- Your index works in San Francisco and breaks in Norway — what's the bug? (senior answer) A planar lat/lng grid. High latitude distorts fixed-degree cells into slivers and the ±180° wrap breaks neighbour math near the date line; SF (mid-latitude, far from the seam) hid both. Fix with S2/H3 spherical cells — equal-area, continuous Hilbert ordering, no pole singularity, no wrap seam, still a sortable integer key.
- A downtown cell becomes a read hot spot — what do you do? (senior answer) It's a hot shard (DDIA Ch. 6). Split that cell to finer precision and distribute the sub-cells across nodes, the spatial version of splitting a hot key range from lesson 07. Adaptive trees do this automatically via their bucket-cap split rule.
- How do moving objects change the design? (senior answer) They turn the index into a write firehose — every GPS tick is a potential re-cell. Debounce: only re-index when the object crosses a cell boundary, not on sub-cell jitter. The read structure is unchanged; the maintenance cost dominates. That write/streaming path is C20's focus.
- Why post-filter instead of computing exact distance inside the index? (senior answer) Cells give a cheap superset of candidates; exact great-circle distance on that small set is a handful of cheap arithmetic ops per candidate. Pushing exact geometry into the index makes cells stop being simple id-sets and complicates sharding and updates for no real win — false positives are filtered in microseconds anyway.
Related lessons
This case is the anchor for geo-cell machinery. C19 (serving / maps) links here for the read path — it consumes this index to answer "what's near me" before routing; C20 (streaming / moving objects) links here for the write path — its contribution is the re-cell-on-boundary-change debounce, not the cell structure. Sharding cells and splitting hot cells is lesson 07's partitioning-and-rebalancing (DDIA Ch. 6) applied to spatial keys; the cell→ids inverted index and forward map are lesson 04's data-modeling discipline; and the candidate/over-fetch cost is bounded by the latency/throughput reasoning in lesson 02.