Geohashes and quadtrees

"Find drivers within 2 km", "restaurants near me", "which delivery zone is this address in?" A normal B-tree index on latitude and longitude doesn't answer these well: it can filter one dimension at a time, not a 2-D neighbourhood. Geospatial indexes map 2-D positions to keys or trees that make proximity queries cheap.

#Geohash

A geohash repeatedly halves the world — longitude, then latitude, alternating — and records each choice as a bit, then encodes the bits in base32. Longer strings mean smaller cells:

Nearby points usually share a prefix, so "nearby" becomes a prefix range scan on an ordinary index. The catch: two points on either side of a cell boundary can have entirely different prefixes. Always search the target cell and its eight neighbours, then filter by exact distance.

#Quadtrees

A quadtree recursively splits space into four quadrants, subdividing only where there are many points. Dense cities get small cells and empty oceans stay as one big cell, which keeps each cell's point count bounded. Good for in-memory indexes of moving objects, such as drivers, rebuilt or updated frequently.

#Other systems

• S2 (Google) and H3 (Uber) cover the sphere with hierarchical cells — S2 with squares projected from a cube, H3 with hexagons whose neighbours are all equidistant, which is convenient for aggregating and comparing areas.
• R-trees index shapes (polygons, lines) by bounding boxes; PostGIS's GiST indexes and most spatial databases use them.

#In practice

• In PostgreSQL, PostGIS with a GiST index answers ST_DWithin radius queries directly.
• Redis has GEOADD and GEOSEARCH, built on geohash-encoded sorted sets.
• For very high update rates (millions of moving vehicles), keep positions in memory, sharded by cell, and update them in place.

Geospatial keys can also serve as partition keys, with care: cities make some cells far hotter than others (hot partitions).