In a find-nearby-places service, what is a geohash, and how does it let an ordinary sorted index answer proximity queries?
answer
- one key for two coordinates
- halve the range, record a bit
- interleave, then five bits per character
- sorted keys keep prefixes contiguous
- near in space, not always near in string
basics
~20 sA geohash turns latitude and longitude into one short string by interleaving their bits, so points in the same cell share a prefix. A prefix range scan on an ordinary sorted index then returns every point in that cell.
solid answer
~50 sA geohash repeatedly halves the longitude and latitude ranges, records each half as a bit, interleaves the two bit streams and encodes them five bits per base32 character. Each extra character narrows the cell to one of 32 sub-cells, so a longer string means a smaller cell. I store the geohash as an ordinary indexed column; because the index is sorted, every point inside a cell sits in one contiguous key range, and a query like `WHERE geohash LIKE 'dr5ru%'` becomes a single range scan instead of a full scan. The one caveat I always mention: a shared prefix means the points are near each other, but near points do not always share a prefix. Two places a few metres apart on either side of a cell edge can have completely different strings, so a real nearby query also scans the neighbouring cells and filters candidates by exact distance.
go deeper
Recall the recipe: halve the ranges, interleave the bits, encode five bits per character, and a longer string means a smaller cell. Say that a prefix query is a range scan on a normal index.
Explain why sorting makes a prefix contiguous and why nearness does not guarantee a shared prefix. Mention that cell width in metres shrinks with latitude and that odd and even lengths give different shapes.
Show that you treat the cell scan as a candidate filter only: neighbour cells plus an exact distance check, and one stored precision truncated at query time to serve many radii.
Position the geohash as the cheapest spatial key that any sorted store can serve, then name when its fixed cell size and curve discontinuities justify an adaptive or sphere-aware scheme instead.
## The problem a geohash solves A **proximity query** asks for points near a location: restaurants within 2 km, stores closest to the user. The data is two-dimensional (latitude and longitude), but an ordinary database index, a **B-tree** or any other sorted index, orders rows along **one** dimension. - An index on `latitude` alone narrows the search to a thin band that wraps the entire planet, full of points thousands of kilometres away in longitude. - A second index on `longitude` narrows to a pole-to-pole strip. The engine must intersect two large row sets or scan one of them. - A composite index on `(latitude, longitude)` can only use a range on its first column efficiently; the second range is applied row by row. What we want is a single sortable key where points that are close in space are usually close in key order. A **space-filling curve** gives exactly that, and a **geohash** is a string encoding of one such curve, the **Z-order** (Morton) curve. ## How a geohash is built 1. Start with the full longitude range [-180, 180] and latitude range [-90, 90]. 2. For longitude, check which half contains the point; write `1` for the upper half, `0` for the lower, and keep only that half. Repeat to get more bits. 3. Do the same for latitude. 4. **Interleave** the bits, longitude first: lon, lat, lon, lat, and so on. 5. Group the bits five at a time and map each group to a character from a 32-symbol base32 alphabet (digits and lowercase letters, with a few look-alike letters left out). Every character adds five bits, so it splits the current cell into **32** smaller cells. The string is a path: its first character picks one of 32 huge cells, the next picks a sub-cell inside it, and so on. That is why **a prefix names a larger cell that contains every longer string starting with it**. ## Precision: how big is a cell? Approximate cell sizes at the equator: | Length | Width x height | |---|---| | 1 | 5,000 km x 5,000 km | | 3 | 156 km x 156 km | | 4 | 39.1 km x 19.5 km | | 5 | 4.9 km x 4.9 km | | 6 | 1.2 km x 0.61 km | | 7 | 153 m x 153 m | | 8 | 38 m x 19 m | Two details matter in practice: - **Odd lengths give square cells, even lengths give 2:1 rectangles**, because the longitude range (360 degrees) is twice the latitude range (180 degrees) and odd lengths give longitude one extra bit. - **East-west width shrinks with latitude.** A degree of longitude covers less ground away from the equator (about half as much at 60 degrees), so the same string length names a narrower cell at high latitudes. ## Querying with an ordinary sorted index Store the geohash, at the finest precision you will ever need, as a normal indexed column next to the exact coordinates. Because the index is sorted lexicographically, all keys that start with a given prefix are **contiguous**, so a prefix query is a single range scan: ```sql SELECT id, lat, lng FROM places WHERE geohash LIKE 'dr5ru%'; ``` The prefix `dr5ru` here is illustrative. Truncating the stored value to a shorter prefix at query time lets one column serve any coarser precision. No special spatial engine is needed: a sorted key-value store or a relational table works the same way. ## The boundary caveat The Z-order curve preserves locality **one way only**: - **Shared long prefix implies nearby.** Both points are inside the same small cell. - **Nearby does not imply shared prefix.** Two cafes 20 metres apart on opposite sides of a cell edge can differ from an early character, and across the equator or the prime meridian they may share no prefix at all. That is why a correct nearby query never scans only the query point's own cell. It scans that cell plus its neighbours, then computes the exact great-circle distance for every candidate and discards the ones outside the radius. The cell scan is a cheap **candidate filter**; the distance check is the answer. ## Where it fits A geohash is the simplest spatial key to explain and to deploy: it is just a string column, it shards and caches like any other key, and prefixes double as a natural aggregation unit (count places per 5-character cell). Its weaknesses, uneven cell shapes by latitude, locality jumps along the curve and fixed cell sizes regardless of density, are what motivate quadtrees and other cell systems. For a first answer in an interview, the expected points are: bits interleaved, base32 characters, longer means smaller, prefix equals range scan, and neighbours plus exact distance filtering to handle edges.
- Why do two separate indexes on latitude and longitude perform poorly for a nearby search?Each index narrows only one dimension. A latitude range is a band around the whole planet and a longitude range is a pole-to-pole strip, so each returns far more rows than the answer. The engine must intersect two large sets or scan one band and filter. A single key that mixes both dimensions, such as a geohash, turns the search into one narrow range scan.
- Why are geohash cells square at some string lengths and 2:1 rectangles at others?Bits alternate starting with longitude, and each character adds five of them. At odd lengths longitude gets one more bit than latitude, which cancels its range being twice as wide (360 vs 180 degrees), so cells are square at the equator. At even lengths both get the same number of bits, so each cell spans twice as many degrees east-west as north-south.
A geohash works like a postal code that gets more specific with every extra digit: the same leading digits mean the same district. Two houses facing each other across a district line still get different codes.
saying these in an interview costs you the question
- A geohash is a cryptographic hash of the coordinates
- Two separate indexes on latitude and longitude answer radius queries efficiently
- Points that are close together always share a long geohash prefix
- A geohash cell has the same size in metres everywhere on Earth
- Points matching the prefix are already the exact radius result