Geohash

A Point Becomes a String

Geospatial Search: The Problem left us with a spec and two families of answer. Here's the first family's opening move, and it's a genuinely clever one: what if we could turn a location into an ordinary string — arranged so that nearby places have similar strings? Then we wouldn't need a new kind of index at all. The plain B-tree from Container 2, the one that's brilliant at prefixes and ranges, could index locations the same way it indexes words. That's the whole idea of a geohash (invented by Gustavo Niemeyer in 2008), and it's beautiful.

Here's how you build one. Take a point — say the Ferry Building in San Francisco, at latitude 37.77, longitude −122.42 — and play a game of twenty questions with the planet:

Is it in the eastern or western half of the world? (Longitude below 0 or above?) It's west. Write down a 0, and throw away the eastern half — the point lives somewhere in the western hemisphere now.
Is it in the northern or southern half of that? (Latitude above the middle or below?) Write down a bit, and keep the half it's in.
Eastern or western half of the surviving box? Another bit. Northern or southern? Another.

Every question halves the box that could contain the point — alternating a longitude cut and a latitude cut — so the surviving rectangle closes in on the point like a lens focusing. Keep going for 25 questions and the box is down to a few kilometers; keep going for 45 and it's the size of a parking space. The string of yes/no answers is the geohash (we'll turn those bits into friendlier characters in a moment).

And here's the payoff, the thing that makes the whole trick work: two points that are close together give the same answers to the early questions. Same hemisphere, same quadrant, same region — they only start to differ once the box has shrunk down to around their scale. So nearby points share a long prefix, and "find things near me" turns into "find strings that start the same way" — exactly what a B-tree does best. A location became a string, and near in space became near in text.

How a geohash turns a latitude-longitude point into a short string by recursive bisection. On a world map, a point in San Francisco. Step one asks: is it in the eastern or western half of the world? West, so the first bit is 0, and we keep the western half. Step two asks: northern or southern half of that? and emits a latitude bit. The questions alternate — longitude, latitude, longitude, latitude — each one halving the box that could contain the point, so the surviving rectangle shrinks toward the point step by step. The accumulating bits, grouped five at a time, become base-32 characters, and the string grows: 9, then 9q, then 9q8, then 9q8y, then 9q8yy. The magic falls out of this: two points that are close end up asking the same early questions, so they share a long prefix. The bottom line: a location becomes a string, and near in space becomes near in text — which a plain B-tree can already index.

Zipping Two Dimensions Into One

Look closely at those questions and you'll see we're actually building two strings at once — a longitude string (all the east/west answers) and a latitude string (all the north/south answers) — and zipping them together, one bit from each, in turns. Longitude bit, latitude bit, longitude bit, latitude bit. This interleaving is the secret sauce: it's what threads a single one-dimensional order through two-dimensional space so that closeness is mostly preserved. Mathematicians call the path it traces a Z-order (or Morton) curve — it snakes through the grid in little Z shapes, keeping most neighbors near each other along the line.

