Geohashing and Quadtrees
The proximity problem
"Find the 20 nearest drivers", "restaurants within 2 km", "friends near me" — these spatial range queries are the core of location systems like Uber, Yelp, and nearby-friends. A naïve approach computes the distance from the user to every point and sorts — O(n) per query, hopeless at scale. The fix is a spatial index: a data structure that lets you prune almost everything and only examine points that are plausibly close. Two dominate interviews: geohashing and quadtrees.
Geohashing — turn 2D coordinates into a 1D sortable string
Geohashing recursively bisects the world. It interleaves the bits of latitude and longitude
and Base32-encodes the result into a short string like 9q8yyk. The elegant property:
Shared prefix ≈ shared location. The longer the common prefix of two geohashes, the closer the two points.9q8yyand9q8yzare neighbours;9qanddpare far apart.
Each extra character refines the cell — ~±2,500 km at length 1 down to ~±2 m at length 9. Because a geohash is just a string, a proximity query becomes a prefix scan on any ordinary B-tree index or key-value store — no special database required. That is its killer feature: it makes "near me" a problem your existing index already solves.
The edge case to mention: two points can be physically adjacent yet sit on opposite sides of a cell boundary, giving them different prefixes. Production systems query the target cell plus its eight neighbours to avoid missing points near an edge.
Quadtrees — adapt to density instead of using a fixed grid
A geohash grid is uniform: a cell over empty ocean gets the same resolution as one over Manhattan. A quadtree fixes this by subdividing only where the data is dense. Each node represents a region; when a node exceeds a capacity threshold (say 100 points) it splits into four children (NW, NE, SW, SE), recursively.
The result is an index that is shallow over sparse areas and deep over hotspots — so a dense city and an empty desert each cost roughly the same to query. You descend the tree to the leaf containing the user, then read that leaf and its neighbours.
Choosing between them
| Geohash | Quadtree | |
|---|---|---|
| Structure | Fixed grid → sortable string | Tree that adapts to density |
| Storage | Any B-tree / KV store (just a string column) | In-memory tree (rebuild/persist separately) |
| Uneven density | Wastes precision; hotspots stay coarse | Handles hotspots naturally |
| Updates | Trivial — write a new string | Costlier — may trigger node splits/merges |
| Best when | Simple, sharded, DB-backed proximity | Highly skewed density, in-memory speed |
Takeaways
- Spatial indexes turn O(n) "nearest" scans into a bounded lookup of a cell + its neighbours.
- Geohash: 2D → 1D string; shared prefix = nearby; rides on any existing index. Always query the 8 neighbours too.
- Quadtree: density-adaptive tree; ideal when points cluster (cities) and you need in-memory speed.
- See these applied in Designing Yelp / Nearby Friends and the Uber backend.
Re-authored for this guide, with concepts and diagrams adapted from Karan Pratap Singh’s System Design (course, MIT licence) and the System Design Primer (CC BY 4.0). Diagrams © their respective authors.
🤖 Don't fully get this? Learn it with Claude
Stuck on Geohashing and Quadtrees? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
Build the mental picture, not memorization.
I just read a lesson on **Geohashing and Quadtrees** (System Design) and want to truly understand it. Explain Geohashing and Quadtrees from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Socratic — adapts to where you're stuck.
Teach me **Geohashing and Quadtrees** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Active recall exposes what you missed.
Quiz me on **Geohashing and Quadtrees** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Intuition + hook + flashcards for long-term memory.
Help me remember **Geohashing and Quadtrees** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.