What it is
“Find the drivers near this rider” and “restaurants within 2 km” are proximity queries over two-dimensional data, and a normal index is one-dimensional. Geospatial indexing reduces 2D proximity to a 1D key that an ordinary index (a sorted set, a B-tree, a prefix scan) can serve. Every design decision downstream (sharding, update cost, boundary handling) follows from which scheme you pick: geohash, a quad-tree, or S2 / H3 cells.
Important
Key takeaway: Turn “near” into “same cell or a neighboring cell”. Index points by a cell id, query the cell and its neighbors (a 3×3 grid), then rank candidates by exact distance. In many geospatial systems the real load is the location update rate, not the queries, so an index with an O(1) update wins.
When you care
Ride matching, “nearby” search, delivery, and geofencing. The interviewer probes the boundary problem and the index choice, and often the real bottleneck.
Note
Interview signal: Saying “the location update firehose is the real load, not the rider’s query” (hundreds of thousands of updates per second against far fewer queries) shows you found the real load before choosing the design. Naming the boundary problem unprompted is the second signal.
The three schemes
| Dimension | Geohash | Quad-tree | S2 / H3 |
|---|---|---|---|
| Key | A 1D string prefix, trivially indexable | A tree traversal | A 1D cell id (Hilbert curve or hex) |
| Density adaptation | Fixed cell size per prefix length: poor with skew | Excellent: splits where points are dense | Good: multi-resolution cells |
| Update cost | O(1): recompute the hash and move cells | O(log n): may split or merge | O(1): recompute the cell id |
| Boundary problem | Severe: neighbors can share no prefix | Handled by the tree | Handled by cell adjacency |
| Complexity | Low | Medium | High: use a library |
| Explainability | High | Medium | Low (hand-wave the projection) |
Geohash. Interleave the bits of latitude and longitude and encode them in base 32. Nearby points share a prefix, so a proximity query is a prefix scan over a plain string index. Cell size is set by the prefix length:
| Geohash length | Approximate cell size |
|---|---|
| 5 | About 4.9 km × 4.9 km |
| 6 | About 1.2 km × 0.6 km |
| 7 | About 150 m × 150 m |
| 8 | About 38 m × 19 m |
Quad-tree. Recursively split space into four quadrants only where a cell holds more than K points, so a dense downtown gets deep, fine cells and a rural area stays coarse. A query descends to the relevant leaves. It adapts to density but adds rebalancing logic.
S2 and H3. S2 projects the sphere onto a cube and orders cells along a Hilbert curve; H3 uses hexagonal cells. Hexagons have properties that matter for dispatch and pricing: every neighbor shares an edge (not just a corner), so the ring of 6 neighbors is a tighter, more uniform band than 8 square neighbors, and all neighbors are equidistant from the center.
Tip
Why geohash for the interview, with H3 named:
Geohash turns the hard part (2D proximity) into the easy part (a 1D prefix scan that any sorted index supports), and an O(1) update
fits an update-bound system. Name H3 as the production upgrade when density skew or neighbor uniformity matters. At small scale, Redis’s
built-in geo commands (GEOADD, GEOSEARCH) are a complete answer; the reason to go further is that one key does not shard by region.
The boundary problem
Caution
Common mistake: Querying only the rider’s own cell. Two points a meter apart on opposite sides of a cell edge have completely different geohashes with no shared prefix, so a driver just across the street is missed. This is the most common geospatial bug.
The fix: query the rider’s cell plus its 8 neighbors (a 3×3 grid; geohash libraries have a neighbors() function), gather the
candidates, and compute the exact haversine distance to filter and sort. The cells give recall; the exact distance gives precision.
Choose the cell size so that 3×3 cells cover the search radius.
Worked example. A rider searches within 500 m. At geohash length 6 (cells about 1.2 km × 0.6 km), the 3×3 block extends at least 0.6 km past the center cell in every direction, which contains a 500 m radius around any point in the center cell. Scan the 9 cells, gather perhaps a few hundred drivers, compute the exact distance to each, and return the nearest. Too fine a cell (length 8) would need many more cells to cover 500 m; too coarse (length 5, about 4.9 km) gathers far too many candidates to rank.
Where the load really is
Ride-hailing illustrates it: drivers report their location every few seconds, so a large city sees on the order of 750,000 location updates a second but far fewer rider queries (on the order of 100,000 a second). The live index is small (hundreds of megabytes for all active drivers) but rewritten constantly, so it must live in memory, and the design is dominated by update throughput: an O(1) update (recompute the cell, move the driver between two cell sets) is the property that matters.
- Index structure:
cell id -> set of driver ids, plusdriver id -> (lat, lng, cell, updated_at)so a move is an O(1) delete from the old cell and insert into the new one. - Sharding: by geographic region (city or a coarse cell prefix), because proximity queries are inherently local and a rider’s query is then answered by one shard. Sharding by driver id would force every query to scatter to all shards.
- A match hold: when two requests want the same driver, claim the driver with an atomic set-if-absent and a time-to-live, so a double-match is impossible and a crashed matcher releases the hold by itself.
When to pick what
| Situation | Choose | Why |
|---|---|---|
| Small scale, a managed store | Built-in geo commands (Redis GEO) | Done in a day |
| Update-bound, uniform-ish density | Geohash grid, 9-cell scan | O(1) update; simple |
| Wide density differences (city centers versus suburbs) | Quad-tree, or H3 at multiple resolutions | Adapts cell size to load |
| Dispatch, surge pricing, neighbor uniformity | H3 | Hex neighbors are equidistant |
| Shards | Geographic region, not entity id | A query hits one shard |
| Exact ranking | Haversine distance on the candidates | Cells give recall only |
Related
- Walkthrough: Designing a Geospatial Matching System — the full ride-matching design this index serves, including the driver hold.
- Reference: Two-Stage Ranking and the Retrieval Funnel — the same retrieve-then-rank shape: cells give recall, exact distance gives precision.
- Reference: Partitioning Strategies — why sharding by region, not by entity id, keeps a proximity query on one shard.