Geohash explained: an interactive nearby-search map

A geohash turns a latitude and longitude into a short string such as 9q8yzt by halving the map again and again and writing down which half the point is in. Every extra character makes the cell 32 times smaller, and places in the same cell share a prefix, so a database can find nearby places with an ordinary index on a text column: look up your cell and its eight neighbours, then check the exact distance.

The playground is a 6.7 km square of a city with 900 places in it. Tap anywhere to search from there, change the precision and the radius, and see which cells are read, what is found and what is missed.

How geohash encoding works

1. Halve the longitude range, from −180 to 180: write 1 if the point is in the east half, 0 if in the west, and keep that half.
2. Halve the latitude range the same way: 1 for north, 0 for south.
3. Alternate, longitude then latitude, for as many bits as you need.
4. Spell every 5 bits as one character from the base-32 alphabet 0123456789bcdefghjkmnpqrstuvwxyz, which leaves out a, i, l and o.

Because each character only narrows the one before it, a longer geohash is always inside its prefixes: 9q8yzt is one of the 32 cells inside 9q8yz. Cell sizes at the equator, where they are widest:

Cells get narrower towards the poles: in the playground, at about 38° north, a 6-character cell is 966 m by 607 m.

Finding nearby places with a geohash

Store each place’s geohash in an indexed column. To find places within a radius, compute the geohash of the search point at a precision whose cells are at least as large as the radius, read that cell and its eight neighbours, and keep only the places within the radius by exact distance. The eight neighbours are not optional: a point near the edge of its cell has close neighbours in the next cell. In the first preset, the nine cells hold 166 of the 900 places, and 30 of them are within 500 m.

The edge problem: close places, different prefixes

Places that share a long prefix are close, but close places do not always share a long prefix. Across the edge of a large cell the hashes differ early: in the second preset the search point is a couple of hundred metres from the corner where four 4-character cells meet, and its nine cells start with 9q8y, 9q8z, 9q9n and 9q9p. They share only 9q, so querying the prefix of your own cell, or of its parent, would miss places a short walk away. Query the nine cells by name instead.

Choosing the precision

If the cells are smaller than the radius, the nine cells do not cover the circle: in the third preset, 7-character cells about 120 by 150 m and a 1 km radius find 5 places and miss 105. If the cells are much larger than the radius, every search reads far more than it needs: in the fourth preset, 5-character cells and a 250 m radius read all 900 places to find 6. Pick the longest geohash whose cell’s short side is still at least the radius, or read extra rings of cells around yours when the radius is larger.

Geohash vs quadtrees, S2 and H3

A geohash cuts the world into a fixed grid, which is simple to store and shard but treats a dense city and an empty desert alike. A quadtree splits only where there are many points, so every leaf holds a similar number. Google’s S2 maps the sphere onto the faces of a cube and orders cells along a Hilbert curve, which keeps neighbouring cells closer together in the ordering and distorts less near the poles; Uber’s H3 uses hexagons, whose six neighbours are all the same distance away. Redis stores GEO positions as 52-bit geohashes in a sorted set, and Elasticsearch can aggregate points by geohash cell.

Geohash in code

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"   # no a, i, l or o

def geohash(lat, lon, precision=6):
    lat_range, lon_range = [-90.0, 90.0], [-180.0, 180.0]
    out, bits, value, use_lon = "", 0, 0, True
    while len(out) < precision:
        rng, x = (lon_range, lon) if use_lon else (lat_range, lat)
        mid = (rng[0] + rng[1]) / 2
        if x >= mid:
            value, rng[0] = value * 2 + 1, mid     # upper half: a 1
        else:
            value, rng[1] = value * 2, mid         # lower half: a 0
        use_lon, bits = not use_lon, bits + 1
        if bits == 5:                              # every 5 bits is one character
            out, bits, value = out + BASE32[value], 0, 0
    return out

# nearby search: your cell and its 8 neighbours, then the exact distance
# SELECT * FROM places WHERE geohash6 IN (:cell, :n, :ne, :e, :se, :s, :sw, :w, :nw)
# and keep the rows within the radius

In a system design interview

For “find restaurants near me”, say the precision and why: “Each business stores a 6-character geohash, about a kilometre by 600 metres here, in an indexed column. A search for 500 m computes the user’s cell, reads it and its eight neighbours, filters by exact distance and ranks the rest. Businesses barely move, so the index is read-heavy and caches well.” Expect the follow-ups: the edge problem, a radius that changes with the zoom level, dense areas where one cell holds too much (a longer geohash, or a quadtree), and moving objects such as drivers, whose cell changes as they move.

Read geohash vs quadtree vs H3, or watch a strong candidate design Yelp, where the nearby search is the heart of the design.

Questions people ask