Geospatial indexing
Geohashes, quadtrees and S2 cells: turning 'nearby' into a range query.
01The intuition
The problem it solves
You are standing in a city and want the nearest five pharmacies. A phone book lists 300 million businesses alphabetically. Checking the distance to every one of them for every search is 300 million subtractions per query; with 10 billion queries a day that is impossible. What you want is a book arranged by place, so that "near here" is a few pages, not the whole book.
Databases index numbers and strings in one dimension; a B-tree can find everything between 10 and 20. "Nearby" is two-dimensional (latitude and longitude), and no single sorted order keeps nearby points together. Geospatial indexes squeeze two dimensions into one key in a way that mostly preserves nearness, so "within 2 km" becomes a handful of range queries an ordinary index can answer.
Build it one piece at a time
Step 1: a grid. Divide the map into squares 1 km on a side and give each a number. Store every pharmacy under its square's number. A nearby search reads the user's square and its 8 neighbours, 9 lookups instead of 300 million.
Step 2: squares that nest. A fixed grid is too coarse in Mumbai and too fine in the Thar desert. A geohash fixes that: split the world in half repeatedly, alternating longitude and latitude, and write down the choices as a string. Each extra character divides the cell by 32. Two places with the same 6-character prefix are within about 1.2 km of each other, and the prefix is a string an ordinary index can range-scan.
| Geohash precision | Cell size | Use |
|---|---|---|
| 4 characters | about 39 km × 20 km | city-level grouping |
| 6 characters | about 1.2 km × 0.6 km | "pharmacies near me" |
| 8 characters | about 38 m × 19 m | a building |
Step 3: search a radius. Compute the user's geohash at the precision matching the radius, take it and its 8 neighbours, range-scan the index for each prefix, then compute exact distances only for the few hundred candidates and keep the nearest five. The neighbours matter because a user at a cell's edge has close points across the border.
Step 4: adapt to density. A quadtree splits a cell into four only when it holds more than, say, 100 points, so dense cities get small cells and deserts stay as one. Google's S2 library does the same on a sphere with a space-filling curve, which avoids geohash's distortion near the poles and its uneven cells.
Step 5: moving points. For drivers whose position changes every few seconds, the index is an in-memory map from cell to the set of drivers currently in it; an update is a remove from the old cell and an add to the new one. Shard cells across servers by region, and expect the airport cell to be a hot shard worth splitting.
Why it works, with the numbers
Nearness in a key means a query reads a small, contiguous slice of the index:
candidates checked ≈ 9 cells × points per cell; for 300 million places over 50 million cells at 6 characters, about 9 × 6 = 54 distance computations instead of 300 million
At 10 billion queries a day (about 115,000 a second), 54 distance computations each is a few million arithmetic operations a second, trivial, so the real cost is the index lookups, which is why the index lives in memory and is replicated. The guarantee is that every point within the radius is among the candidates as long as the cell size is at least the radius and the neighbours are included. The failure modes are the edge case the neighbours fix (forgetting them loses results), hot cells (a stadium during a match), and precision mismatch (searching 50 km with 8-character cells means thousands of range scans).
The trade-off you must say out loud
A geohash is simple and works with any sorted index but has uneven cells and the border problem; quadtrees and S2 are adaptive and accurate but need their own structure. Say which you chose and the cell precision for the radius you expect. The interviewer's next question is almost always "what about the airport?", meaning hot cells, and then "how fresh must a driver's position be?", which decides whether the live index is in memory or on disk.
Where it shows up in the 100 Google problems
- Design nearby places search (NALSD): the index above, sized to the given machines and the 8 ms budget.
- Design Uber: an in-memory cell-to-drivers map updated every few seconds, sharded by region.
- Design Google Maps: tiles and places both keyed by cell so a viewport is a range of cells.
- Collect GPS data and show live traffic: positions bucketed by cell and road segment before aggregation.
- Design a personalized deals and promotions service: "a store near you has a deal" is a nearby query over stores with active promotions.