H3, Geohash or Quadtree: Choosing a Geospatial Index for Driver Matching

Driver search asks one narrow question, constantly: which available drivers are near this point, ranked, right now.

It looks simple enough that it often gets whatever indexing approach the first engineer reached for. That decision then shapes query latency, infrastructure cost, and — less obviously — how the system behaves at the edges of whatever cells it divides the world into.

What the query actually has to do

Before comparing structures, it is worth being precise about the workload, because it is unusual in two ways.

The write rate is very high. Every active driver emits position updates continuously, so the index is being rewritten constantly rather than built once and queried.

The read is approximate and latency-sensitive. Dispatch does not need the mathematically nearest driver; it needs a good candidate set fast. A perfect answer that takes 400ms is worse than a good answer in 20ms, because the extra time is added directly to how long the rider waits.

That combination — write-heavy, read-approximate, latency-critical — is what makes this different from typical geospatial workloads, and it is why general-purpose spatial databases are not automatically the right answer.

Hexagonal grids

Hexagonal indexing divides the world into hexagonal cells at fixed resolutions. Each position resolves to a cell identifier, and finding nearby drivers means looking up the containing cell plus its neighbours.

The property that makes hexagons attractive here is uniformity. Every neighbour of a hexagon shares an edge and sits at the same centre-to-centre distance, so "expand the search by one ring" is a well-defined operation with predictable distance semantics. Radius expansion during reassignment is exactly that operation, which makes the two fit together neatly.

The cost is that cell size is fixed per resolution. A resolution tuned for dense city-centre supply will produce cells containing very few drivers in outer suburbs, so a single-ring lookup returns too little and you end up expanding frequently.

Geohashes

Geohashing encodes a position as a string where each additional character narrows the area. Shared prefixes mean proximity, which is convenient: a prefix query in almost any key-value store or database becomes a crude proximity query with no specialised extension.

That operational simplicity is the real argument for geohashes. If drivers' positions already live in a store that indexes strings well, proximity search is close to free.

The well-known drawback is boundary behaviour. Two points can be metres apart and share almost no prefix if they fall either side of a cell division. Handling that means querying neighbouring cells too, which is standard but adds work — and the cells are rectangular and vary in physical size with latitude, so distance semantics are less clean than the hexagonal case.

Quadtrees

A quadtree subdivides space recursively, splitting a region into four when it exceeds some density threshold. The structure adapts: dense areas subdivide deeply, sparse areas stay coarse.

That adaptivity is the appeal. A platform operating across a dense city centre and thin outer areas gets appropriate granularity in both without tuning a global resolution.

The cost is that the structure changes as data moves. With drivers updating position continuously, the tree needs rebalancing, and that maintenance competes with the query path you are trying to keep fast. Quadtrees tend to suit workloads where the underlying distribution is more stable than a moving fleet.

What should actually drive the decision

The honest answer is that all three work, and the differentiators are usually operational rather than algorithmic.

Fleet density and its variance matter most. A platform in one dense city can pick a fixed resolution and be fine. One spanning dense centres and sparse regions either needs adaptive structure or accepts frequent expansion.

Update frequency determines how much the write path matters. At high position-update rates, a structure that is cheap to query but expensive to maintain can lose to a simpler one overall.

Operational familiarity deserves more weight than it usually gets. An index your team can reason about at 3am, in a store you already run, will outperform a theoretically superior structure nobody has operated before.

Boundary handling is not optional in any of them. Every approach needs neighbour lookups. Any benchmark that skips this is measuring the wrong thing.

Separate the read paths before optimising the index

A common mistake is trying to serve every location read from one index.

Dispatch needs a fast approximate answer across many drivers. A rider watching a car approach needs a smooth accurate stream for exactly one driver. Analytics needs completeness but tolerates delay.

These have almost nothing in common, and forcing them through one path is what makes location infrastructure expensive. Separating them early often delivers more than choosing a different index would, because the high-frequency single-driver stream stops competing with dispatch search for the same resources. We go into that split in more detail on real-time tracking and location infrastructure.

Benchmark against your own data

Published comparisons of these structures are usually run against synthetic uniform distributions. Real fleets are not uniformly distributed — they cluster around demand, and that clustering is what stresses an index.

If this decision matters enough to research, it matters enough to test with a replay of actual position data at actual update rates. The result is frequently that the difference is smaller than expected, and that the surrounding architecture — how candidate lists are cached, how reassignment expands the search, how read paths are separated — matters considerably more than which of the three you chose.

---

We build the location and tracking infrastructure behind ride-hailing platforms, and the dispatch layer that queries it. If you are weighing this decision for a platform in design or already feeling it in production, we are glad to compare notes.