Geocoding: Under the Hood

Geocoding and reverse geocoding databases contain hundreds of millions of records - every street, building, landmark, and administrative boundary on the planet. Answering a query like "What address is at 48.8584, 2.2945?" in under 50 ms requires more than a text index. The engine needs to efficiently narrow down candidates in geographic space before any name matching happens.

This page explains how hexagonal spatial indexing solves that problem.

The problem with a full scan

A naïve approach - scan all records and compute the distance from the query coordinate to each one - doesn't scale. At 500 million records and 10 nanoseconds per comparison, a full scan takes 5 seconds. Not acceptable for a real-time API.

The solution is a spatial index: a data structure that organises records by location so the engine can discard large swaths of the planet without examining them. The most common approach in modern location services is a hierarchical grid - divide the world into cells, group records by cell, and at query time only look at records in nearby cells.

Why hexagons?

Grids can use squares, triangles, or hexagons. Hexagons have two properties that make them uniquely suited for proximity-based search:

• All six neighbours are equidistant. In a square grid, the four edge neighbours are 1× the cell size away, but the four corner neighbours are √2 ≈ 1.41× away. This means "cells within distance D" is an octagon, not a circle - the approximation is poor. In a hexagonal grid, all six neighbours are exactly 1× the cell size away, so "cells within distance D" is a close approximation of a circle.
• Best area-to-perimeter ratio. Hexagons have the highest ratio of any regular tessellation. This means less perimeter (fewer edge effects and border queries) per unit of covered area.

The practical result: for a query "find all addresses within 500 m of this point", a hexagonal grid returns a cleaner candidate set with fewer false positives than a square grid.

H3: hierarchical hexagonal indexing

H3 is an open-source spatial indexing system created by Uber and released in 2018. It divides the entire planet into hexagonal cells at 16 resolution levels (0 = planet-scale, 15 = sub-meter). Each cell at resolution N is entirely contained within exactly one cell at resolution N−1, and contains approximately 7 children at resolution N+1.

The hierarchy matters for performance. Instead of storing one massive flat index, the system maintains multiple resolution levels. A query at "city scale" only needs to check resolution 6 cells (~1.2 km²). A query at "building scale" drills down to resolution 10 (~15,000 m²). Most of the planet's cells are never loaded.

The lookup algorithm

Converting a coordinate (lat, lon) to an H3 cell index is a pure mathematical operation - it applies a series of trigonometric transformations that map the sphere to a planar hexagonal grid. No database lookup is involved. The computation takes microseconds.

The resulting integer (the H3 cell index) encodes both the resolution and the cell's position in the hierarchy. You can extract the parent cell at any coarser resolution with a single bitwise operation - which enables fast range queries: "find all records within 3 hexagonal rings of this cell at resolution 8."

Resolution and accuracy

A single geocoding query typically touches 2–3 resolution levels - starting coarse to eliminate most of the planet, then drilling down to find the closest match.

Further reading

• H3 official documentation
• Uber Engineering: H3 - Uber's Hexagonal Hierarchical Spatial Index
• Geocoding API guide - how this indexing translates to query parameters and response fields