Geospatial Indexing: Geohash, Quadtrees & Nearby Search

The problem. A table of places with lat and lng columns cannot use an ordinary B-tree to answer 'within 2 km of this point': a B-tree sorts on one dimension, and 'near' is two-dimensional. Scanning every row works at 1,000 places and collapses at 100 million.

Idea 1 - Geohash. Split the world into a grid, name each cell with a short string, and make nearby cells share a prefix. Each extra character shrinks the cell: about 5 km at 5 characters, about 150 m at 7. Store the geohash in a column, index it, and a prefix query (LIKE 'u4pru%') returns everything in the cell.

The catch: cell edges. Two points 10 m apart can sit in different cells with different prefixes. So a nearby search always reads the target cell plus its 8 neighbours, then filters those candidates by exact distance (haversine). The grid is a cheap first filter, never the final answer.

Idea 2 - Quadtree. Start with one box for the whole map. When a box holds more than N places (say 100), split it into four children, recursively. Dense cities become deep trees of small boxes; the ocean stays one big box. A query walks down to the box holding the point and collects neighbours. The tree adapts to density, which a fixed geohash grid does not. It usually lives in memory on a service and is rebuilt from the database.

Idea 3 - S2 / H3 cells. Google S2 and Uber H3 cover the sphere with hierarchical cells (squares or hexagons) identified by an integer. They fix geohash's distortion near the poles and make 'ring of neighbours' a first-class operation. H3 hexagons suit ride-hailing because every neighbour is the same distance away.

Which to use? Interview default: geohash in a database column or Redis (GEOADD / GEOSEARCH use it internally) for static places; a quadtree when density varies wildly; H3/S2 for moving objects and surge-style aggregation by area.

Moving objects (drivers, couriers). Writes dominate: each driver pings every few seconds. Keep current positions in memory or Redis keyed by cell, not in the main database, and expire stale entries. Static places (restaurants) are the opposite: read-heavy, so index and cache them.

Routing is a different problem. 'Find nearby' is an index lookup. 'Fastest route' is a graph search (Dijkstra / A*) over road segments with live traffic weights, usually run on a pre-processed graph partitioned by region. Maps-style systems separate the two: tiles and nearby search on one side, routing on the other.