Section 7: Turning a Circle into Cells - Deep Dive: Geo-Indexing & Candidate Retrieval
Executive Summary: We show why scans and two-column B-trees fail, compare five options, explain geohash, then run the covering algorithm on Sam's 1 km ramen search: 12 cells from the bounding box, postings intersected with filters, an exact haversine check that drops about 53%, and a per-cell cap, the budget divided by the covering, that holds every query to 5,000 candidates. Geographic sharding sends it to one shard of 64.
Asked where to go deeper, you pick geo-indexing first: everything else assumes "places near Sam" fits in 70 ms of index time against 200M places.
Why the Obvious Answers Fail
Interviewer: "Start simple. Store lat and lng and filter by distance?"
You: "A full scan computes 200M distances per query, so that's out. Two B-tree indexes look better but aren't. A B-tree orders one dimension, so lat BETWEEN 40.744 AND 40.763 gives back a 2 km-tall ribbon around the whole planet, which lng then mostly throws away. It's a 2D question asked of a 1D index. We need places that are close on the map to be close in the index."
| Option | How it localizes | Verdict and flip trigger |
|---|---|---|
| Geohash cell tokens in an inverted index (D1) | Point → base-32 cell string, indexed as keyword postings | Chosen. One engine does text, filters and geo, and the cell doubles as shard, cache-key and cap unit |
| In-memory quadtree service | Recursive splits that adapt to density | A bespoke service to build, replicate and update. Flip for sub-10 ms in-memory lookups |
| S2 / H3 | Spherical cells or hexagons, near-uniform area | Flip for polygons, polar regions or uniform-area cells |
| PostGIS R-tree | Rectangle tree on one node | Great on one node; at 200M points the limits are single-node QPS and blending text relevance, not row count |
Engine-native geo_point / BKD |
Built-in spatial tree | Viable. Rejected only because explicit cells make sharding, caching and caps controllable |
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson