Engineering Atlas › System Design Fundamentals

Encoding locations with Geohash

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Bit interleaving

Start with longitude in [-180, 180] and latitude in [-90, 90]. Split the longitude range at its midpoint and write 1 if the point is in the upper half, 0 otherwise. Do the same for latitude, and keep alternating, shrinking the range you just used.

Group the bits five at a time and map each group to a character of a 32-symbol alphabet (0-9 and the lowercase letters minus a, i, l, o). Thirty bits become six characters. Gustavo Niemeyer published the string format in 2008 and put it in the public domain; the underlying bit interleaving goes back to G. M. Morton's 1966 IBM report, which is why it is also called a Morton code (Wikipedia). Decoding runs the same process backwards and yields a bounding box, not a point: the centre of that box is the best estimate of the original coordinate.

Precision

Odd lengths give square-ish cells; even lengths give cells twice as wide as tall. At the equator: 4 characters is about 39 km by 20 km, 5 is about 4.9 km square, 6 is 1.2 km by 0.6 km, 7 is about 150 m square, 8 is 38 m by 19 m, and 9 is under 5 m (Elasticsearch geohash grid docs). Cells narrow toward the poles as meridians converge: a cell's east-west width shrinks with the cosine of latitude, so at 60 degrees north it is half its equatorial width.

Why prefixes work, and where they fail

The interleaving traces a Z-order (Morton) curve through the plane. Points close along the curve are close in space, so a prefix scan returns a compact region. The reverse is not true. No curve can fix this completely: a query region always breaks into several runs of the curve, and their number grows with the region's perimeter rather than its area. The Hilbert curve, which S2 uses, needs fewer runs than the Z curve for the same query (Moon et al.). The curve jumps at every cell boundary, and the largest jumps happen on the major dividing lines. A point just east of the prime meridian at the equator starts with s; a point just west starts with e. They share nothing.

The fix is neighbour expansion: pick a precision whose cell is at least as large as the radius, scan the target cell and its 8 neighbours, then filter by true distance. To find a neighbour, decode to a box, step one cell over, and re-encode.

Storage patterns

In SQL, index a geohash column and query a range such as >= 'u4pru' AND < 'u4prv'. Redis GEOADD stores a 52-bit interleaved hash as a sorted-set score, so GEOSEARCH is score-range scans plus a distance filter. GEOSEARCH arrived in Redis 6.2, and GEORADIUS and GEORADIUSBYMEMBER have been deprecated since then, so older tutorials use the old names (Redis docs). MongoDB's legacy 2d index is also a geohash, 26 bits per axis by default, about 60 cm (MongoDB docs). In DynamoDB or Cassandra, a short prefix is the partition key and the full hash the sort key.

Down the stack

Layer 1The contract

Encoding is deterministic and total: every coordinate maps to exactly one cell at each precision, and a hash of length n is a prefix of the hash of length n+1 for the same point. So "shares a prefix" implies "inside the same cell". The converse is not promised. Nearby points may share no prefix, so a correct radius query is the union of the target cell and its neighbours, filtered by real distance. Decoding returns a box with a known error: plus or minus half the cell in each axis.

Layer 2The mechanism

Redis is a good reference. GEOADD interleaves 26 latitude bits and 26 longitude bits into a 52-bit integer and stores it as the score of a sorted-set member. Latitudes beyond plus or minus 85.05112878 degrees, the Web Mercator limits, are rejected with an error, and distances use haversine on a sphere, which Redis warns can be off by up to 0.5 percent (Redis GEOADD). GEOSEARCH picks a step (bits per axis) so the cell is at least as large as the radius, computes the centre cell and its 8 neighbours, and turns each into a score range by shifting the cell's hash left to 52 bits: [hash << shift, (hash + 1) << shift). Each range is a skip-list range scan, and every returned member is checked with the haversine formula. Base32 strings are only a presentation format; the index works on integers.

The step choice has three corrections that a naive implementation misses (geohash_helper.c). Above 66 degrees latitude it uses one step coarser, and above 80 degrees two, because cells are narrower there. It then checks that the four edge neighbours actually reach the query's bounding box and, if not, drops another step. Finally it skips neighbour cells that cannot intersect the box, so many searches scan fewer than nine ranges.

In SQL the same idea is a B-tree on a geohash column, and each cell becomes a key range rather than a LIKE pattern.

Layer 3The machine

Interleaving is a handful of shift-and-mask operations (the classic "spread bits" trick with magic constants such as 0x5555555555555555), a few nanoseconds per point. A 52-bit integer fits exactly in a double's 53-bit mantissa, which is why Redis can store it as a sorted-set score without precision loss (Redis GEOADD) and compare scores with one floating-point instruction.

On disk, consecutive geohashes sit next to each other in B-tree leaf pages. A cell scan is one descent (3 to 4 page reads, usually cached) followed by sequential reads within 8 KB pages, so the 9-cell query costs roughly 9 random page accesses plus sequential reads. Storing the hash as an 8-byte integer instead of a 12-character string fits more keys per page and avoids collation-aware string comparison.

Why it's built this way

  1. Storage engines are built around one-dimensional ordered keys, so two-dimensional locations are folded onto a line.
  2. Bit interleaving is the cheapest fold, but any fold must break locality somewhere, so queries add neighbour cells.
  3. Integer comparisons are cheaper and smaller than string comparisons, so production systems store the bits, not the base32 text.
  4. A double holds 53 bits exactly, so Redis caps the hash at 52 bits, which still gives sub-metre cells.

Diagram

flowchart TD
    A["Point (lat, lon)"] --> B["Halve lon range, emit bit"]
    B --> C["Halve lat range, emit bit"]
    C --> D{"Enough bits?"}
    D -->|no| B
    D -->|yes| E["Group 5 bits, map to base32"]
    E --> F["Geohash string"]
    F --> G["Truncate to search precision"]
    G --> H["Cell + 8 neighbours"]
    H --> I["9 prefix range scans"]
    I --> J["Filter by true distance"]

Worked example

A food-delivery app stores 2 million restaurants and serves "restaurants within 2 km" at 8,000 QPS peak.

At precision 5 a cell is about 4.9 km square, which comfortably covers a 2 km radius when combined with neighbours. The 9-cell window spans roughly 14.7 km by 14.7 km. In a dense city that window might hold 6,000 restaurants; across the whole fleet the average is closer to 400. Precision 6 would give a 3.6 km by 1.8 km window. Its cells are 1.2 km by 0.6 km, both smaller than the 2 km radius, so a user near a cell edge has part of the circle outside the window and misses results.

Each request is 9 range scans on a covering index (geohash, id, lat, lon), roughly 0.5 ms each on a warm cache. At 8,000 QPS that is 72,000 range scans per second, which a pair of read replicas absorbs.

Dense cities are the problem: filtering 6,000 candidates per request in central London costs CPU and network. Use adaptive precision: keep a small table of counts per precision-5 cell and drop to precision 6 for small radii in dense cells.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Geohash in a B-tree or sorted setWorks in any ordered store, easy to shard, human-readableEdge discontinuities, fixed cell sizes, distortion near polesYou need proximity search without a spatial database
QuadtreeAdapts cell size to densityIn-memory structure to build and keep updatedDensity varies wildly and you control the serving tier
PostGIS / R-treeExact geometry, polygons, KNN operatorsTies you to a spatial-capable databaseYou need polygons, routes, or precise containment
S2 or H3 cellsLess distortion, better coverings, uniform neighbours (H3)Library dependency, harder to debug by eyeGlobal scale, analytics, or polygon coverage

Pitfalls in production

Leadership lens

Check yourself

  1. Two shops 20 metres apart have geohashes ezzzzz and spbpbp. Is the encoder broken?

    Show answer

    No. They straddle a major cell boundary, so the Z-order curve puts them far apart in string order even though they are physically close. Neighbour expansion handles this.

  2. Why does an odd-length geohash give a roughly square cell while an even-length one does not?

    Show answer

    Longitude is split first, so after an odd number of characters (5 bits each) longitude has one more bit than latitude, and since longitude spans twice the degrees, the extra halving makes width and height roughly equal.

  3. Why is a geohash range scan a filter and not the final answer?

    Show answer

    The 9-cell window is a rectangle bigger than the search circle, so it returns points outside the radius that must be removed with a true distance check.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →