System design
Part 2 of 6 · Geospatial IndexingGeohash — Prefix Locality, Encoding, Precision & Edge Cases
Geohash turns lat/lng into a base32 string (or interleaved int) whose shared prefixes mean spatial locality — until a cell border. Encode cheaply, pick precision from radius, fan out neighbors, then haversine-filter.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Radius search with geohash
Prefer
Precision from radius, then neighbors, then true distance
Pick a cell size that matches the search radius. Union the center cell with N/S/E/W and diagonals (more rings if the radius spans several cells). Fetch, then drop anyone outside the circle.
- Shared prefixes help range scans and shard keys — until an edge.
- Integer geohash is the same bits without base32.
- Redis GEO stores a geohash in a sorted set and hides neighbor math.
Alternative
One prefix scan, or precision copied from a blog
Two cafes across a cell edge can have unrelated strings. Precision 8 with 1 Hz GPS thrashes membership. Precision 5 for a 100 m search returns a city.
- False negatives without fan-out fail the interview.
- False positives without haversine waste CPU and dispatch.
- Poles and lon ±180 need wrap — DIY bit code often forgets.
Radius query
Encode is cheap. Correctness is neighbors plus filter plus precision.
- 1
Choose precision
Map radius to cell size. Street-level nearby ≠ city-district analytics. - 2
Encode the center
Bisect lon/lat; pack base32. Same bits as an integer key. - 3
Fan out neighbors
Eight adjacent cells, or more if radius / cell size > 1. - 4
Fetch then filter
mget / GEOSEARCH, then haversine ≤ radius. Drop false positives.
Overview
Geohash turns a point into a base32 string (alphabet drops confusing letters) or an interleaved integer. Shared prefixes mean the same parent cell — useful as a Redis key, a sort key, or a shard prefix.
It is a planar lat/lng grid, not a sphere. H3/S2 exist because squares and prefix edges are awkward at global scale. Still: geohash is the interview default for KV designs and Redis GEO.
You should be able to:
- Walk encode on a whiteboard (bisect, 5 bits, character).
- Explain why prefix search is not radius search.
- Pick precision from product numbers.
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: radius search with neighbor fan-out
Flow
- 1
Step 1 Query lat lng plus radius
- nextStep 2 Pick precision from radius - 6 chars is about 1 km
- 2
Step 2 Pick precision from radius - 6 chars is about 1 km
- nextStep 3 Encode the center geohash
- 3
Step 3 Encode the center geohash
- nextStep 4 Add the 8 neighbor cells
- prefix scan onlyFailure path - points across a cell edge are missed
- 4
Step 4 Add the 8 neighbor cells
- nextStep 5 Fetch members of all 9 cells - mget or GEOSEARCH
- 5
Step 5 Fetch members of all 9 cells - mget or GEOSEARCH
- nextStep 6 Haversine filter - drop points beyond the radius
- 6
Step 6 Haversine filter - drop points beyond the radius
- nextStep 7 Return results sorted by distance
- 7
Step 7 Return results sorted by distance
- 8
Failure path - points across a cell edge are missed
Pick a precision whose cell is about the size of the radius, encode the center, then fetch the center plus the eight neighbors. Haversine drops the points that shared a cell but sit outside the circle. Sort what remains by distance.
Lesson map
Geohash — Prefix Locality, Encoding, Precision & Edge Cases
Diagram 1 walks 7 steps from Step 1 Query lat lng plus radius through Step 7 Return results sorted by distance.
Architecture. Step 1 Query lat lng plus radius Ready. Step 2 Pick precision from radius - 6 chars is about 1 km Ready. Step 3 Encode the center geohash Ready. Step 4 Add the 8 neighbor cells Ready. Step 5 Fetch members of all 9 cells - mget or GEOSEARCH Ready. Step 6 Haversine filter - drop points beyond the radius Ready. Step 7 Return results sorted by distance Ready. Failure path - points 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 Query lat lng plus radius Ready"] B["Step 2 Pick precision from radius - 6 chars is about 1 km Ready"] C["Step 3 Encode the center geohash Ready"] D["Step 4 Add the 8 neighbor cells Ready"] E["Step 5 Fetch members of all 9 cells - mget or GEOSEARCH Ready"] F["Step 6 Haversine filter - drop points beyond the radius Ready"] G["Step 7 Return results sorted by distance Ready"] X["Failure path - points across a cell edge are missed Ready"] A -->|continues| B B -->|continues| C C -->|continues| D D -->|continues| E E -->|continues| F F -->|continues| G C -->|prefix scan only| X
Diagram 2 - Failure path: shared prefix is not the same as nearby
Sequence
- 1
Search service → Search service
Step 1 user stands near the edge of the center cell
- 2
Search service → KV store
Step 2 prefix scan of the center cell only
- 3
KV store → Search service
Step 3 two points far away inside the same cell
- 4
Search service
Step 4 a cafe 50 m away hashes to the neighbor cell with a different prefix
- 5
Search service → Search service
Step 5 far points returned as nearest - false negative plus false positive
- 6
Search service
Fix - scan center plus 8 neighbors, then haversine filter
A shared prefix means the same parent cell, not a small distance. A prefix scan of the center cell returns far points inside that cell and misses the cafe 50 m away in the neighbor cell. Scan all nine cells, then filter.
Diagram 3 - Decision: geohash precision and when to use something else
Decisions
- 1
Step 1 Need proximity search
- nextStep 2 Simple KV or Redis keys enough?
- ?
Step 2 Simple KV or Redis keys enough?
- yesStep 3 Radius vs cell size?
- need uniform neighbor distanceH3 hex cells
- arbitrary polygonsR-tree or S2 cover
- ?
Step 3 Radius vs cell size?
- radius within about one cellGeohash - center plus 8 neighbors
- radius spans many cellsCoarser precision or more rings
- 4
Geohash - center plus 8 neighbors
- Wrong pick - precision too fine for the radiusFan-out grows to hundreds of cells
- 5
Coarser precision or more rings
- Wrong pick - precision too coarseHuge candidate sets to filter
- 6
H3 hex cells
- 7
R-tree or S2 cover
- 8
Fan-out grows to hundreds of cells
- 9
Huge candidate sets to filter
Geohash is enough when a KV or Redis key and a nine-cell fan-out cover the radius. If the radius spans many cells, coarsen the precision or add rings. Uniform neighbor distance wants H3. Arbitrary polygons want an R-tree or an S2 cover. Precision that is too fine explodes the fan-out. Precision that is too coarse dumps a huge candidate set on the filter.
Precision and cell size
Rule of thumb (order of magnitude — quote your library's table in production):
| Length | Scale | Typical use |
|---|---|---|
| 5 | ~5 km (district) | City analytics, coarse shards |
| 6 | ~1 km (neighborhood) | Wide nearby |
| 7 | ~150 m (street) | Ride-hail default nearby |
| 8 | ~40 m (building) | Tight geofence / indoor-ish |
Shorter prefix = coarser cell. Longer = finer. Too fine: drivers hop cells every GPS tick (write amplification). Too coarse: huge candidate sets (filter CPU).
Encoding intuition
- Bisect longitude, then latitude, alternating (bit order varies by implementation).
- Each bit chooses the high or low half of the current range.
- Pack 5 bits → one base32 character.
- Shared prefix ⇒ same parent — locality for scans and sharding.
Integer geohash is the same interleaving without the alphabet. Prefer ints as packed shard keys; prefer strings in logs and APIs.
Borders — must teach
- Two close points across a meridian or cell edge can have unrelated prefixes.
- False positives: points in the query cell farther than the radius.
- False negatives: neighbors outside the center cell — expand to 8 adjacent cells (or a k-ring analog).
- Poles and antimeridian: longitude wraps at ±180. Libraries handle this; DIY bisection must clamp and wrap.
vs H3: squares, cheaper mentally; hex has uniform neighbor distance.
vs S2: planar grid vs sphere cells; S2 better for global coverings.
vs quadtree: fixed precision vs adaptive density.
vs R-tree: excellent as a string key in KV; weak for arbitrary polygons without many cells.
Radius search
Flow
- 1
1 Query latlng plus radius
- next2 Pick precision
- 2
2 Pick precision
- next3 Center geohash
- 3
3 Center geohash
- next4 8 neighbors
- 4
4 8 neighbors
- next5 Union cell ids
- 5
5 Union cell ids
- next6 Fetch membership
- 6
6 Fetch membership
- next7 Haversine filter
- 7
7 Haversine filter
Redis GEOADD / GEOSEARCH stores a geohash in a sorted set and abstracts neighbor expansion. DIY KV still does this flowchart.
Shard by geohash prefix: yes — cell → shard / hotspot split only. Do not re-teach vnode rings.
Sandbox: encode plus neighbor idea (Python)
Didactic bisection encoder. Neighbor expansion here uses small lat/lng offsets so the sandbox stays self-contained (production uses base32 adjacency tables with border carry).
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.
Pitfalls
Pick a cell edge in a city. Encode both sides at precision 6 and 7. Do they share a prefix? If a rider sits on the west cafe, which cells do you fetch for a 200 m radius?
Interview Q&A
Why base32?
Answer
Compact string keys, sortable prefixes, human-debuggable. The alphabet skips easily confused characters. Integers pack better for shard keys.
What happens if precision is too fine?
Answer
Drivers cross cells on every GPS tick. Deletes plus inserts amplify writes. Loosen precision or update only on significant move.
What happens if precision is too coarse?
Answer
Candidate sets explode. Filter CPU and scatter-gather latency spike. Match the cell to the radius.
How does Redis GEO work at a high level?
Answer
It stores a geohash in a sorted set. GEOADD encodes; GEOSEARCH (or GEORADIUS) fans out and can return distance. You still shard at city/global scale.
Can a prefix scan replace neighbors?
Answer
Only if the query bounding box sits inside one parent cell. Any border, and you miss people. Plan 8-neighbors by default.
Shard by geohash prefix?
Answer
Yes. Map the prefix (or full cell) to a shard. Hot prefixes split — see consistent hashing for cell→shard only.
Integer vs string geohash?
Answer
Same interleaved bits. Ints pack; strings log and copy-paste. Redis GEO uses the integer form internally.
Antimeridian?
Answer
Longitude is discontinuous at ±180. Neighbor computation must wrap. A naive bbox that stretches across the date line fetches the wrong half of the planet.
When is H3 or S2 a better cell?
Answer
When you need uniform rings (H3) or spherical coverings (S2). Geohash remains fine for many KV nearby designs. Depth: S2 & H3.
Does geohash replace an R-tree?
Answer
No. Polygons and kNN inside SQL still want MBRs / GiST. Geohash is the membership and shard key.