Data structures · 13 min

Geohash

Build a short code like xn76fg for any spot on Earth, so “ramen near me” becomes “codes that start with xn76fg”, one read on an ordinary database index.

You are standing outside Shibuya Station in Tokyo, hungry. Your app has a table of every ramen shop it knows, each with a latitude and a longitude. You want the ones within a few hundred metres, and you want them in milliseconds.

That sounds like a normal database query. It turns out to be awkward, and the fix is a code you can build by hand in a few minutes. Let’s build it.

Why two indexes on latitude and longitude don’t help much

Your search area is a small box: latitude 35.65 to 35.67 and longitude 139.69 to 139.71, about 2 km across. Put an index on latitude and the database can jump to “latitude 35.65 to 35.67” in one go.

But that range is not a box. It is a thin ring that goes all the way round the planet at that latitude. Every shop on that ring comes back, and the database then checks each one’s longitude and throws most of them away.

An index on longitude has the same problem the other way: a thin slice from pole to pole. A combined index on (latitude, longitude) is like a phone book sorted by surname, then first name. Ask for “surnames Sa to Sm, first name Anna” and you still read every Sa…Sm entry, because the Annas are scattered through them. Here the surname is latitude, so you still read the whole ring.

The real problem: an index sorts one value, and a place is two values. We need to turn the two numbers into one value, where places close together on the map end up close together when sorted.

Cut the world in half, then in half again

Start with the whole map. Draw a line down the middle at longitude 0. Shibuya is east of it, in the right half. Write 1 (left would be 0). Throw away the left half.

Now cut what is left across the middle, at latitude 0. Shibuya is north, in the top half. Write 1 (bottom would be 0).

Keep going, taking turns: left/right, then top/bottom, always cutting the piece you kept. Each answer is one bit, a single 0 or 1. Here are Shibuya Station’s first 5:

Five more cuts give 1, 0, 1, 0, 0 (the demo lets you step through them). After 10 cuts you are left with a box from longitude 135° to 146.25° and latitude 33.75° to 39.375°.

That is roughly a 1,000 km by 600 km rectangle around central Japan. Shibuya is in it, and so is everything else in Tokyo.

The bits are a set of directions: “right, top, right, bottom, …”. Follow them from the whole world and you land in that box. More bits, smaller box.

Five bits make one letter

A long row of 0s and 1s is hard to read and to store, so we group the bits in fives and turn each group into one character.

Shibuya’s first five bits are 11101, which is 29. The second five are 10100: 16 + 4 = 20.

Now look up each number in this 32-character alphabet, counting from 0:

0123456789bcdefghjkmnpqrstuvwxyz

Position 29 is x. Position 20 is n. So the 2-letter geohash for Shibuya Station is xn, and it stands for that 1,000 km box around central Japan.

Keep cutting and you get more letters. Shibuya Station’s 6-letter geohash is xn76fg.

Each letter shrinks the box 32 times

One letter is 5 cuts. Each cut halves the area of the box, so one letter makes the area 2 × 2 × 2 × 2 × 2 = 32 times smaller. Five cuts can’t split evenly between two directions: one letter does 3 left/right cuts and 2 top/bottom, the next does 2 and 3. So width and height shrink by 8 and 4 in turn, and the cells swap between wide and square. The number of letters is called the precision.

The boxes are called cells. Every point inside one cell gets exactly the same code. At 6 letters, the cell xn76fg is a rectangle about 1 km wide and 600 m tall, and Shibuya Station is inside it.

You are standing on a corner just outside the station, at latitude 35.6595, longitude 139.7005, about 190 m from the point we encoded. Your code is xn76fg too.

The payoff: nearby places start the same way

Look at how the code is made. The first letter picks a big box, the second picks a box inside it, and so on. So the code for a small cell always starts with the code of the bigger cell it sits in. xn76f is a cell, and xn76fg is one of the 32 cells inside it.

That means “every shop in my cell” is the same as “every shop whose geohash starts with xn76fg”. Store each shop’s geohash on the shops table at 8 letters (Ramen Sakura is xn76fgck), index that column, and the query is one range scan:

SELECT * FROM shops
WHERE geohash >= 'xn76fg' AND geohash < 'xn76fh'

Two numbers became one sortable value, and the box you care about is one unbroken stretch of the index. That is the whole trick.

There are three ramen shops within 1 km of you. Here are their 6-letter codes:

The catch: the line you can’t see

Your cell’s east edge is at longitude 139.7021, 0.0016° east of you: about 149 m. Haruto Tsukemen is 245 m away, just over that edge, in the next cell, xn76g5. Your code and Haruto’s share only xn76: they split at the fifth letter, even though the shop is a three-minute walk away.

So the rule only works one way. Same start means close. Different start does not mean far. Two places either side of a cell edge can have codes that differ early, because the edge they straddle was drawn by an early cut.

The fix is to search more cells. Take your cell and the 8 cells around it: north, south, east, west and the four corners. Run one range scan for each, 9 in total. Then measure the real distance to each shop you got back and keep the ones that are close enough.

In the demo, those 9 scans find all three shops. Anything outside those 9 cells is on the far side of a whole neighbouring cell, so it is at least one cell’s short side from you: 611 m here.

The whole search

Here is everything above in a few lines. Notice that the database only ever does range scans on a text column; the distance maths runs on a handful of rows at the end.

nearby(you, radius, letters):
    mine = geohash(you, letters)            # e.g. "xn76fg"
    cells = [mine] + neighbours(mine)       # 9 cells
    found = []
    for c in cells:
        found += db.rows_where_geohash_starts_with(c)
    return [s for s in found if distance(you, s) <= radius]

How many letters to use

The 9 cells only guarantee everything within one cell’s short side (the smaller of its width and height). So pick the precision whose short side is at least your search radius.

Try it with the table. For 500 m in Tokyo, 6 letters works: the short side is 611 m. The 9 cells cover about 3 km × 1.8 km, and you filter what comes back by real distance.

For 1 km, 6 letters is too small. You are 236 m below the top edge of your cell, and the cell above is 611 m tall, so a shop 900 m due north sits two cells up and would be missed. That is why the demo, which searches 6-letter cells, only promises shops within 611 m. For 1 km, drop to 5 letters: the 9 cells now cover about 12 km × 15 km, and you filter a lot more rows.

That is the trade: smaller cells mean fewer rows to filter but a smaller safe radius.

You will find geohashes in real systems. Redis stores GEOADD points sorted by their geohash bits, and GEOSEARCH scans your cell plus its 8 neighbours, exactly as above. Elasticsearch can group map points into geohash cells to draw heat maps.