Geohashing for Proximity Search
Concept
Geohashing encodes a latitude/longitude pair into a single string built on a Z-order (Morton) space-filling curve: recursively bisect the world's bounding box, alternating between longitude and latitude, and append a bit for which half each coordinate falls into. Grouping those bits into 5-bit chunks and mapping each chunk to a base32 character produces a short, human-shareable string like 9q8yy. The core property that makes it useful: points that share a longer prefix are, in general, spatially closer together, because each additional character subdivides the same cell into finer sub-cells. A geohash of length 5 covers roughly a 5×5 km cell; length 7 narrows that to roughly 150×150 m.
That prefix property turns "find things near this point" into a plain string operation: store each record's geohash as an indexed column, and a proximity query becomes a prefix match or a lexicographic range scan — no spatial index extension, no R-tree, no PostGIS required. It's why geohashing shows up as the go-to trick for adding "nearby" search to a system that only has ordinary key-value or relational storage.
Tradeoffs
| Approach | Storage/query mechanism | Cell shape | When it wins |
|---|---|---|---|
| Geohash (base32 Z-order) | Plain string prefix/range query, any KV or SQL store | Rectangular, size varies by latitude — cells shrink near the poles due to the underlying lat/lng projection | Lightweight bucketing, sharding by region, systems without spatial index support |
| H3 (Uber, hexagonal hierarchical index) | Integer cell IDs, purpose-built spatial libraries | Hexagonal, near-uniform cell size and a single distance to all neighbors | Heavier spatial analytics — density heatmaps, ride-matching, anything needing consistent neighbor relationships |
True spatial index (R-tree / PostGIS GIST) |
Native spatial query engine | Exact — no cell approximation at all | Precise polygon/radius queries where geohash's cell approximation error is unacceptable |
Geohash's rectangular grid is the cause of its most-cited weakness (below); H3's hexagons trade away plain string-prefix simplicity for uniform cell geometry, which matters for anything doing spatial aggregation or "k nearest neighbors" work rather than coarse bucketing.
When to use / when not to
- Use for lightweight geo-bucketing: sharding a dataset by rough region, coarse "nearby" filtering before a more precise distance calculation, or adding basic proximity search to a data store with no spatial index support at all.
- Use when the query pattern is naturally prefix-shaped — e.g. "give me everything in this ~1 km cell" maps directly onto a geohash prefix match.
- Avoid for anything requiring uniform-precision neighbor queries or spatial aggregation across a wide area (density maps, dispatch/matching at scale) — H3's uniform hexagons avoid the latitude-dependent cell-size distortion that geohash has.
- Avoid as the sole distance mechanism when precision matters (e.g. "is this point within exactly 500 m") — always verify true distance after a prefix match; the geohash cell is an approximation, not a distance guarantee.
Common pitfall
The boundary problem: two points can sit meters apart but fall on opposite sides of a geohash cell boundary, giving them completely different prefixes despite being geographically adjacent. A geohash-prefix search around a point near a cell edge can miss genuinely nearby records entirely. The standard mitigation is to search the target cell and its 8 neighboring cells (a "geohash neighbor" expansion), not just an exact prefix match — and to always re-verify actual great-circle distance on the candidate set returned, since prefix proximity is only ever an approximation near edges.
Engineering Lens
Geohashing is a good example of trading exactness for a simpler storage/query mechanism — the same tradeoff shows up any time a continuous value (here, a 2D coordinate) gets discretized into buckets to make it indexable by ordinary tools. The lesson generalizes: whenever a system reaches for "encode X as a sortable string so I can use a plain B-tree index," the boundary/edge-effect problem geohash has is going to reappear in some form, and the fix is the same shape every time — search the neighboring buckets too, then verify precisely on the smaller candidate set.
Sources
- Breaking Down Location-Based Algorithms: R-Tree, Geohash, S2, and H3 Explained — Sylvain Tiset
- What is Geohashing? — PubNub