Geospatial Indexing: Geohash, Quadtrees & H3

In one line

'Find drivers within 2 km' can't scan every driver. Geospatial indexes turn 2-D locations into cells or keys you can look up quickly: geohash strings, quadtrees that split busy areas, and hexagonal grids like H3.

0/8 · 0%

Think of it like this

Finding a friend in a huge stadium. Instead of checking every seat, you use section numbers: go to section B7 and look around it and its neighbours. Geospatial indexes give every location a 'section number' so nearby things share it.

Key ideas

01
GEOHASH: interleaves latitude and longitude bits and encodes them as a base32 string; longer strings are smaller cells (6 chars ≈ 1.2 km × 0.6 km). Points with the same prefix are close, so 'nearby' becomes a prefix/range lookup in any key-value store or index. Edge problem: two points either side of a cell border can have different prefixes, so always search the cell PLUS its 8 neighbours.
02
QUADTREE: recursively splits the map into four squares until each square holds at most N points. Dense cities get tiny cells, deserts stay one big cell, so it adapts to uneven density. Usually kept in memory by a location service and rebuilt or updated as points move.
03
H3 (Uber) and S2 (Google): hierarchical grids of hexagons or spherical cells. Hexagons have uniform neighbour distances, ideal for surge pricing areas, heatmaps, and demand forecasting. Databases: PostGIS (R-tree/GiST indexes) for rich geometry queries; Redis GEOADD/GEOSEARCH (geohash sorted sets) for fast radius queries; Elasticsearch/OpenSearch geo queries.
04
For MOVING objects (drivers updating every 4 seconds), write load dominates: keep current locations in memory/Redis keyed by cell, update cell membership only when a driver crosses a cell border, and treat locations as ephemeral (Phase 12, Uber / proximity service).

Code & diagrams

Redis geo searchbash

GEOADD drivers:active 77.5946 12.9716 driver:17
GEOADD drivers:active 77.6010 12.9750 driver:42
GEOSEARCH drivers:active FROMLONLAT 77.5950 12.9720 BYRADIUS 2 km ASC COUNT 10 WITHDIST
1) 1) "driver:17"
   2) "0.0580"
2) 1) "driver:42"
   2) "0.7810"

Explain without notes

Why must a geohash search also check neighbouring cells?

Practice

Design 'restaurants within 3 km that are open now' for 5 million restaurants.

Trade-offs

↔
Geohash: simple, works in any key-value store, fixed cell sizes. Quadtree: adapts to density, but in-memory and more complex to shard. H3/S2: uniform, hierarchical cells, needs libraries.

Run it in production

You've designed it. Now build, operate, and break the same idea hands-on in the DevOps courses:

Stateful · Redis & caching patterns

Cache-aside with a stampede lock, TTLs, rate limiting, and sessions in Redis.

Completion checklist

I can explain geohash prefixes and the neighbour-cell rule
I can choose an index for static vs moving points

Back to phase

Command Palette