You need every driver within two kilometres of a moving rider, updated every four seconds. What index makes that cheap?

Short answer

Use a geospatial cell index such as geohash, S2 or H3 for nearby-driver search. Store each driver's current cell in an in-memory index, query the rider's cell plus neighbouring cells to avoid boundary misses, then run a real distance calculation on the candidate set. The index narrows the search cheaply; it is not the final distance answer.

The write rate comes first, because it rules out most indexes

State the load before choosing a structure. Say forty thousand drivers are on shift in a city, each reporting a position every four seconds. That is 40,000 / 4, so 10,000 position writes a second, every second, for as long as the city is awake. Rider queries are far rarer than that.

This is a write-dominated index over data that is worthless within seconds. That single characteristic eliminates a lot of options. An index with expensive updates, or one that has to be rebuilt in place, or one whose pages fragment under constant churn, is the wrong shape no matter how well it answers the read. The read is easy. Staying current is the cost.

It also tells you the current-position index does not need to be durable. If it is lost, every driver reports again within four seconds and it refills itself. Keep it in memory. Write the durable trail of positions somewhere else entirely, as an append-only stream for billing, disputes and analytics, where the access pattern is by driver and time rather than by proximity.

Why a B-tree on latitude and longitude does not work

The obvious attempt is an index on latitude and another on longitude, then a query with a range on each. It performs badly and the reason is worth being able to say.

A B-tree orders rows on one key. A range on latitude between 51.49 and 51.53 selects a horizontal band across the entire planet, which the index can seek to efficiently. The longitude predicate is then evaluated as a filter over every row in that band. You have read a strip of the world to find a square in a city. A composite index on both columns is barely better, because the second column is only useful within a single exact value of the first.

The problem is that proximity in two dimensions has no faithful representation in one ordering. Two points a metre apart can be far apart in latitude order if that metre crosses a longitude they do not share.

Interleave the bits, and nearby becomes contiguous

The trick every practical scheme uses is to build a single key that alternates between the two dimensions. Take the bits of latitude and the bits of longitude and interleave them. The resulting number encodes a repeated subdivision: each pair of bits cuts the remaining box in half vertically then horizontally, so a shared prefix means a shared box, and a longer shared prefix means a smaller shared box.

Geohash is this idea rendered in base32 text, which is why a geohash prefix behaves as an area. Drop a character and the box gets bigger. Points in the same short prefix are within a few kilometres of each other; a longer prefix narrows that to a block. The exact size depends on the length and on the latitude, since cells of constant degree width are physically narrower away from the equator.

S2 projects the sphere onto the six faces of a cube and orders cells along a space-filling curve within each face, which avoids the pole distortion and gives cells of more even area. H3 tiles with hexagons, which has the property that every neighbour shares an edge and is the same distance away, so smoothing and neighbour traversal are tidier. Any of the three is a defensible answer. What matters is that you can say what the encoding buys: a proximity query becomes one or more range scans on an ordered key.

In an in-memory store the shape is a set per cell. The driver's cell id is the set's key and the driver id is a member. A position update is two operations: remove from the previous cell, add to the new one. Most updates do not change the cell at all, because a car covers a small fraction of a cell edge in four seconds, so most of your ten thousand writes a second touch nothing but a timestamp. Redis models this directly by storing an interleaved geohash as the score of a sorted set, so proximity queries are score ranges.

A gridded street atlas is the same idea on paper. The index at the back tells you a street is in square F4, and to find everything near a junction you look at F4 and the squares around it. Where the paper analogy fails is scale: every square on the page is the same size, whereas a spatial index has to choose a cell size once and then live with density that varies by a factor of a thousand between a city centre and a ring road.

The boundary problem, and why one cell is never the answer

Here is the mistake that makes a demo look correct and a product look broken. A rider standing near the edge of a cell has drivers fifty metres away sitting in the cell next door, and those drivers have a different prefix. Query only the rider's own cell and you confidently return the wrong answer, biased in a way that is hard to notice: the missing drivers are always the closest ones on one side.

So the query is the rider's cell plus its neighbours. On a square grid that is nine cells; on a hexagonal grid it is seven. Choose the cell size so that its edge is at least the search radius, and nine cells then cover any two-kilometre circle regardless of where in its cell the rider stands. Pick cells much smaller than the radius and you must enumerate dozens of them; pick them much larger and each scan returns far more candidates than you want.

The cell scan produces candidates, not results. Every candidate is then filtered by a real distance computation, haversine on the two coordinate pairs, because a cell is a box and the request was a circle, and the corners of nine boxes reach well beyond two kilometres. Presenting the cell contents as the answer is the second half of the same error as ignoring neighbours.

The rider is moving, and that changes less than it sounds

A moving query point is not a new index problem. The rider's own cell changes rarely, so recomputing the candidate set on every rider tick is wasted work. Recompute when the rider crosses a cell boundary, or on a slower timer than the driver updates, and interpolate the display in between.

Two smaller points earn credit. Drivers should be expired from the index rather than deleted on sign-off, because a phone that dies never sends a sign-off and a stale position is worse than a missing one — give each entry a time-to-live a little longer than the reporting interval. And straight-line distance is not the ranking anyone wants: a driver eight hundred metres away across a river is further in driving time than one two kilometres away on the same road. The index narrows forty thousand drivers to a few dozen candidates cheaply, and a routing service ranks those few dozen expensively. Keeping those two jobs separate is what makes the expensive one affordable.

The index exists to turn a two-dimensional neighbourhood into a contiguous range on one key, and it earns its keep by producing a small candidate set fast, not by being right about distance.

---

© 2026 Preptima. Originally published at preptima.com.