Geohash

Why it matters

"Show me drivers near me" is a two-dimensional range query, and a normal B-tree index is one-dimensional: indexing latitude alone returns a horizontal band spanning the whole world. Geohash flattens two dimensions into one string so that an ordinary sorted index, a key-value store or a plain WHERE prefix LIKE can answer nearby queries. It is the simplest geospatial index and the one most interviewers expect you to reach for first.

The idea

A geohash encodes a latitude and longitude as a base-32 string by repeatedly halving the world. Longitude bits and latitude bits are interleaved: the first bit says west or east half, the second says south or north half, the third splits the chosen longitude half again, and so on. Every five bits become one character. The result has a key property: a geohash is a rectangular cell, and any string with it as a prefix is a sub-cell inside it. Longer hash, smaller cell.

Answering "within 2 km"

1. 1

   Pick a precision whose cell is about the search radius

   For 2 km, 6 characters (about 1.2 km × 0.6 km cells) or 5 characters depending on density.
2. 2

   Compute the user's cell and its eight neighbours

   Points just across a cell edge are nearby but have a different prefix, so always include neighbouring cells; libraries compute them directly.
3. 3

   Fetch candidates by prefix

   Nine prefix lookups against a sorted index: a B-tree on the geohash column, a Redis sorted set with lexicographic ranges, or a key-value store keyed by cell.
4. 4

   Filter by true distance

   Cells are rectangles, radii are circles; compute the haversine distance for each candidate and keep those within 2 km, then sort.

Storing moving objects

For drivers updating every few seconds, store the current cell per driver and maintain a set of driver ids per cell: on each update, remove from the old cell and add to the new one. Redis GEO commands implement exactly this with a sorted set keyed by a 52-bit geohash score, with GEORADIUS and GEOSEARCH doing the neighbour-cell expansion and distance filtering for you. Expire stale entries with a TTL so offline drivers disappear.

Edge cases and limits

Cells are not squares and their size varies with latitude, so precision choice is approximate. Nearby points across a boundary share no prefix (hence the neighbour step), and at the 180th meridian and the poles the neighbour logic needs care. Cells are uneven in population: a precision that is right for suburbs is too coarse for a dense city centre, where you drop to a finer level or switch to an adaptive structure such as a quad tree, next lesson. Geohash answers proximity of points; polygons, routing and shapes need other tools.

Trade-offs

Geohash buys a geospatial index out of any sorted store with one string column and simple prefix queries, and pays with boundary handling, uneven cell sizes and density, and poor support for shapes. For "points near a point" at city scale it is the fastest thing to build and explain; for adaptive density or polygon queries, quad trees, R-trees and hierarchical grids take over.

In an interview

State it with the neighbour step included: "Drivers are indexed by 6-character geohash in a Redis sorted set; a rider query takes their cell plus the eight neighbours, fetches candidates and filters by haversine distance. Updates move the driver between cells, with a TTL for stale entries. Dense downtown areas use a finer precision." The neighbour cells and the final distance filter are what distinguish a correct answer from a hand-wave.