System design
Part 1 of 6 · Geospatial IndexingGeospatial Indexing — Cells, Trees & Proximity at Scale
Ride-hail, delivery, and maps live or die on nearby search. Index lat/lng with cells (geohash, S2, H3), adaptive trees (quadtree), or MBR trees (R-tree). Always fan out neighbors and filter true distance.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
How you index lat/lng at city to global scale
Prefer
Match the index to the access pattern
Fixed cell IDs shard cleanly and update with TTL. Adaptive trees follow density. MBR trees win on polygons and kNN inside a database. Cells are buckets — neighbors plus a true-distance filter are mandatory.
- Shard keys: geohash, H3, or S2. Hex rings: H3. Sphere coverings: S2.
- Skewed maps / tiles: quadtree. PostGIS predicates: R-tree via GiST.
- Moving drivers: cell membership. Static POIs: bulk-load R-tree or precomputed tiles.
Alternative
One global R-tree, or prefix scan with no neighbors
A single tree cannot absorb GPS upserts. A single cell misses everyone across the border. Interviews fail on false negatives, not on naming H3.
- Prefix locality dies at cell edges and the antimeridian.
- Hot cells (airports) melt one Redis key and one shard.
- GiST is an SQL access method — not a fleet membership store.
Nearby plus dispatch — the hub pipeline
Each hop is a later lesson. Interviews start at fan-out and hotspots, not at base32 trivia.
- 1
Encode the cell
GPS and the query lat/lng become a geohash, H3, or S2 id at a product resolution. - 2
Upsert membership
Cell → entity set with TTL. Moving objects overwrite; crashed apps expire. - 3
Fan-out neighbors
Center plus 8-neighbors, k-ring, or an S2 covering. Depth: geohash and S2/H3 pages. - 4
Filter true distance
Haversine / great-circle (and ETA). Cells over-approximate. - 5
Shard and split hotspots
Cell → shard. Airports get finer precision or sub-shards. Depth: location services.
Overview
Interview prompt: design nearby search and driver dispatch. Seniors are graded on index choice, border false negatives, and hotspot splits — not on naming a library.
Geospatial indexes turn lat/lng into something you can shard, scan, and prune. Three families:
- Fixed cells — geohash, S2, H3. Stable IDs. Cheap encode. Neighbor tables or k-rings.
- Adaptive space partition — quadtree. Deep downtown, shallow desert.
- MBR trees — R-tree / R-star. Rectangles and polygons inside a spatial DB.
Rule of thumb: fixed cell shard keys → geohash / H3 / S2. Adaptive density → quadtree. Geometry predicates in SQL → R-tree via GiST. Hex analytics and k-rings → H3. Spherical coverings → S2.
This hub is the map. The five sibling pages are the whiteboard depth.
You should be able to:
- Draw ingest → encode → membership → fan-out → filter → match → hotspot split.
- Say when you would refuse a global R-tree or a prefix-only scan.
- Cross-link GiST and cell sharding without teaching B-tree/Hash/GIN or hash rings.
Diagrams - step by step
Three small diagrams. Step numbers in the labels give the animation order. The lesson map under Diagram 1 plays those steps.
Diagram 1 - Happy path: cell index for nearby search
Flow
- 1
Step 1 Driver GPS update arrives
- nextStep 2 Encode lat lng to a cell id - geohash, H3 or S2
- 2
Step 2 Encode lat lng to a cell id - geohash, H3 or S2
- nextStep 3 Upsert driver into the cell set with a TTL
- 3
Step 3 Upsert driver into the cell set with a TTL
- cell setsStep 6 Fetch candidates from those cells
- 4
Step 4 Rider asks for nearby drivers
- nextStep 5 Cover the radius - center cell plus neighbors
- 5
Step 5 Cover the radius - center cell plus neighbors
- nextStep 6 Fetch candidates from those cells
- 6
Step 6 Fetch candidates from those cells
- nextStep 7 Haversine filter, then rank by ETA
- center cell onlyFailure path - drivers just across a cell edge are missed
- 7
Step 7 Haversine filter, then rank by ETA
- 8
Failure path - drivers just across a cell edge are missed
A GPS update becomes a cell id and a TTL membership write. A nearby query covers the center cell plus its neighbors, fetches those sets, then keeps only points that pass haversine and ranks them by ETA. The cell is a bucket, not the answer.
Lesson map
Geospatial Indexing — Cells, Trees & Proximity at Scale
Diagram 1 walks 7 steps from Step 1 Driver GPS update arrives through Step 7 Haversine filter, then rank by ETA.
Architecture. Step 1 Driver GPS update arrives Ready. Step 2 Encode lat lng to a cell id - geohash, H3 or S2 Ready. Step 3 Upsert driver into the cell set with a TTL Ready. Step 4 Rider asks for nearby drivers Ready. Step 5 Cover the radius - center cell plus neighbors Ready. Step 6 Fetch candidates from those cells Ready. Step 7 Haversine filter, then rank by ETA Ready. Failure path - drivers just across a cell edge are missed Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB A["Step 1 Driver GPS update arrives Ready"] B["Step 2 Encode lat lng to a cell id - geohash, H3 or S2 Ready"] C["Step 3 Upsert driver into the cell set with a TTL Ready"] R["Step 4 Rider asks for nearby drivers Ready"] D["Step 5 Cover the radius - center cell plus neighbors Ready"] E["Step 6 Fetch candidates from those cells Ready"] F["Step 7 Haversine filter, then rank by ETA Ready"] X["Failure path - drivers just across a cell edge are missed Ready"] A -->|continues| B B -->|continues| C R -->|continues| D C -->|cell sets| E D -->|continues| E E -->|continues| F E -->|center cell only| X
Diagram 2 - Failure path: center-cell-only lookup misses close drivers
Sequence
- 1
Rider app → Nearby API
Step 1 find drivers within 1 km
- 2
Nearby API → Cell store
Step 2 read the center cell only
- 3
Cell store → Nearby API
Step 3 drivers inside that one cell
- 4
Nearby API → Rider app
Step 4 the driver 300 m away is missing - he sits across the cell edge
- 5
Nearby API
Fix - read center plus neighbor cells, then haversine filter
The driver 300 m away sits just across the cell edge, so a center-only read never returns him. Read the center plus the neighbor cells, then drop anyone outside the true radius.
Diagram 3 - Decision: pick the index by access pattern
Decisions
- ?
Step 1 What dominates the workload?
- moving fleet pointsStep 2 Need hex rings or demand bins?
- static polygons in SQLR-tree via GiST
- very uneven densityQuadtree
- global sphere coveringsS2 cells
- ?
Step 2 Need hex rings or demand bins?
- yesH3 cells
- no - simple KV keysGeohash cells
- 3
H3 cells
- 4
Geohash cells
- 5
R-tree via GiST
- Wrong pick for a fleet updating every few secondsMBR updates thrash index pages
- 6
Quadtree
- 7
S2 cells
- 8
MBR updates thrash index pages
Moving fleet points want a cell id: H3 when you need hex rings, geohash when a simple KV key is enough. Static SQL polygons want an R-tree. Very uneven density wants a quadtree. A global sphere covering wants S2. Putting that moving fleet in an R-tree thrashes MBR pages.
Pick by access pattern
| Index | Wins | Loses |
|---|---|---|
| Geohash | String/int key, Redis GEO heritage, cheap neighbors | Square-ish cells; border prefix breaks; planar vs sphere |
| Quadtree | Density-adaptive; maps tiles; sparse + dense in one tree | Unstable as a cross-service shard key; move cost on splits |
| R-tree / R-star | MBRs, range, kNN, polygons (PostGIS GiST) | Write-heavy movers thrash pages |
| S2 | Sphere → Hilbert cell IDs; mixed-level coverings | Heavier API; square-ish on cube faces |
| H3 | Hex neighbors ≈ equidistant; demand/supply bins | 12 pentagons; library dependency |
GiST is the Postgres framework that stores an R-tree-like geometry index. Depth of operator classes lives in B-tree vs Hash vs GIN vs GiST — stay on geometry here.
Nearby plus dispatch
GPS updates and rider requests share an encoder. Membership is a KV set. Queries never trust one cell.
Flow
- 1
1 GPS update
- next2 Encode cell
- 2
2 Encode cell
- next4 Cell to entity set
- next5 Center plus neighbors
- 3
3 Query latlng
- next2 Encode cell
- 4
4 Cell to entity set
- 5
5 Center plus neighbors
- next6 Haversine filter
- 6
6 Haversine filter
- next7 Rank ETA
- 7
7 Rank ETA
- next8 Hotspot split
- 8
8 Hotspot split
Cell → shard mapping (and splitting a melted airport cell) is the only consistent-hashing beat on this cluster: rings / vnodes. Do not redraw Maglev or RF walks here.
Architecture that stitches the indexes: nearby search, dispatch shards, hotspots.
Sequence
- 1
1 Driver → 2 Cell index
upsert cell TTL
- 2
3 Nearby → 2 Cell index
encode plus neighbors
- 3
2 Cell index → 3 Nearby
candidate ids
- 4
3 Nearby
haversine then rank
Decision: which index?
Interviews want a chooser, not a favorite library.
Decisions
- 1
1 Need
- next2 SQL geometry?
- ?
2 SQL geometry?
- yes3 R-tree GiST
- no4 Hex rings?
- 3
3 R-tree GiST
- ?
4 Hex rings?
- yes5 H3
- no6 Sphere cover?
- 5
5 H3
- ?
6 Sphere cover?
- yes7 S2
- no8 Adaptive density?
- 7
7 S2
- ?
8 Adaptive density?
- yes9 Quadtree
- no10 Geohash or H3 or S2
- 9
9 Quadtree
- 10
10 Geohash or H3 or S2
Teaching point: cells are approximate buckets. Borders need neighbor fan-out. Candidates need a precise filter.
Sandbox: index chooser (Python)
Educational picker. SQL geometry points at R-tree/GiST. Hex rings at H3. Sphere cover at S2. Adaptive density without a durable shard key at quadtree.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Same idea (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Read-heavy maps vs write-heavy fleets
- Static tiles / POIs — precomputed quadkeys or S2 coverings; CDN. Rebuild on snapshot.
- Live fleet — cell membership with TTL / overwrite. Do not split R-tree pages on every GPS tick.
- Geofences / zones — R-tree or S2 covering in Postgres. Lower QPS than membership.
Pitfalls
A rider at an airport asks for a car within 500 m. Draw encode → k-ring or covering → mget → haversine → rank. Then double driver density in that cell. Do you refine resolution, split the shard, or both? Which index did you pick for membership vs geofences?
Interview Q&A
Why not one global R-tree for drivers?
Answer
Moving drivers are a high write rate. R-tree pages split and MBRs churn. Fixed cells shard cleanly and overwrite membership. Keep R-trees for polygons, geofences, and static POIs inside a DB.
Geohash vs H3 for dispatch?
What are border false positives and false negatives?
Answer
False positives: candidates in the query cell farther than the radius — filter with haversine. False negatives: nearby points across the edge — expand to neighbors / k-ring / covering, then filter.
How do you handle an airport hotspot?
Answer
One cell owns too many drivers and too much QPS. Raise local precision, split into sub-shards, or map the hot cell onto extra keys. Cell→shard rebalance is consistent hashing — not a new ring lecture.
Read-heavy map tiles vs write-heavy fleet?
Answer
Tiles: precomputed quad/S2, CDN, snapshot rebuilds. Fleet: cell membership with TTL. Do not share one index for both QPS shapes.
Why hexagons?
Answer
A hex has six equidistant neighbors. Squares have diagonal asymmetry (edge vs corner). H3 exploits that for rings and heatmaps.
S2 vs H3 in one sentence each?
Answer
S2: Hilbert-ish cell IDs on a sphere — strong mixed-level coverings for polygons and caps. H3: hex hierarchy — strong k-rings, analytics bins, and dispatch catchments.
What is GiST doing here?
Answer
Postgres access method for lossy trees. Geometry uses an R-tree-like GiST opclass. See B-tree vs Hash vs GIN vs GiST for the AM — do not recap those other methods on this page.
Can a geohash prefix scan replace neighbor expansion?
Answer
Only if the query bbox sits inside one parent cell. Borders, poles, and the antimeridian break that. Always plan fan-out.
Where does consistent hashing show up?
Answer
Map cell_id → shard, and split a hot cell onto more owners. Do not re-teach vnode rings, HRW, or Maglev here — that cluster already exists.