What it is
The problem: given a point on the map, find all indexed points within R kilometres. A B-tree can't answer this — indexes are 1D, geography is 2D. The trick is to encode 2D positions into a hierarchical 1D string such that spatially close points share long common prefixes, and then a range query on the prefix returns candidates.
Three encodings dominate the interview: geohash (uniform Z-order grid, simple), quadtree (adaptive splits by density, richer but heavier), and S2 (spherical cells, used by Google, the modern default for anything global). Interviewers score on knowing when each earns its cost.
For a proximity feature I'd start with geohash prefixes at grid size 5 or 6 — good enough for city-scale queries and it fits inside any SQL index. If I needed variable density or true spherical geometry, S2.
The variants and when to pick each
Geohash — the interview default
Interleave the bits of latitude and longitude (mapped into unit intervals), Base32-encode the result. Longer prefix = smaller cell. Precision 5 is ~4.9 km per cell, precision 6 is ~1.2 km, precision 7 is ~150 m. To find candidates within R, query the caller's cell plus the 8 neighbouring cells at a precision level whose cell size is comparable to R.
Cheap to compute (a few CPU cycles), works in any database index (LIKE 'dr5r%'), no library needed. The reason candidates trip: the boundary problem. Two points that are physically close but sit either side of a cell edge share no prefix — you must always query neighbours, not just the caller's cell.
Quadtree — adaptive to density
A tree that recursively splits any cell exceeding a point-count threshold into four children. Manhattan gets many small cells; the Pacific gets one big one. Great for maps and rendering (you draw only cells visible in the viewport), and for range queries in datasets where density varies wildly.
The catch: it's a tree, so inserts and deletes rebalance. Not as easily indexed in a plain SQL column — you either serialise the tree path (like a materialised path) or rely on a tree-supporting store.
S2 cells — the global default
Google's library projects the sphere onto a cube, then uses a Hilbert curve inside each cube face to produce a 64-bit cell ID. Two properties make it beat geohash: near-uniform cell area globally (no polar distortion), and hierarchical composition — you can 'cover' any polygon with a small set of cells whose union approximates it well.
S2 is the right pick when queries are spherical (aviation, global logistics) or when you're indexing regions rather than points (find all users inside this delivery zone).
R-tree — the third option worth naming
An R-tree indexes rectangles (bounding boxes) rather than points, arranged so overlapping-region queries walk down the tree. Native support in PostGIS and other spatial extensions. Great for 'points in polygon' queries where the polygon isn't rectangular.
Use it when the shape of the query matters more than the raw speed of the range read. For pure nearest-neighbour on points, geohash or S2 usually wins on simplicity.
Numbers worth memorising
| Geohash precision 5 | ~4.9 km cell |
| Geohash precision 6 | ~1.2 km cell |
| Geohash precision 7 | ~150 m cell |
| S2 cell level 10 | ~10 km² |
| Query neighbours to check | 8 adjacent + own cell = 9 (geohash), similar for S2 |
Where the interviewer pushes
First push: 'why not just index (lat, lng) and do WHERE lat BETWEEN and lng BETWEEN?' Two problems: the composite index can only leverage the first column (lat), so you scan more than you should; and the query is a bounding box, not a circle, so you over-fetch by ~27% and then have to filter. Geohash makes the index geometry-native.
Second push: 'what precision do I pick?' Match the query radius to the cell size. If your app asks for '5 km around me', precision 5 (~5 km cells) is right; smaller and you query too many neighbours, bigger and you fetch too many candidates. When the radius varies, keep multiple precision columns indexed and route the query at runtime.