STANDARDwalkthrough

Geospatial Indexing (H3)

1 of 8

3 related

How do we find the 10 nearest drivers out of 500,000 broadcasting GPS every 3 seconds? Brute-force distance calculation against every driver is

O(n)

per query and takes 200ms at 500K entries.

167K

writes/sec saturating MySQL

Trade-off: we gave up QuadTree's adaptive density in exchange for zero write contention. H3 divides the Earth into hexagonal cells at 16 resolutions.

“We chose the H3 hexagonal grid (not QuadTree) because H3 cell assignment is a pure function of (lat, lng) with no tree mutations, while QuadTree rebalances on every insert at 167K writes/sec.”

At resolution 9, each cell covers roughly 0.1 km^2 (about one city block). To index a driver, we compute the H3 cell ID from GPS coordinates in

O(1)

and insert into a Redis sorted set keyed by that cell ID.

To find nearby drivers, we compute the rider's cell ID and query the cell plus its 6 adjacent neighbors (a k-ring query), returning all drivers within 1-2 km in

O(1)

cell lookups. Why hexagons over squares?

Hexagons have uniform neighbor distances: every neighbor's center is equidistant from the query cell, eliminating the diagonal bias that makes square grids return drivers at 1.41x the expected distance in corner cells. Uber's DISCO dispatch system processes 167K location updates per second through this index.

Why it matters in interviews

Interviewers want to hear us explain why H3 beats QuadTree for a write-heavy workload. QuadTree rebalances on every insert; H3 cell IDs are computed from coordinates with no tree mutation. What if the interviewer asks: 'Why not a QuadTree with lazy rebalancing?' We answer: even lazy rebalancing causes lock contention at 167K/sec because multiple threads compete for the same internal nodes.

Related concepts

Next →Ride Matching / Dispatch