Geospatial indexing: geohash, quadtrees and H3

A normal B-tree index sorts one dimension. A query like 'drivers within 2 km' needs two dimensions (latitude and longitude), and an index on latitude alone returns a long strip across the whole country. Geospatial indexes solve this by dividing the earth into cells and giving each cell an ID, so nearby points share or neighbour the same cell IDs.

Geohash encodes a point as a base-32 string by repeatedly halving longitude and latitude ranges. Each extra character makes the cell smaller: 5 characters is about 4.9 km x 4.9 km, 6 is about 1.2 km x 0.6 km, 7 is about 153 m x 153 m. Points with a common prefix are usually close, so a prefix search in any sorted store (Redis sorted set, B-tree, DynamoDB sort key) finds candidates. Edge case: two points 10 m apart across a cell boundary can have different prefixes, so you always search the 8 neighbouring cells too.

A quadtree recursively splits a square into 4 children until each leaf holds at most K points (say 100). Dense areas like central Bengaluru get deep, small cells; empty areas stay large. It adapts to density, but it usually lives in memory and must be rebuilt or rebalanced as points move.

Google's S2 maps the sphere onto a cube and a Hilbert curve, giving 64-bit cell IDs at 31 levels. Uber's H3 uses hexagons at 16 resolutions; every hexagon has 6 neighbours at the same distance, which makes ring searches, smoothing and surge-pricing zones cleaner than with squares. Both have libraries to cover a circle or polygon with a set of cells.

1. 1Classify the data: static points (shops, restaurants, ATMs) change rarely and suit a database index; moving points (drivers, riders, delivery partners) update every few seconds and suit an in-memory index.
2. 2Choose the cell size from the search radius: make cells about the size of a typical search, so a search covers the centre cell plus its neighbours (9 geohash cells or an H3 ring of 7) without scanning far too many points.
3. 3Write path for moving points: on each GPS ping, compute the new cell; if it changed, remove the driver from the old cell and add to the new one; always update the driver's latest position and timestamp. Expire drivers whose last ping is older than about 30 s.
4. 4Read path: compute the user's cell, get the neighbour cells, fetch all candidates in those cells, compute exact distance (haversine) or, better, road ETA, filter by radius and status (available, vehicle type), sort and return the top N.
5. 5If too few results, expand: search the next ring of cells or a coarser resolution, up to a maximum radius.
6. 6Shard by geography: partition the index by city or by coarse cell (for example H3 resolution 3 or 4) so each shard holds one region; a city like Mumbai may need several shards. Watch for hot shards during rain or events.
7. 7For static points, use built-in support: PostGIS with a GiST index and ST_DWithin, MongoDB 2dsphere, Elasticsearch geo_point with geo_distance queries, or Redis GEOSEARCH, which stores 52-bit geohash scores in a sorted set.
8. 8Use road distance for ranking: straight-line distance ignores rivers, flyovers and one-way roads. Index by straight-line distance to get candidates cheaply, then rank the top 20 to 50 by ETA from a routing engine (OSRM, Valhalla or a maps API).

# Nearby drivers with H3 + Redis (h3-py v4 API)
import h3, time

RES = 8

def update_location(r, driver_id, lat, lng):
    cell = h3.latlng_to_cell(lat, lng, RES)
    old = r.hget(f"driver:{driver_id}", "cell")
    pipe = r.pipeline()
    if old and old.decode() != cell:
        pipe.srem(f"cell:{old.decode()}", driver_id)
    pipe.sadd(f"cell:{cell}", driver_id)
    pipe.hset(f"driver:{driver_id}", mapping={"lat": lat, "lng": lng, "cell": cell, "ts": time.time()})
    pipe.execute()

def candidates(r, lat, lng, k=1):
    cells = h3.grid_disk(h3.latlng_to_cell(lat, lng, RES), k)  # centre + k rings
    ids = set()
    for c in cells:
        ids |= {i.decode() for i in r.smembers(f"cell:{c}")}
    return ids  # then drop stale, filter by status, rank by ETA