"Find drivers within 2 km", "restaurants near me", "friends nearby": these are proximity queries on latitude/longitude. A normal index on lat and one on lng can't answer them efficiently, because a nearby search is a 2-D range. Geospatial indexes map 2-D space onto structures that make "what is near this point?" a cheap lookup.
In simple words
Instead of checking the distance to every taxi in the city, you divide the map into a grid of squares and only look at taxis in your square and the eight squares around it.
Turn a 2-D search into a few cell lookups, then check exact distances on the small candidate set.
Deep Dive: Why Two 1-D Indexes Fail
SELECT * FROM drivers
WHERE lat BETWEEN 12.90 AND 12.99 AND lng BETWEEN 77.55 AND 77.65;
The lat index returns a whole horizontal band of the map (every driver at
that latitude, worldwide); the lng index returns a whole vertical band.
Intersecting two huge sets is slow. We need an index on "the cell" instead.
Deep Dive: Geohash
Recursively split the world in half (longitude, then latitude, alternating),
writing 0/1 for each choice; encode the bits in base32.
precision cell size (approx)
4 chars ~39 km x 19.5 km
5 chars ~4.9 km x 4.9 km
6 chars ~1.2 km x 0.6 km
7 chars ~153 m x 153 m
Nearby points usually share a prefix: "tdr1y..." and "tdr1w..." are close.
Query: compute the user's cell at a precision matching the radius,
fetch that cell + its 8 neighbours, then filter by exact distance.
Why the neighbours: two points a metre apart can sit on either side of a cell border and share no prefix. Geohash strings index in any B-tree or key-value store and work well as cache/partition keys. Redis GEO commands use a geohash-style encoding in a sorted set.
Deep Dive: Quadtrees and S2 / H3
Quadtree: split a region into four quadrants, and keep splitting any quadrant with more than N points. Dense cities get small cells and deserts stay coarse, so each leaf holds a similar number of points. Usually held in memory and rebuilt or updated periodically.
Google S2: projects the sphere onto a cube and uses a Hilbert curve to number cells, giving a hierarchy of cells with 64-bit ids and good locality; a region is covered by a small set of cell ranges.
Uber H3: hexagonal cells at multiple resolutions; hexagons have uniform neighbour distances, handy for supply/demand grids and pricing.
Key Pointers
Turn 2-D proximity into lookups on cell ids; then filter candidates by exact distance (haversine).
Always search the neighbouring cells too.
Geohash: simple, string prefixes, fixed grid. Quadtree: adapts to density. S2/H3: hierarchical cells used at scale.
Moving objects (drivers) update often: keep their locations in memory (e.g. Redis GEO) with a short TTL, not in a heavy database index.
How It Works
On a location update, compute the cell id and store the object in that cell's set (removing it from its old cell).
For a query, pick a precision from the search radius, compute the query cell and its neighbours.
Fetch all objects in those cells and compute exact distances; keep those within the radius.
If too few results, widen to a coarser precision (or a ring of more cells) and repeat.
Follow-up Questions
Geohash or quadtree for "restaurants near me"?
Restaurants rarely move and density varies hugely between city and countryside; a quadtree (or geohash with variable precision) adapts well. For millions of frequently moving drivers, a geohash/S2 cell keyed store in memory is simpler to update.
What about PostGIS?
Postgres with PostGIS offers R-tree-like GiST indexes and exact geographic functions. Great for moderate scale and complex shapes (polygons, routes); very high update rates of moving objects are usually kept in an in-memory store instead.
Trade-offs
Fixed grids are simple and cache-friendly but uneven in dense areas; adaptive trees balance load but are more complex to update and shard. All approaches return candidates that must still be filtered by exact distance.