System Design HLD-15.03
Geospatial indexing
Why latitude and longitude indexes struggle with 'find nearby', and how geohashes, quadtrees, S2 and H3 cells turn it into fast cell lookups.
The big idea
A ride-hailing app needs the drivers within 2 km of a rider, right now, out of millions of drivers worldwide. An index on latitude and an index on longitude do not help much: a latitude range covers a thin band around the entire planet, a longitude range covers a band from pole to pole, and the database must intersect two huge sets. Ordinary indexes sort along one dimension, and "nearby" is a two-dimensional question.
Geospatial indexes solve this by dividing the map into cells and giving each cell an id that an ordinary index can handle. A geohashAn encoding of a latitude and longitude into a short string, where each extra character narrows the location to a smaller cell and points sharing a prefix are usually close together. turns a location into a string like gcpuvp where a longer shared prefix means a smaller shared cell. A quadtree splits busy areas into smaller squares. Systems such as S2 and H3 tile the whole globe with hierarchical cells. "Find nearby" becomes "find everything in these few cells, then check exact distances".
Think of postal codes. Instead of comparing everyone's coordinates, a delivery company sorts by postal district, then sub-district. People in the same small district are close together, though two houses across a district boundary can be neighbours with different codes.
How it works
Step 1: Geohash: interleave the bits
A geohash repeatedly halves the world: is the longitude in the east or west half? Then is the latitude in the north or south half? Each answer is one bit, alternating longitude and latitude, and every 5 bits become one base-32 character. Each extra character divides the cell into 32 smaller ones:
- 5 characters: cells of about 5 km
- 6 characters: about 1.2 km by 0.6 km
- 7 characters: about 150 m
Because the string is ordered, a normal B-tree index (or a sorted key-value store) can find all points in a cell with a prefix range scan: WHERE geohash LIKE 'gcpuv%'.
Step 2: The edge problem, and neighbours
Two points 100 meters apart on opposite sides of a cell boundary can have completely different geohashes. So a radius search never looks at one cell only:
- Pick a precision whose cell size is about the search radius.
- Compute the cell containing the query point and its 8 neighbours.
- Fetch all candidates in those 9 cells with prefix scans.
- Filter by exact distance, and sort by it.
Try it
Try this:
- With Big Ben and the London Eye, move precision from 4 to 8. Up to precision 5 they share a cell; at 6 the London Eye, about 450 m away, falls into a neighbouring cell.
- At precision 6, the neighbour check finds it: it is in one of the 8 surrounding cells. At precision 7, cells are about 150 m wide and the London Eye lies beyond the neighbours entirely. The cell size must match the search radius.
- Switch to the two points 110 m apart across the equator. Their geohashes share no characters at all, even at precision 1, yet they are neighbours.
Step 3: Quadtrees: adapt to density
A quadtreeA tree where each node covers a square region and splits into four children when it contains more than a set number of points, so cell size adapts to data density. starts with one square for the whole map and splits any square holding more than, say, 100 points into four. Dense city centers get tiny cells, oceans stay as one big cell. A query walks down to the cells overlapping the search circle. Quadtrees adapt beautifully to uneven density, but they are usually in-memory structures that must be rebuilt or updated as points move.
Step 4: Global cell systems: S2 and H3
Geohash cells are rectangles that get distorted near the poles. Google's S2 projects the Earth onto a cube and numbers cells along a space-filling curve, giving 64-bit cell ids where nearby cells usually have nearby ids. Uber's H3 tiles the globe with hexagons at 16 resolutions. Hexagons have one distance to every neighbour (squares have two: edge and corner), which makes radius approximations and smoothing over neighbouring cells simpler.
Cells also make sharding and aggregation easy: partition location data by coarse cell ( Partitioning and sharding ), count demand per cell, or join datasets on cell id.
Going deeper
Moving objects
Drivers report positions every few seconds. Updating a heavy disk index at that rate is wasteful, so live positions usually go into an in-memory store keyed by cell, such as Redis's geospatial commands (which use geohash-style encoding internally), or into sharded in-memory services. Each update moves the driver from one cell's set to another only when the cell changes. Historical traces go to cheaper storage asynchronously.
Hot cells
Stadiums, airports and city centers concentrate huge numbers of points and queries in a few cells ( Hot partitions and the celebrity problem ). Use finer cells in dense areas (adaptive structures such as quadtrees do this automatically) and cache popular queries.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Lat/long B-tree indexes | Small datasets and rough bounding boxes | Radius queries at scale; two-dimensional ranges |
| Geohash in a sorted store | Simple, works in any key-value store or database | Edge effects (check neighbours) and distorted cells near poles |
| Quadtree | Very uneven density, in-memory nearby search | Rebuilds and rebalancing as points move; harder to distribute |
| S2 or H3 cells | Global coverage, hierarchical aggregation, sharding by cell | Library dependency and learning curve |
| Spatial database (PostGIS R-tree) | Rich geometry queries (polygons, intersections) | Scaling writes for millions of moving objects |
Common mistakes
- Searching only the query point's cell and missing results just across the boundary.
- Choosing a precision far smaller than the search radius, so dozens of cells must be scanned.
- Sorting by cell id and treating it as distance; always finish with an exact distance filter.
- Writing every driver location update to a disk-based index.
- Ignoring hot cells in dense areas.
In the wild
Uber
H3: Uber's hexagonal hierarchical spatial index (opens in a new tab)Uber's 2018 post explains that it built H3 to analyze and optimize its marketplaces, such as setting dynamic prices and making decisions across a city. It chose hexagons because a hexagon has only one distance between its center and its neighbors' centers, compared with two for squares and three for triangles, which simplifies analysis and approximating radiuses. H3 supports sixteen resolutions, each finer cell having about one seventh the area of its parent, though hexagons only approximately nest. The grid is built from 122 base cells laid over an icosahedron projection, with twelve pentagons placed at its vertices.
Check yourself
-
Why are separate latitude and longitude indexes poor for 'find drivers within 2 km'?
Show answer
B. Each one-dimensional range covers a huge band of the globe, so the database must intersect two large sets Nearby is a 2D question; cells turn it into 1D lookups.
-
Two points 100 m apart have geohashes with no common prefix. How is that possible?
Show answer
B. They lie on opposite sides of a cell boundary Prefix sharing implies closeness, but closeness does not imply a shared prefix; check neighbouring cells.
-
What does a quadtree do in a dense city center?
Show answer
B. Splits cells further so each holds a manageable number of points Cell size adapts to density: small cells where there are many points.
-
Why does H3 use hexagons?
Show answer
B. Every neighbour is the same distance from the center, which simplifies radius approximations and smoothing Squares have edge and corner neighbours at different distances; hexagons have one.
Recap
- Ordinary one-dimensional indexes struggle with two-dimensional 'nearby' queries.
- Geohash interleaves latitude and longitude bits into a prefix-searchable string; longer prefixes mean smaller cells.
- Radius searches check the containing cell plus its neighbours, then filter by exact distance.
- Quadtrees adapt cell size to density; S2 and H3 tile the globe with hierarchical cells.
- Keep fast-moving positions in memory keyed by cell, and watch for hot cells.