Raw bits are awkward to store and read, so the last step packs them into text: take the interleaved bits five at a time, read each group as a number from 0 to 31, and map it to a character from a 32-character alphabet (this is base32). Geohash uses 0123456789bcdefghjkmnpqrstuvwxyz — the digits plus the lowercase letters, but with a, i, l, and o removed (they're too easy to confuse with 0, 1, and each other). Five bits per character, so each character carries five of those yes/no cuts.

Run the real algorithm on the Ferry Building (37.7749, −122.4194) and the first ten interleaved bits come out 0100110110, which packs into the geohash 9q8yy… — and character by character, 9 pins it to a slab of the western United States, 9q to Northern California, 9q8 to the Bay Area, 9q8y to San Francisco, 9q8yy to a few blocks near the waterfront. Every character you keep is five more questions answered, and a smaller box. (This is exactly how Redis stores geospatial data internally: it interleaves your latitude and longitude into a single 52-bit geohash integer and sorts on it.)

Every Character Halves the Box (Again)

Because each character is five more binary cuts, each character you add shrinks the cell by about 32×. That gives geohash a lovely property: the length of the string is the precision. Want city-level buckets? Use 5 characters. Want to pin a delivery to a specific building? Use 8. Here's the measured ladder (cell sizes computed from the real bit counts):

geohash    approx cell size          feels like
  1 char     5,009 km                 a slab of a continent
  3 chars    156 × 156 km             a large metro region
  5 chars    4.9 × 4.9 km             a neighborhood
  6 chars    1.2 km × 611 m           a few blocks
  7 chars    153 × 153 m              a building's footprint
  9 chars    5 × 5 m                  a parking space

Two details worth noticing. First, the cells alternate shape: odd-length geohashes are roughly square, while even-length ones are about twice as wide as they are tall. That's not a bug — it's because longitude gets the first bit of each pair, so at even lengths it has received one more cut than latitude. Second, because the whole thing is just string length, you can store one precise geohash per object and query at any coarser precision by truncating — a 9-character hash starts with its own 5-character bucket. One column, many zoom levels. This is why geohash slots so naturally into systems that already speak strings: it's a plain indexed text column in Postgres, the score in a Redis sorted set, the bucket key in an Elasticsearch geohash_grid aggregation. No exotic index required — you're reusing infrastructure you already have.

The geohash precision ladder: every character you add shrinks the cell about thirty-two times. A table with one row per prefix length. One character is a cell roughly 5,000 kilometers on a side — a chunk of a continent. Three characters, about 156 by 156 kilometers — a large metro region. Five characters, about 4.9 by 4.9 kilometers — a neighborhood. Six characters, about 1.2 kilometers by 600 meters — a few blocks. Seven characters, about 153 by 153 meters — a single building's footprint. Nine characters, about 5 by 5 meters — a parking space. The cells alternate shape: odd-length geohashes are roughly square, even-length ones are about twice as wide as they are tall, because longitude receives the extra bit. The bottom line: you pick the precision to match the question — longer prefix, smaller box, more precise 'near.'

"Near" Becomes "Shares a Prefix"

So how do you actually use this to answer "what's near me?" The recipe is short:

Encode the query point to a geohash at a precision whose cell is roughly the size of your search radius — say 6 characters for a ~1 km search.
Prefix-scan that bucket. "Every object whose geohash starts with 9q8yyk" is a plain B-tree range scan (all strings from 9q8yyk to 9q8yyk~). That instantly narrows millions of points down to the handful in that one cell.
Refine. Compute the exact great-circle distance to those few candidates and drop the ones outside your true radius. This is the filter-then-refine pattern from the last lesson: the prefix gives you cheap candidates; haversine gives you the exact answer.

That's the entire pitch for a ride-hailing dispatcher: instead of measuring the distance to a million drivers, you encode the rider to a 6- or 7-character geohash and pull only the drivers sharing that prefix. The search space collapses from everyone to this cell, and it's just a string range query on the database you already run. Redis ships this as GEOADD / GEOSEARCH; Elasticsearch as the geohash_grid aggregation; Groupon famously scaled to millions of geo queries a minute on exactly this with Redis.

Drive it yourself: drop a point and watch its geohash build up bit by bit, slide the precision to grow and shrink the cell, then drop a second point nearby and compare their strings. Something's about to go wrong at the edges — and it's the most important thing to understand about geohash.

Click anywhere to drop a point and watch it turn into a geohash, one question at a time — east or west, north or south — the box halving and the string growing with every character. Slide the precision to trade a longer string for a smaller cell. Then drop a second point right across a cell boundary and watch their geohashes diverge — sometimes sharing nothing at all, even though they're neighbors on the map. Flip on 'check the 8 neighbors' and see the blind spot at the seam close: the nine-cell patch catches the points a bare prefix search would have missed.

The Seam: Why You Always Check the 8 Neighbors

The prefix trick has a sharp edge, and it's the thing interviews and outages both love. A shared prefix always means the points are near — but near does not always mean a shared prefix. The magic is one-directional, and it breaks at cell boundaries.

Here's a real, measured example. Take two points just 3.1 km apart, straddling the prime meridian: one at longitude +0.02°, one at −0.02°. You'd expect near-identical geohashes. Instead you get u000b7q9 and gbpbze33 — they share not a single character. Why so violent? Because the very first longitude question — east or west of 0°? — splits them into opposite halves of the world. On one side the longitude bits run 100000…, on the other 011111…; like an odometer rolling over, every bit flips at the seam. The same thing happens across the equator and across the ±180° antimeridian. Two doors down, opposite ends of the alphabet. (The Z-order curve is what creates these seams; a smarter space-filling curve — the Hilbert curve that Google's S2 uses, later in this section — has fewer of them, but no flat-to-curve mapping erases them entirely. Every grid has edges.)

This isn't a rare corner case — every cell has edges, and any point near one has close neighbors on the far side with a different prefix. Measure it: put a query on a boundary and ask for everything within its cell. A prefix-only search finds just 52% of the genuinely nearby points — it silently misses the other 48%, all the ones sitting across the seam. In a dispatcher, that's the closest driver, invisible, because they parked on the wrong side of an invisible line.

The fix is the standard geohash proximity query, and it's why you'll always see it done this way: scan your cell and its 8 neighbors — the four edges and four corners of the 3×3 block around you. Now any point within a cell's width, on any side of any seam, lands in one of the nine buckets you checked. (The one condition: size the cell to be at least your search radius — pick the precision that way. If your radius is larger than a cell, the 3×3 block isn't enough; you need a wider cover, or a coarser precision.) In the same measurement, adding the neighbors takes recall from 52% straight to 100%. It's nine cheap prefix scans instead of one, feeding the same haversine refine step. Treat a shared prefix as "very likely close"; never treat no shared prefix as "far." Compute the neighbors, then let real distance have the final word.

The geohash boundary problem, drawn on a map straddling the prime meridian. Two points sit just 3.1 kilometers apart, one at longitude plus 0.02 degrees and one at minus 0.02 degrees. Because a major cell boundary — the prime meridian itself — runs between them, their geohashes share not a single character: one is u000b7q9 and the other is gbpbze33. On one side the longitude bits begin 100000, on the other 011111, so every bit flips at the seam. A prefix search anchored on the first point therefore misses the second entirely. Below, the fix: a three-by-three block of nine cells — the query's own cell plus its eight neighbors, four edges and four corners — drawn as a highlighted patch that spans the seam. With the neighbors included, recall jumps from 52 percent to 100 percent. The bottom line: a shared prefix always means near, but near does not always mean a shared prefix, so a real query scans the cell and its eight neighbors and then refines with true distance.

What to Remember

⭐ A geohash turns a 2-D point into a 1-D string by recursively bisecting the world — alternating a longitude cut and a latitude cut, interleaving the bits (a Z-order curve), and packing them into base-32 characters. A location becomes a string; near in space becomes near in text.
⭐ The string length is the precision. Every character is 5 more cuts and a box ~32× smaller: 1 char ≈ 5,000 km, 5 ≈ a neighborhood, 7 ≈ a building, 9 ≈ a parking space. Truncate a long hash to query coarser — one column, many zoom levels.
⭐ "Near" becomes "shares a prefix," so a plain B-tree (or a Redis sorted set, or an Elasticsearch bucket) indexes locations with no special machinery — then filter-then-refine: prefix for candidates, haversine for the truth.
⭐⭐ The boundary problem is the one thing you must not forget. A shared prefix ⇒ near, but near ⇏ shared prefix: two points 3 km apart across a seam can share zero characters. A prefix-only search missed 48% of nearby points in our measurement. Always scan your cell + its 8 neighbors (recall 52% → 100%), then refine.
Geohash's charm is its simplicity — it's just strings, and it runs anywhere. Its limits are the seams and a fixed grid that can't bend to density.

That last limit is the opening for the next idea. Geohash chops the world into a fixed grid, the same everywhere, so a dense downtown cell overflows while an ocean cell sits empty — exactly the density-skew problem from the last lesson, still unsolved. What if the grid could adapt — splitting itself finely where points pile up and staying coarse where they don't? That's the quadtree, and it's next.