Geospatial indexes

A geospatial index answers "what is near this point?" without measuring the distance to every item. It divides the map into cells and stores each item in its cell. A search then looks at the pickup's cell and a few neighbors, and ignores the rest of the city.

The big idea

Three common approaches:

• A geohash encodes a latitude and longitude as a string. Points that share a longer prefix are closer together.
• A quadtree recursively splits the map into four boxes, and splits again wherever the density is high.
• H3, from Uber, tiles the world with hexagons at several resolutions. Each hexagon has six neighbors, which makes ring searches simple.

The idea behind all three is the same. Cells turn distance into set membership, and membership is cheap to check.

Walking through it

A nearest-driver search with H3 has three steps:

1. Find the H3 cell that contains the pickup, at a resolution suited to city blocks.
2. Collect the drivers in that cell. If there are fewer than the target, such as 20, expand to neighboring cells in rings.
3. Score the candidates by road ETA and other rules, and pick the best.

A trace with an empty pickup cell:

Ring 0 (pickup cell):   0 available drivers → expand
Ring 1 (6 neighbors):   4 drivers           → 4 < 20, expand
Ring 2 (12 more cells): 16 drivers          → 20 total, stop
Rank these 20 by ETA, not the whole city.

Resolution is a product choice. Each H3 cell at resolution 7 averages about 5 km², which is too coarse for a pickup. Resolutions 8 and 9 are common for dense cities. The exact choice depends on the city and the density of drivers.

In Redis, a simple setup uses GEOADD and GEOSEARCH. A larger one keeps one set per H3 cell, containing the driver IDs. An update removes the driver from its old cell and adds it to the new one, only when the cell changes.

Common mistakes

• Searching only the pickup's cell. The nearest driver may sit in the next cell.
• Ignoring boundaries with geohash. Search the neighbors as well.
• Ranking every driver in the city. Shrink the set with the index first, then rank with ETA.

Check yourself

1. Why does a geohash search need to check neighboring cells?

   Answer: two nearby points can sit on opposite sides of a cell edge and have different prefixes, so the nearest driver may be in an adjacent cell.

2. Why expand in rings when the pickup's cell has too few drivers?

   Answer: the pickup's own cell may be empty, so the search widens to neighbors until it has enough candidates.

Key takeaways

• Geospatial indexes turn distance into cell membership, so a search looks at a few cells instead of the whole map.
• H3 hexagons have six neighbors, which makes ring searches clean.
• Geohash is simpler, but it needs neighbor searches at cell boundaries.
• Expand rings until you have enough candidates, then rank them.

Further learning

Next, see how driver locations reach the index in the first place, in driver location ingestion.