Advanced Topics
Proximity Search
Finding the nearest things to a point — why naive distance scans fail, and the spatial indexing ideas (geohashes, quadtrees, R-trees) that make 'what's near me' fast.
Proximity search answers "what's near this location?" — nearby drivers, restaurants, friends, stores. It shows up constantly (ride-hailing, delivery, dating, maps), and the naive approach falls apart at scale. The problem is that geography is two-dimensional, and ordinary indexes only sort one dimension at a time. Solving it well means indexing space itself.
Why the obvious approach fails
The tempting query is: compute the distance from the user to every point and keep the closest. That's an O(n) scan over your whole dataset on every search — fine for 100 points, hopeless for millions. A bounding-box filter (WHERE lat BETWEEN ... AND lng BETWEEN ...) helps, but a B-tree index on lat and one on lng can't be used together efficiently: the database narrows on latitude, then still scans a long strip of longitudes. You need an index that understands two dimensions at once.
The core idea: turn 2D into something indexable
Every technique below does the same trick — it maps nearby points to nearby index entries, so "find neighbours" becomes "scan a small, local part of the index."
Geohashing. Recursively divide the map into a grid, giving each cell a short string. Crucially, nearby places share a geohash prefix — so proximity becomes a prefix match, which a normal B-tree index handles. Longer prefix = smaller, more precise cell. You find candidates by matching the user's prefix (plus neighbouring cells at the edges), then do exact distance only on that small set. This is simple and works on a plain database — a common, pragmatic choice.
Quadtree. A tree that splits a region into four quadrants, and splits any quadrant that gets too crowded. Dense areas (a city) end up finely divided, sparse areas (an ocean) stay coarse. You descend to the user's cell and read its neighbours. Good when density varies wildly.
R-tree / spatial index. Groups nearby objects into nested bounding rectangles. This is what PostGIS (Postgres's geospatial extension) uses under a GiST index — you get real "within radius" and "k nearest" queries with a single CREATE INDEX, without hand-rolling geohashes.
Picking an approach
| Approach | Reach for |
|---|---|
| Geohash + B-tree | Simple, works on any DB, uniform-ish density |
| Quadtree | Highly variable density (cities vs. countryside) |
| PostGIS (R-tree/GiST) | You're on Postgres and want it to just work |
| Redis geo commands | Fast, in-memory "near me" for moving objects (live drivers) |
For live, constantly-moving objects (drivers), an in-memory geo index (Redis GEOADD/GEOSEARCH) is often the right call — the data churns too fast to keep hammering a disk index.
Don't forget the two-phase shape
Whatever the index, the pattern is: (1) use the spatial index to get a small candidate set near the point, then (2) compute exact distance on just those candidates and sort. The index gets you from millions to dozens; the exact math ranks the dozens.
What to say in an interview
Reject the full scan, name a spatial index, and describe the two-phase query:
"I won't scan every restaurant and compute distance — that's O(n). I'd index locations spatially: on Postgres, PostGIS with a GiST index gives me 'within 2km' directly; otherwise geohashing, where nearby places share a prefix, so a prefix match on a B-tree narrows to a handful of cells. Then I compute exact distance on that small candidate set and sort. For live driver positions I'd use Redis geo commands since they move constantly."
Next up: Time-Series Databases — storing and querying data that only ever moves forward in time.