Spatial Indexing (QuadTrees & GeoHashing)

"Find drivers within five miles" looks like an ordinary query. Written naively it is not:

SELECT * FROM drivers
WHERE sqrt(pow(lat - :lat, 2) + pow(lon - :lon, 2)) < 5;

The distance is computed from two columns, so no index can be used. The database evaluates that expression for every driver on Earth and then throws almost all of them away.

An index on lat does not rescue you either. It narrows the search to a horizontal band of the planet — every driver at that latitude, from London to Vladivostok — and you still scan the band. A B-tree orders one dimension, and location is two.

The whole discipline of spatial indexing is one idea: collapse two dimensions into one ordered key, so an ordinary index works again.

Geohash: two dimensions folded into a string

Split the world into four quadrants and label them. Split each quadrant into four again, and again, appending a character each time. Any point is then described by the sequence of cells it fell into.

┌─────────┬─────────┐        ┌─────┬─────┐
│   NW    │   NE    │  zoom  │ 00  │ 01  │
├─────────┼─────────┤  ───►  ├─────┼─────┤
│   SW    │   SE    │        │ 02  │ 03  │
└─────────┴─────────┘        └─────┴─────┘

San Francisco at 37.7749, -122.4194 becomes 9q8yyk8y. Each additional character is one more subdivision, so longer means smaller and more precise.

The property that makes it useful falls straight out of the construction: points sharing a prefix are inside the same cell, and therefore near each other.

9q8yyk8y   ← driver A
9q8yyk8z   ← driver B, same building
9q8yyj2p   ← driver C, different cell

Proximity search becomes a prefix match, which is exactly what a B-tree or a Redis sorted set is good at:

SELECT * FROM drivers WHERE geohash LIKE '9q8yy%';

You choose the prefix length to match the radius you want:

The border problem

Shared prefix implies proximity. The converse is false, and forgetting that is the classic bug.

Two drivers standing three metres apart on opposite sides of a cell boundary can differ from the very first character of their geohash. Query by prefix alone and the driver across the street is invisible while one at the far corner of your own cell is returned.

That two-stage shape — cheap index lookup to shortlist, exact maths to filter — is how essentially every production geospatial query works.

Geohash has two further quirks worth knowing. Cells are rectangles in latitude/longitude space, so their real-world width shrinks towards the poles: a precision-6 cell in Norway covers far less ground than one at the equator. And precision comes in fixed steps, so you pick between a cell that is somewhat too big and one that is somewhat too small.

QuadTree: let the data choose the cell size

Geohash divides space uniformly, regardless of what is in it. That is wasteful when density varies wildly — and it always does. Manhattan holds more drivers in one square kilometre than a Welsh valley holds in a thousand.

A QuadTree subdivides only where it needs to. Each node owns a square region and holds points directly, up to a capacity. Exceed the capacity and the node splits into four children, pushing its points down.

Level 0            Level 1               Level 2 (dense SW only)
┌─────────┐        ┌────┬────┐           ┌────┬────┐
│         │        │ 30 │ 15 │           │ 10 │  8 │
│  100    │  ───►  ├────┼────┤    ───►   ├────┼────┤
│         │        │ 40 │ 15 │           │ 12 │ 10 │
└─────────┘        └────┴────┘           └────┴────┘

The result is a tree deep where the data is dense and shallow where it is sparse, so every leaf holds a comparable number of points regardless of geography. Empty ocean costs one node.

Querying is a recursive descent that prunes: if a child's square does not intersect your search rectangle, skip its entire subtree unexamined. Typical queries touch a small fraction of the tree.

The costs are real. A QuadTree is an in-memory structure, awkward to persist and to shard across machines. And when a point moves — which, for drivers, is every few seconds — you must remove and reinsert it, potentially collapsing or splitting nodes. Geohash handles movement by writing a new string to a column.

Choosing between them

S2 is Google's library, and it is the one to reach for when polar distortion matters. It projects the sphere onto the six faces of a cube and subdivides those, so cells stay close to equal-area worldwide, and it encodes each cell as a single sortable 64-bit integer — a database-friendly key with much less distortion than a geohash.

Uber's H3 is a separate grid built on hexagons. Hexagons tile without gaps and all six neighbours sit at the same distance from the centre, which suits movement and flow modelling — with squares, diagonal neighbours are further away than edge neighbours, and that asymmetry distorts anything that reasons about travel.

What production systems actually do

Keep the two tiers separate. Slow-moving data — restaurants, shops, homes — sits in the database with an indexed geohash or cell id column, because it is written rarely and read constantly. Fast-moving data — drivers, delivery riders — lives in memory, typically a Redis sorted set scored by geohash, because a position update every few seconds against a disk index is a write storm nobody needs.

And in both cases the index only ever produces candidates. The last step is always exact distance, computed on the handful of rows the index handed back rather than on every row in the table. That is the entire win: a full scan becomes a lookup of nine cells.

Check your understanding

Common mistakes

Querying one cell and calling it a radius search. Neighbours are not optional. Anyone on the far side of a boundary is invisible.

Skipping the exact-distance filter. Nine cells cover a square that over-covers your circle, so raw results include points outside the radius.

Assuming a longer prefix is always better. Higher precision means smaller cells, more boundaries, and more neighbour lookups to cover the same radius.

Ignoring latitude distortion. A precision-6 cell is not the same size in Singapore as in Reykjavik. If uniform area matters, use S2 or H3.

Writing every driver position update to the database. Live locations belong in memory. The disk index is for things that rarely move.

Reaching for a QuadTree because it sounds cleverer. It adapts to density, but it is in-memory, hard to shard, and needs a reinsert on every movement. A geohash column solves most problems.

Practice

Key takeaways

• Distance computed from two columns cannot use an index, so the naive nearest-neighbour query is a full scan.
• Spatial indexing exists to fold two dimensions into one ordered key that an ordinary index can serve.
• Geohash recursively quarters the world into a string; a shared prefix means a shared cell, so proximity search becomes prefix matching.
• Proximity does not imply a shared prefix. Always query the target cell plus its eight neighbours, then filter by exact distance.
• The index produces candidates, not answers — cheap lookup first, precise maths on the shortlist second.
• QuadTrees adapt to density and prune whole subtrees on query, but are in-memory, hard to shard, and need a reinsert whenever a point moves.
• S2 uses near-equal-area spherical cells encoded as sortable 64-bit ids, avoiding geohash's polar distortion; H3 uses hexagons, whose neighbours are all equidistant.
• In production, static places live in an indexed database column and moving objects live in Redis.

Further reading

• Antonin Guttman, "R-Trees: A Dynamic Index Structure for Spatial Searching" (SIGMOD 1984).
• Raphael Finkel and Jon Bentley, "Quad Trees: A Data Structure for Retrieval on Composite Keys" (Acta Informatica, 1974).
• Gustavo Niemeyer, "Geohash" (2008) — the encoding and its properties.
• Hanan Samet, Foundations of Multidimensional and Metric Data Structures (Morgan Kaufmann, 2006) — the comprehensive reference.
• Sean Cribbs and Kevin Sahin, "S2 Geometry" (Google open-source documentation) — spherical cells that avoid the projection distortions of a flat grid.