LESSON 25.1
Geohash
Turn latitude and longitude into a short string whose prefixes are nested boxes, so ordinary indexes can answer "what's near here?". Precision, the edge problem, and how to query neighbors.
7 min read
"Show restaurants within 2 km" or "find the nearest available drivers" are range queries in two dimensions. Standard indexes sort along one dimension, so an index on latitude alone returns a thin band around the globe. Geohash maps 2D points onto a 1D key that sorts well, so ordinary databases and key-value stores can answer proximity queries.
Drop a point across a cell edge and compare center-only and neighbour searches.
How it encodes a point
- Start with the whole world: longitude −180 to 180, latitude −90 to 90.
- Split the longitude range in half; write 1 if the point is in the upper half, 0 if lower. Then do the same for latitude.
- Keep alternating longitude and latitude bits, halving the box each time.
- Group the bits into 5s and write each group as a base-32 character.
The result, such as tdr1y for a spot in Bengaluru, names a box. Every prefix names a bigger box containing it: tdr1 contains tdr1y, and tdr contains both. The bit interleaving traces a Z-order curve through space.
- 4 characters
- ~39 km × 20 km
- 5 characters
- ~4.9 km × 4.9 km
- 6 characters
- ~1.2 km × 0.61 km
- 7 characters
- ~153 m × 153 m
- 8 characters
- ~38 m × 19 m
Querying nearby points
Store each point's geohash in an indexed column or as a key. Then:
- Pick a precision whose cells are about the size of the search radius (6 characters for roughly 1 km).
- Compute the geohash of the search center and its 8 neighbors.
- Fetch candidates in those 9 cells with prefix range scans (
WHERE geohash LIKE 'tdr1y%'orBETWEENthe cell's bounds). - Compute the exact distance for each candidate and drop those outside the radius. Sort by distance.
The neighbors are required because of the edge problem: two points 20 m apart on either side of a cell boundary can have very different geohashes. Near the boundaries of big cells (even the equator and prime meridian), prefixes can differ from the first character.
Strengths and weaknesses
Strengths:
- Works with any sorted index or key-value store, with no spatial extension needed.
- Easy to shard by prefix, and simple to compute and debug.
- A good fit for static points: restaurants, stores, listings.
Weaknesses:
- The fixed grid ignores density: a city cell may hold 100,000 points and a desert cell none.
- Cells are rectangles that distort toward the poles.
- Edge effects mean every query needs the neighboring cells.
Very uneven density, or a need for accuracy across the globe, pushes toward quadtrees, S2 or H3.
Moving points
For drivers that report location every few seconds:
- Keep current positions in memory, such as Redis
GEOADD drivers lng lat id, which stores a geohash-derived score in a sorted set, and query withGEOSEARCH ... BYRADIUS 2 km. - Update only when the driver changes cells, or with a TTL so stale drivers vanish.
- Shard by city or region; a single sorted set per city keeps queries local.
Try it
Nearby Places Search HLD
Find nearby places with spatial candidates and exact filtering.