Spatial indexing — Geohash, Quadtrees, S2, H3

When you have millions of points and need to answer "what's near here?" in milliseconds, you need a spatial index. A spatial index pre-organises data by location so proximity queries skip the vast majority of records rather than scanning every row. The right choice depends on your data volume, query patterns, and database.

Geohash

A geohash encodes a lat/lon as a short string. The longer the string, the smaller the cell. Each character adds 5 bits of precision, alternating between latitude and longitude.

Length	Cell size (mid-latitudes)
1	~5,000 km
4	~20 km
6	~600 m
8	~19 m
12	~3.7 cm

Why it's useful: prefix matching = nearby cells. gcpvj is in gcpv, which is in gcp. Range queries on a geohash string column work directly with B-tree indexes — no special spatial extension needed.

Caveat: geohash cells are not square (they're elongated), and adjacent cells often have completely different prefixes (the famous "boundary problem" near the equator and prime meridian). Always check 8 neighbors plus center for proximity queries. If your query point sits near a cell boundary, the closest point in the world might be in a neighboring cell with a completely different hash prefix.

Quadtree

A quadtree recursively divides space into 4 quadrants:

Root: covers the whole world
  ├── NW
  ├── NE
  ├── SW
  └── SE
       ├── NW
       ├── NE
       ...

Each leaf holds up to N points. Insertion and proximity queries are $O(\log n)$ on average. The Web Mercator tile system is a quadtree.