Geospatial Indexinglesson 4 of 4 · 3 min read

Quadtrees and Hexagons

A fixed grid on an uneven world

Geohash boxes form a fixed grid, and the world you are indexing is not uniformly full.

A 610 metre box over the North Sea holds nothing. The same box over central Tokyo holds thousands of businesses. One grid size cannot serve both, so a fixed scheme is always too coarse somewhere and too fine somewhere else at the same time.

A quadtree adapts instead. Start with one box covering everything, and one rule: if a box holds more than a set number of points, split it into 4 and push the points down.

Your recursion stops where the density stops, so ocean stays a single shallow node while Tokyo subdivides a dozen levels deep. Every leaf holds at most that number of points by construction, and that is the property you came for. A nearby query drops to the user's leaf and its neighbours and reads a bounded number of points, whether they are standing in Tokyo or Wyoming.

That costs something, because a quadtree is a built structure. It has to live in memory, be rebuilt as points move, and be shared across your servers, all of it real operational weight that a string column simply does not have.

What the large systems use

Look at what the large systems converged on, because you can borrow it. S2, from Google, projects the sphere onto the six faces of a cube and runs a space-filling curve through each one. That keeps neighbours together better than plain bit interleaving, and avoids the worst distortion near the poles.

H3, from Uber, tiles the world with hexagons instead, and the reason is neighbour distance. A square box has 8 neighbours sitting at two different distances: the ones sharing an edge, and the ones sharing only a corner. Any calculation across neighbours comes out subtly lopsided. A hexagon has exactly 6 neighbours, all the same distance away, which makes smoothing and flow calculations behave.

Choose by weight rather than fashion. Geohash is a string column with no dependency to install, and it carries most products further than people expect. Quadtrees earn their complexity when density varies wildly and your points keep moving. Hexagons earn theirs when you calculate over neighbourhoods rather than merely searching them. That is exactly the surge pricing problem Uber built them for.

the shape of it

step 1 of 3

A quadtree spends its depth where the points are, so every leaf holds a bounded number of them.

Worked example

Uber's early dispatch used a geohash grid and hit the density problem in exactly the way the theory predicts: cells sized for suburban Phoenix held single-digit driver counts, while the same cell size over Manhattan at 6pm held thousands, so the two ends of the system needed opposite tuning. Worse, surge pricing averages supply and demand across a cell and its surroundings, and with square cells the 4 edge neighbours sit closer than the 4 corner neighbours, so the same set of drivers produced different surge depending on which way the block was oriented. H3's hexagons fixed the second problem by construction, since all 6 neighbours are equidistant, and its 16 resolutions fixed the first by letting the city pick resolution 9 (about 0.1 square km) where Phoenix picks resolution 7 (about 5 square km). Uber open-sourced H3 in 2018 and Foursquare and others adopted it for the same reasons.

Geospatial Indexing: wrapping up

In the real world

01Redis ships geospatial commands built directly on geohash: GEOADD stores a point as a 52-bit score in a sorted set and GEOSEARCH does the neighbour expansion for you. It is the fastest route from nothing to working proximity search, and holds up to a few million points.
02PostGIS gives Postgres a GiST index over an R-tree, which indexes real bounding boxes rather than grid cells and so handles polygons and lines, not just points. If you need "inside this delivery zone" as well as "within 2 km", this is the answer rather than geohash.
03Uber built H3 because surge pricing averages over neighbouring cells, and square grids make neighbours unequal distances apart. Hexagons give 6 equidistant neighbours, which is a property about arithmetic, not aesthetics.
04Elasticsearch geo_point fields index using a BKD tree and expose geo_distance queries, which is how many search-first products get proximity without adding a second datastore.
05MongoDB 2dsphere indexes store S2 cell ids, so $near queries are cell lookups with the same 9-cell expansion happening below the API.

Questions people ask

Do I need PostGIS, or is a geohash column enough?

A geohash string column plus a 9-cell query and a Haversine filter handles point-radius search to several million rows with no extension and no new service. Reach for PostGIS when you need shapes rather than points: polygon containment for delivery zones, line distance for routes, or genuine spherical accuracy at high latitudes.

How do I choose the geohash precision?

Pick the shortest length whose cell still exceeds your search radius, so the 3 by 3 block is guaranteed to cover the whole circle. For a 1 km radius that is 6 characters at 610 m. If your radius varies per query, store several prefix lengths as separate columns and pick at query time rather than recomputing.

Why does everyone still run a distance calculation at the end?

Cells are rectangles and a radius is a circle, so a cell query returns a superset that includes corners outside the radius. The index exists to make the candidate set small, not to be correct on its own. Haversine over a few hundred candidates costs microseconds and is what makes the answer exact.

Quick review

The core problem:: a B-tree orders one dimension. Coordinates are two, and separate indexes on lat and lon still leave a huge intersection to filter
Geohash:: interleave the bits of latitude and longitude, then base32 encode. A shared prefix means physically close, so proximity search becomes a prefix scan
Precision by length:: 4 characters is roughly a 20 km cell, 5 is 2.4 km, 6 is 610 m, 7 is 76 m. Pick the length that brackets your search radius
Boundary problem:: two points either side of a cell edge share no prefix. Query the cell plus its 8 neighbours, then filter by true distance
Quadtree:: split a region into 4 quadrants recursively until each leaf holds fewer than K points. Depth follows density, so Manhattan subdivides far deeper than Wyoming
S2 (Google) and H3 (Uber):: the production alternatives. S2 walks a Hilbert curve over a sphere projection, H3 uses hexagons so all 6 neighbours sit at equal distance
Redis GEO:: GEOADD and GEOSEARCH are geohash on a sorted set. Fine to a few million points before a dedicated index earns its keep
The index narrows, it does not answer:: cell lookup returns candidates, then Haversine distance sorts and trims to the real radius

the trade-off

You trade exact answers for cheap candidate sets, so every query pays for a second distance pass. Cell size is a bet on the search radius: too coarse and you scan thousands of extra rows, too fine and you union dozens of cells per query. Dense cities hotspot badly, because one cell over Manhattan can hold more rows than an entire rural state.

in the room

Any "find X near me" feature: ride-hailing, food delivery, store locators, dating apps, geofence alerts.

the short version

Fixed grids waste space on empty land and choke on dense cities.