← All articles

Geospatial indexes with geohashes and quadtrees

Updated Nov 10, 2026 · 4 min read

“Show me cars within 2 km” sounds like a simple query. With a few hundred thousand drivers moving every few seconds, it isn’t. A geospatial index turns a position into something a normal index can search, so “nearby” becomes a quick lookup instead of measuring the distance to every driver.

Why latitude and longitude alone are slow

An index on latitude finds everyone in a horizontal stripe around the world, and an index on longitude finds everyone in a vertical one. A database can use one of them well, then has to check every row in that stripe against the other. What you want is one key where nearby places sort next to each other.

Geohash

A geohash splits the world in half again and again, alternating between longitude and latitude, and writes down a bit for each choice. Every 5 bits become one base32 character. The result is a short string like gcpvj0 where each extra character narrows the cell to a 32nd of its area, and places that share a prefix are close together.

CharactersCell sizeGood for
439 km × 20 kmA metro area
54.9 km × 4.9 kmA town
61.2 km × 0.6 kmCars nearby
7153 m × 153 mA block
838 m × 19 mA building
Cell size by geohash length, near the equator. Cells get narrower toward the poles.

Store each driver under their geohash and “drivers near me” becomes “drivers whose geohash starts with these 6 characters”. Any key-value store or sorted index can answer that.

The edge problem

Two points a few meters apart can fall on either side of a cell boundary and share no prefix at all. A rider standing at the edge of their cell would never see the driver just across the line. The fix is to always search the rider’s cell and its 8 neighbors, then sort the results by real distance or, better, by driving time.

NeighborNeighborNeighborNeighborRider’s cellriderNeighbornearest driverNeighborNeighborNeighbor
Search the rider’s cell and all 8 around it. The nearest driver is often next door.

Quadtrees

Geohash cells are all the same size, but drivers aren’t spread evenly. A downtown cell may hold 500 drivers while a rural one holds none. A quadtree adapts. It starts with one square, and whenever a square holds more than some limit, say 100 drivers, it splits into four. Busy areas end up with small squares and empty ones with large squares, so every search reads about the same number of drivers.

The cost is upkeep. As drivers move, squares have to split and merge, so quadtrees usually live in memory on the service that searches them. Other options work the same way with different shapes. Google’s S2 uses cells on a cube wrapped around the earth, and Uber’s H3 uses hexagons, whose neighbors are all the same distance away.

GeohashQuadtree
Cell sizeFixed for a given lengthAdapts to how crowded an area is
Stored asA string key in any databaseA tree, usually in memory
UpdatesChange one keyMay split or merge squares
Best whenSimple, and density is fairly evenDensity varies a lot

Keeping live locations in memory

Driver positions are a write-heavy stream. 300,000 drivers sending an update every 4 seconds is 75,000 writes a second, and each position is stale within seconds. Writing every ping to a durable database is wasted work. Keep only the latest position per driver in memory, filed by cell. At about 100 bytes each, 300,000 drivers fit in 30 MB.

  • Overwrite, don’t append. Only the latest position matters for matching.
  • Expire entries that stop updating, a few intervals after the last ping, so drivers who lost signal or closed the app drop out on their own.
  • Shard by region when one node is not enough. Riders in one city never need drivers in another.
  • Send pings to a log as well if you want trip history, and keep it out of the matching path.

Matching a rider to a driver

  1. Find the rider’s cell and its 8 neighbors.
  2. Read the free drivers in those cells.
  3. Rank them by driving time, since the closest driver in a straight line may be across a river.
  4. Mark the best driver as offered in one atomic step, so no other rider can be matched to them.
  5. Send the offer. If it’s declined or times out, clear the mark and try the next driver.

The atomic mark is what stops double booking. A compare-and-set from “free” to “offered”, with its own short expiry so a crashed matcher can’t hold a driver forever, is enough.