Geospatial indexing and proximity search

Geohash, S2 and quadtrees, nearest-neighbour and radius queries, indexing moving objects, map tiles, and the accuracy and hot-cell problems that come with each.

"Find things near me" appears in ride sharing, delivery, dating, maps and store locators. A two-dimensional problem has to be forced into a one-dimensional index, and every technique for doing that is a different compromise between precision, query cost and hot-spot behaviour.

Why a B-tree is not enough

WHERE lat BETWEEN … AND lng BETWEEN … uses one index column well and the other badly: the database scans a stripe of the planet and filters. It works at small scale and falls over when the table is large or the write rate is high. The fix is a spatial index that maps 2D to 1D while preserving locality.

The three encodings

Geohash. Interleave the bits of latitude and longitude, base-32 the result: 9q8yyk8ytp. Each extra character refines the cell. Neighbouring points usually share a prefix, so a range scan on the prefix is a proximity query and any key-value store can be the index.

The catch: points either side of a cell boundary can be metres apart with completely different prefixes, so any correct query must also read the eight neighbouring cells. Cell size also varies with latitude.

S2. Projects the sphere onto the six faces of a cube, fills each face with a Hilbert curve, and yields 64-bit cell ids at 30 levels. Cells are much more uniform in area than geohash cells, the Hilbert curve preserves locality better, and a region can be covered by a compact set of mixed-level cells. This is what Google and Uber-style systems use; naming it and saying why (uniform cells, region covering) is a strong signal.

Quadtree. Recursively subdivide a square until each leaf holds at most k points. The tree adapts to density — Manhattan is deep, the ocean is shallow — which is exactly what geohash and S2 do not do on their own. The cost is a mutable tree structure that is harder to shard and rebalance than a flat key.

PostGIS / R-tree. A real spatial index with polygons, ST_DWithin and true distance operators. The right answer when the data fits one database and the shapes matter (service areas, delivery zones, geofences).

Radius and nearest-neighbour queries

The recipe for "the 20 nearest drivers within 3 km":

1. Choose a cell level whose size is close to the search radius.
2. Compute the covering cells: the point's cell plus its neighbours (or an S2 region covering).
3. Fetch candidates from those cells — this is a set of key-range reads, and they parallelise.
4. Compute true distances (haversine) on the candidates and sort.
5. If too few results, widen: go one level coarser and repeat.

Say step 5 out loud. The widening loop is what makes the answer correct in sparse areas, and it is the step candidates forget.

Moving objects

Drivers and couriers update their location every 3–5 seconds, which makes the index write-heavy rather than read-heavy.

• Keep the live index in memory (Redis or a sharded in-process index), not in a durable database. Losing it means a few seconds of stale positions, not lost money.
• Store the latest position per object keyed by id, plus a per-cell set of object ids. An update is: remove from the old cell if it changed, add to the new cell, update the position hash. Most updates do not cross a cell boundary, so most are a single field write.
• Use TTLs so an object that stops reporting disappears instead of being dispatched to.
• Write the history to a stream (Kafka) for analytics and for the traffic or ETA pipeline; do not keep it in the live index.

Sizing: 1 M active drivers reporting every 4 s is 250 k writes/s — the number that justifies an in-memory index and sharding by cell.

Sharding and hot cells

Shard by cell prefix so nearby lookups land on the same shard, then handle the inevitable skew: a stadium at kick-off or an airport at 6 pm puts a disproportionate share of objects in one cell.

• Use finer cell levels in dense regions (adaptive levels, or a quadtree).
• Split hot cells across several shards with a suffix, and query all sub-shards.
• Cap the number of candidates returned from a cell and accept approximation; nobody needs all 40 000 people in the stadium, only 20.

Map tiles

Rendering maps is a caching problem, not a query problem. The world is split into z/x/y tiles, each tile is immutable content addressed by version, and tiles are served from a CDN. Vector tiles (geometry plus style applied on the client) are ~10× smaller than raster tiles, allow client-side styling and rotation, and are the modern default. Update by publishing a new tile version and letting the old ones expire.

Accuracy and privacy notes worth a sentence

• GPS is accurate to about 5 m outdoors and much worse in cities; snapping to roads or buildings is a separate step.
• Distances in a city are not straight lines. Use a geo query to shortlist candidates, then a routing service for the real ETA — shortlist with geometry, decide with routing.
• Location is sensitive data: coarsen or fuzz stored history, keep raw traces for a bounded period, and say so when the question involves people.

Common mistakes

• Querying one cell and missing the neighbours.
• Using lat/lng B-tree ranges at scale.
• Putting the live position index in the main database and drowning it in writes.
• Sorting by geohash distance instead of computing real distance on the candidate set.
• Ignoring hot cells until the interviewer names a stadium.

Checklist

• Encoding (geohash, S2, quadtree, PostGIS) and why.
• Cell level relative to the query radius, plus neighbour coverage and widening.
• Where live positions live, their write rate and TTL.
• Hot-cell strategy.
• Shortlist-then-route, if the product cares about travel time.