Geospatial indexing
Turn "near me" into a range query, because databases cannot sort by two dimensions at once.
What problem does geospatial indexing solve?
An index sorts on one axis. Location has two, and "everything within 3 km of here" is not a range on either of them. Filter by latitude and you get a band that circles the whole planet.
Geospatial indexes solve this by mapping two dimensions onto one, in a way that keeps nearby things nearby. Then closeness becomes a lookup you can index.
What geospatial indexing costs you
Every concept in here states a cost. A technique with no price is a technique you have not understood yet — and naming the cost out loud is most of what separates a senior answer from a junior one.
When to reach for geospatial indexing, and when not to
Use it when
- Find things near a point: drivers, restaurants, stores, users.
- Matching supply to demand by location.
- Taking in a stream of location updates and answering nearby queries over it.
- Checking whether a point is inside a region, like a delivery zone.
Do not, when
- Small datasets. Scanning ten thousand rows and computing distance is fast, and far simpler.
- The result depends on travel time rather than straight-line distance. Then geospatial indexing narrows the candidates, and a routing service ranks them.
How geospatial indexing actually works
Geohash is the one to explain, because it is simple and widely used. Repeatedly cut the world in half: left or right of the middle, top or bottom. Record each choice as a bit, then encode those bits as characters. A longer string means a smaller box. Five characters is about 5 km, six is about 1 km, seven about 150 m. Because the start of the string encodes the rough position, points that share a prefix are in the same region. So a nearby search is a prefix range scan on an ordinary B-tree index.
There is a catch to mention before the follow-up finds it. Two points on either side of a cell boundary can be 10 metres apart and share no prefix. So you always query your cell plus its eight neighbours, then work out the real distances and filter. Skipping the neighbours gives you a system that misses the closest result, which is a bad bug in a ride-hailing product.
A quadtree splits space as needed: a cell that gets too crowded divides into four. That handles very uneven density, city centre against countryside, better than a fixed grid. The price is a tree you have to maintain, which is more work when points move constantly. S2 and H3 are the production-grade versions. H3 uses hexagons, which have the nice property that all six neighbours are the same distance away, unlike a square with its mix of edges and corners.
For moving objects the shape of the problem changes. Drivers report their position every few seconds, so writes hugely outnumber reads, and a tree that rebalances on every update is the wrong choice. The common answer is to keep current positions in memory, grouped by cell. A Redis sorted set per cell works. Accept that positions are a few seconds old, and treat the index as a filter that produces candidates, not as the answer.
The last step is always the same. The index narrows millions down to dozens. Then you compute the real measure, actual distance or estimated arrival time from a routing service, and rank on that. Do not let the index decide the ranking.
- Forgetting neighbouring cells and silently missing the nearest result.
- One fixed cell size everywhere, so city queries return 50,000 candidates and rural ones return none.
- Ranking by straight-line distance when the product needs arrival time.
The geospatial indexing follow-up an interviewer will ask
"A driver is 100 metres away but in a different geohash cell. Do you find them?"
Only if I search the neighbouring cells, which is why that step is required and not an optimisation. A cell boundary is arbitrary, and the nearest driver is as likely to be just over it as inside it. So I query my cell plus the eight around it, combine the candidates, then compute true distances and sort. If the passenger is right at a corner I might widen further, and in an empty area I would step down to a shorter prefix, meaning bigger cells, until I have enough candidates. There is a second subtlety worth naming. I should rank by estimated arrival time, not straight-line distance, because a driver 100 metres away on the far side of a motorway with no crossing is much further away in practice than one 400 metres down the same road.
Your turn
Why can you not just index latitude and longitude as two normal columns and query both?
Learn it from the source
This page gets you interview-ready. These take you to where the idea is actually specified or measured — read them when you want the real depth.
- H3 — Hexagonal hierarchical geospatial indexing ↗Uber's grid system, built for exactly the matching problems this concept serves.