Start here: the problem it solves#
TL;DRthe 30-second version
- A geohash turns a (latitude, longitude) point into a short base32 string, so that nearby points share a long leading prefix.
- You build it by halving each coordinate range one bit at a time, interleaving the longitude and latitude bits, and reading every five bits as one base32 character.
- Each character shrinks the cell by about 32 times: 5 characters ≈ 4.9 km, 6 ≈ 1.2 km, 7 ≈ 150 m, 8 ≈ 38 m.
- The catch: two points close together but on opposite sides of a cell edge share almost no prefix. So a real proximity query checks the cell plus its 8 neighbours.
You are building the back end for a maps app. A user is standing somewhere, and you want to answer one question fast: which of the million restaurants in your database are within two kilometres of them?
The obvious approach is to scan the table. For each restaurant, compute the distance to the user, and keep the ones under two kilometres. That is a million distance calculations for a single query, and it repeats on every map pan. At any real traffic it falls over.
The usual fix is an index, but the standard index does not help here. A B-tree can find every restaurant with latitude between two values, and separately every one with longitude between two values. It cannot find the ones that satisfy both at once without pulling a long strip of the map and filtering it. Two one-dimensional indexes do not make a two-dimensional one. We want one value per point that keeps nearness, so an ordinary sorted index can answer the question.
The mechanism: interleave the bits, then base32#
Start with longitude, which runs from -180 to 180. Ask one question: is the point in the eastern half or the western half? Write 1 for east, 0 for west. Now split the half you kept at its own midpoint and ask again. Each question is one bit, and each bit halves the range that is left. This is binary search on the coordinate, and two points near each other take the same turns for a long time, so their bit strings share a long prefix.
One coordinate only pins the point to a strip of the map. So run the same halving on latitude too, from -90 to 90, and take turns between the two. Longitude goes first, by convention. Every five bits, read them as a number from 0 to 31 and map it to a base32 character.
The first ten bits of a point in San Francisco (37.77, -122.42), longitude in the top row, latitude in the bottom
The alphabet is a specific base32: the digits 0 through 9 and the letters b through z, with a, i, l and o left out so no two characters are easy to confuse. Each character is five more halvings, so each one shrinks the cell about 32 times. A six-character geohash has 30 bits, 15 per coordinate, which is a cell about 1.2 km wide and 0.6 km tall at the equator. Gustavo Niemeyer built it in 2008 for the geohash.org URL shortener.
Now the payoff. A second point a kilometre away in San Francisco takes the same turns for a long time and comes out as "9q8yym". It agrees with "9q8yyk" on the first five characters. New York, at 40.71, -74.01, diverges on an early longitude bit and comes out as "dr5reg", sharing nothing. So store each point's geohash in an ordinary sorted index, and "near me" is a prefix scan for the user's own geohash prefix.
PredictYou shorten every stored geohash from 6 characters to 5 before indexing. What happens to a "near me" prefix search?
Hint: Fewer characters means a larger cell. Think about how many points now share each prefix.
A 5-character prefix is a cell about 4.9 km across instead of 1.2 km, so many more points share each prefix. The search returns more candidates, including some farther away than you wanted, which you then filter by true distance. The precision you index at has to match the radius you query.
There is one sharp edge. Two points can be 60 metres apart and still share only three characters, if a cell boundary runs between them. They took different turns at the bit where that boundary was decided, and their strings diverge from there. A shared prefix means close, but close does not guarantee a shared prefix.
Cost and precision#
Encoding is cheap and fixed. An n-character geohash is 5n halvings, each a comparison and an assignment, so it is O(n) with a tiny constant. There is no tree to walk and no structure to keep in memory.
- The geohash is its own index key, usually 5 to 12 characters.
- Precision is set by length: 5 chars ≈ 4.9 km, 6 ≈ 1.2 by 0.6 km, 7 ≈ 150 m, 8 ≈ 38 by 19 m, 9 ≈ 5 m. Redis keeps 52 bits, which pins a point to roughly 0.6 m at the equator.
- A near-me query is 9 prefix scans (the cell plus 8 neighbours) and a true-distance filter, instead of a full-table distance scan.
- Cells are rectangles in latitude and longitude, not squares on the ground. A degree of longitude shrinks toward the poles, so the same length covers less ground the farther you are from the equator.
If this comes up in an interview#
Does a shared prefix guarantee two points are close?
A long shared prefix means they fall in the same cell at that precision, so yes. The reverse is not guaranteed: two close points on opposite sides of a cell edge can share almost no prefix. That is why a proximity search checks the cell plus its 8 neighbours rather than trusting a single prefix.
How do I pick the precision?
Match the cell size to your search radius. For things within a kilometre, index at 6 characters (about 1.2 km) so a cell is close to the radius, then query that cell and its 8 neighbours. Too short a prefix returns too many candidates. Too long makes a cell smaller than your radius, so you would have to stitch together many cells to cover it.
When would you not use a geohash?
When you need equal-area cells at global scale, use S2, which numbers cells along a Hilbert curve with no long jumps. When you need evenly spaced neighbours, use H3, which tiles the world with hexagons. When point density varies wildly, a quadtree refines only where the data is. Geohash wins when you want a plain string you can index anywhere and share in a URL.
Strengths, limits, and the alternatives
- It is simple and portable. The key is a short string that indexes in any ordinary database and shares in a URL. This is the whole reason to use it.
- Prefix means proximity, mostly. It is one-way: close points usually share a prefix, but points across a boundary may not, so you must query the 8 neighbours. Redis GEOSEARCH does exactly this, scanning the score ranges of the target cell and its neighbours.
- Precision is quantised to characters: 4.9 km, then 1.2 km, then 150 m. If your radius sits between two levels you either over-fetch at the coarser level or stitch neighbours at the finer one.
- Cells are not equal-area and not square, so a fixed length means different physical precision in different places.
- Under the hood, interleaving traces a Z-order (Morton) curve across the map. It mostly keeps neighbours together, but at the edges of its big zig-zags it jumps, and those jumps are where close points get different prefixes.
| Geohash | Quadtree | S2 | H3 | |
|---|---|---|---|---|
| Key | base32 string | tree path | 64-bit id (Hilbert) | 64-bit id (hex) |
| Cell shape | lat/lng rectangle | square | near-equal-area quad | hexagon |
| Adapts to density? | no, fixed grid | yes | no | no |
| Prefix = proximity? | yes, with edge gaps | path prefix, edge gaps | smoother (Hilbert) | by resolution |
| Neighbours | 8, unequal | 8, unequal | 8, unequal | 6, equal |
| Best when | simple, portable keys | clustered data | global, equal-area | uniform movement |
A lot of systems use more than one: a geohash for the human-facing short link, and S2 or H3 underneath for the heavy indexing. Elasticsearch's geohash_grid aggregation buckets documents by prefix at a chosen precision, which is how map tools draw heat maps: zooming in just lengthens the prefix.
References
- Geohash — Wikipedia — the algorithm, the base32 alphabet, the precision table, and the worked example
- Redis — GEOADD / GEOSEARCH and the geospatial index — stores a 52-bit interleaved geohash as a sorted-set score; radius search scans a cell and its neighbours
- Google S2 — S2 Geometry library — the Hilbert-curve, near-equal-area alternative
- Uber H3 — hexagonal hierarchical spatial index — the hexagon alternative with uniform neighbour distance