Quadtree & Geohashing
Spatial indexes for nearby search — split map into cells (quadtree) or encode lat/lng as string prefix (geohash).
Interview tip Lead with a 30-second definition, then one real system example and name 2–3 designs where Quadtree & Geohashing is non-negotiable.
① What it is (30 seconds)
Spatial indexes for nearby search — split map into cells (quadtree) or encode lat/lng as string prefix (geohash).
② How it works in system design
Quadtree recursively subdivides until cell has few POIs. Geohash: lat/lng → base32 string; neighbors share prefix. Redis GEO uses geohash internally. S2 used at Google.
Typical placement
Client→Edge / Gateway→Quadtree→Services→Data stores
③ Concrete system design example
Scenario: Yelp nearby: query geohash cells covering search circle, fetch POI IDs, rank by distance. Uber: quadtree index for driver locations updated every second.
④ Important interview Q&A
| Question | Answer |
|---|---|
| Geohash vs quadtree? | Geohash simple prefix queries; quadtree adaptive density for uneven POI distribution. |
| Edge cases? | Geohash distortion near poles; S2 cells more uniform globally. |
| Redis GEORADIUS? | Uses geohash-encoded sorted set — practical interview answer for proximity MVP. |
⑤ Seen in these system designs
- Google Maps — spatial tiles
- Uber / Rides — driver index
- Proximity Service — nearby POI
In interviews, after explaining the concept, say: "This shows up directly in …" and link two designs.
⑥ Revision checklist
- Geohash prefix search
- Quadtree split rule
- Redis Geo mention
- S2 at scale