[System Design] H3 Geospatial Indexing: How Uber Finds Nearby Drivers with Hexagonal Spatial Index

The Problem: Finding a Needle in a Haystack Answer-first: Uber and Grab find the nearest available driver in under 100ms by dividing the Earth's surface into hexagonal cells (H3 index at Resolution 8, each ~0.74 km²). Instead of calculating distance to every driver, they look up only the 7 cells nearest to the rider — reducing millions of comparisons to dozens. When you tap "Book" on Grab, the system must find the most suitable driver within a radius of a few kilometers. But the system is tracking millions of drivers simultaneously. The naive approach — calculating the distance from you to every driver — is impossible: The Naive Approach (Brute Force): SELECT * FROM drivers WHERE ST_Distance(driver_location, rider_location) < 2000 -- 2km ORDER BY ST_Distance(driver_location, rider_location) With 5 million drivers → 5 million distance calculations Latency: takes seconds → Unacceptable The solution: Divide the map into a grid (Spatial Indexing) t