Geospatial Indexing

Intermediate · 17 min read · High-Level Design, Data Processing & Specialised Systems

Geohashes, quadtrees, S2 and H3 — finding what is nearby, fast.

"Find drivers within 2 km", "restaurants near me", "which delivery zone is this address in?" — location queries power ride-hailing, food delivery, maps, dating apps and local search. A naive approach compares the user's position with every point in the database.

Why ordinary indexes aren't enough

Location is two numbers: latitude and longitude. You could index each separately and query a bounding box:

Geohash

A geohash recursively halves the world: alternate between splitting longitude and latitude, emitting one bit per split, then encode the bits in Base32. Each additional character narrows the cell.

Quadtree

A quadtree recursively divides space into four quadrants, but only where there's data: split a node when it holds more than k points (e.g., 100).

R-Tree

An R-Tree groups nearby objects into bounding rectangles, nested hierarchically — like a B-Tree for rectangles. It handles shapes (polygons, delivery zones, road segments), not just points. It's the index behind PostGIS (via GiST) and many spatial databases.

S2 and H3: cells on a sphere

Geohash distorts badly near the poles and cells aren't uniform in area. Large-scale systems use spherical cell systems:

Moving objects: drivers and couriers

Static places (restaurants) change rarely. Drivers update their location every few seconds, which changes the design:

Distance calculations

After the index narrows candidates, compute exact distance — the haversine formula for great-circle distance — and sort. For "nearest by driving time" (what users actually care about), call a routing engine for the top few candidates only, since road-network ETA computation is far more expensive than straight-line…

Interview questions

  • Why do geohash-based searches query the 8 neighbouring cells too?
  • Geohash or quadtree for a Yelp-like 'nearby businesses' service?
  • How would you handle 1 million drivers sending location updates every 4 seconds?

Practice

Write your answer before opening the suggested one. Anything you mark "Partly" or "Missed it" comes back in your review deck.

Further reading

Key takeaways

  • Ordinary B-Tree indexes can't search two dimensions efficiently; geo indexes map nearby points to nearby keys.
  • Geohash: prefix = cell; search the cell plus 8 neighbours, then filter by exact distance.
  • Quadtrees adapt to density; R-Trees handle shapes; S2 and H3 provide uniform cells on a sphere with 64-bit IDs.
  • Moving objects belong in a sharded in-memory geo index with TTLs, with history streamed asynchronously.
  • Narrow with the index, filter with haversine, and use a routing engine only for the final few candidates.

Previous: Search & Inverted Indexes · Next: Probabilistic Data Structures