Cutting the world in half, repeatedly
Geohash builds that single ordered key by cutting the world in half over and over.
Start with the whole planet. Ask whether your longitude falls in the eastern or western half, and write down a 1 or a 0. Ask the same of latitude, north or south, and write another. Keep alternating, each bit halving the remaining box on one axis, and your growing string of bits describes a shrinking rectangle. Encode the bits five at a time and you get the familiar string. Trafalgar Square is gcpvj0.
Watch the useful property fall straight out of that construction. Two places inside the same box agreed on every bit that led there, so they share a prefix.
The longer the prefix they share, the smaller the box, and so the closer together they are. Nearness in space has become prefix length in a string, and matching prefixes is exactly what a B-tree does well. Everything starting with gcpvj is one index range scan.
Prefix length is your radius dial
Treat prefix length as your radius dial, and memorise the numbers, because interviewers ask for them. Four characters is a box about 20 kilometres across, five is 2.4 kilometres, six is 610 metres, seven is 76 metres, eight is 19.
Pick the length whose box comfortably exceeds the radius you are searching, because a box smaller than your radius cannot possibly hold all the answers.
One detail people miss. The boxes are neither square nor equal. Lines of longitude converge towards the poles, so a box in Oslo is noticeably narrower than the same-length box in Nairobi. For city-scale search this never matters. For anything spanning high latitudes, measure rather than assume.
Worked example
Kenji indexes 12 million Japanese restaurant records for a nearby search with a 1 km radius. He picks 6-character geohashes, since a 610 m cell is the largest that fits comfortably inside 1 km, and stores the string in a plain B-tree column. A lookup near Shibuya Station computes the user's geohash xn76fg, does a prefix range scan, and gets back about 900 candidates instead of the 61,000 the latitude-band approach was returning. Haversine distance then sorts and trims those 900 to the 140 genuinely within 1 km. Total query time 11 ms, and because it is an ordinary string column, the whole thing works on the Postgres instance he already had, with no extension and no new service.