Geohashing

The problem: proximity isn’t one-dimensional

In ten minutes you’ll know why a plain (lat, lng) index can’t answer “find things near me,” how geohashing collapses the problem to a string comparison, and where the one sharp edge will bite you if you forget it.

A location is two numbers, latitude and longitude. Databases index one dimension well (a B-tree on a single sorted column), but “find points near me” is inherently 2D: two points can be neighbours while differing in both coordinates, so a B-tree on lat alone, or lng alone, or even a composite (lat, lng), can’t return a compact set of nearby rows — sorting by latitude puts a point in Paris next to a point in Boston (same latitude, opposite sides of an ocean). The goal of a spatial encoding is to map 2D space onto a 1D sortable key such that points close in space are usually close in the key — so a single index range covers a geographic neighbourhood.

How a geohash works: interleaving and Base32

A geohash recursively bisects the world. Longitude spans −180…180 and latitude −90…90. To encode a point you repeatedly halve each range: is the longitude in the lower or upper half? Bit 0 or 1. Then the latitude: lower or upper half? Another bit. You interleave the longitude and latitude bits (lng, lat, lng, lat, …), narrowing the rectangle each time, and the resulting bit string is grouped into 5-bit chunks encoded as Base32 characters. The result is a short string like u4pruyd.

The two properties that make it useful:

• Length = precision. Each extra character shrinks the cell roughly 32× in area. A 5-char geohash is a cell of a few km; 7 chars is ~150 m; 9 chars is a few metres. You pick the length for the precision you need.
• Shared prefix = proximity. Two points in the same cell share the whole geohash; two points in nearby cells usually share a long prefix. So u4pruy* is “everything in this ~150 m cell,” and a database range scan WHERE geohash BETWEEN 'u4pruy' AND 'u4pruz' returns the points in that cell — using an ordinary string index, no special spatial database required.

encode(lat, lng): interleave bits while bisecting each range

lng ∈ [-180,180]: upper half? → 1
lat ∈ [ -90, 90]: upper half? → 0
lng (narrower):   lower half? → 0
lat (narrower):   upper half? → 1
...                            → 10010...  →  Base32  →  "u4pruyd"

prefix length  cell size (approx)
   4 chars        ~40 km
   5 chars        ~5 km
   6 chars        ~1 km
   7 chars        ~150 m
shared prefix length ↑  ⇒  points are closer together

The boundary problem

Here is the trap that bites every geohash-based proximity search. Because the encoding bisects fixed global ranges, adjacent points can fall on opposite sides of a cell boundary and get wildly different codes. Two drivers 10 metres apart, but straddling a cell edge, can share no prefix at all — one is u4pruy…, the other u4prv0… — even though they’re nearly on top of each other. If your “near me” query just selects the rider’s own cell (WHERE geohash LIKE 'u4pruy%'), you will miss the closest driver simply because they’re one metre into the next cell.

The standard fix: a proximity search must query the rider’s cell and its eight neighbouring cells (the 3×3 grid around the point), then compute exact distances within that candidate set and keep the truly-nearest. Computing the eight neighbour geohashes is a known algorithm, and the candidate set is small, so this is cheap — but forgetting it is the single most common geohash bug, and it shows up as “the app says the nearest driver is 800 m away when one is parked across the street.”

Quadtree, S2, and H3: the alternatives

Geohash is one point on a design space; the same “1D key from 2D space” idea has refinements:

• Quadtree. A tree that recursively splits a region into four quadrants, subdividing only where data is dense. Unlike a fixed-grid geohash, it adapts to density — sparse areas stay coarse, hot areas (a city centre) subdivide deeply — which keeps each leaf to a bounded number of points. Geohash is essentially a fixed-depth, string-encoded quadtree.
• S2 (Google). Projects the sphere onto a cube and maps each face with a Hilbert curve. The Hilbert curve has better locality than geohash’s Z-order (fewer wild jumps at seams), and S2 cells are more uniform in area across the globe, avoiding geohash’s distortion near the poles.
• H3 (Uber). A hexagonal grid. Hexagons have a key advantage for proximity: every neighbour is the same distance away (a hexagon has six equidistant neighbours), whereas a square cell’s diagonal neighbours are farther than its edge neighbours — which makes “expand to neighbours” cleaner and distance reasoning more uniform. H3 was built precisely for the ride-hailing “drivers near me” problem.

Together, these three alternatives share the same core insight as geohash — encode 2D space into a 1D key — but each trades simplicity for better locality, uniform cell area, or cleaner neighbour geometry. Without the neighbour expansion step (or a structure that tightens it), you’ll miss close points no matter which scheme you pick.

The tradeoff axis: geohash is dead simple and works on any string index; S2/H3 give better locality, more uniform cells, and cleaner neighbour math at the cost of a library and a more complex cell model. For “store a location and range-scan nearby in Postgres/Redis,” geohash is often enough; for serious geospatial analytics or uniform global indexing, reach for S2 or H3.