Why you need a geospatial index, and when to use one
"Find the drivers near me" or "restaurants within 2 km" asks for the nearest items to a point. Comparing the distance to every item works for a few hundred places and fails for millions that move. A geospatial index organises locations so a query looks only at the nearby ones.
It gives you two things interviewers always ask about:
- Low latency: a nearby search touches a handful of cells, not the whole map.
- Scalability: the index can be split by region, so a city or a country is handled by its own servers.
Use it when:
- You search by distance or area: nearby drivers, stores, friends, listings.
- Locations change often (vehicles) or the dataset is large (millions of places).
- You need map tiles or regions: which area contains this point.
Skip it, or use something else, when:
- You have a few hundred points: a scan is fine.
- You filter by city or postal code, not distance: an ordinary index is enough.
Try it
A rider wants the nearest driver. Change how the search narrows down the drivers.
Geospatial Indexing
Step 1 of 4 · Press Space to play, arrow keys to stepInitial state. 7 drivers are spread over a 4 by 4 grid of cells. A rider in cell (1, 1) wants the nearest driver.
- tick:
- 0
- drivers in the city:
- 7
- drivers examined:
- 0
- found nearest:
- -
1 tick = one step of the simulation.
Things to try:
- Run Scan every driver. It always finds the right one but looks at everyone (every driver examined).
- Run Grid: my own cell with a rider at the edge of a cell. The real nearest driver is across the border and gets missed (1 of 7 drivers examined, found nearest NO).
- Switch to my cell plus its 8 neighbours, then try Dense downtown. Fixed cells can still hold too many drivers (42 of 46 examined with neighbours, 41 of 46 with only the own cell).
What to watch: with the typical situation and neighbours, only 2 of 6 drivers are examined and the answer is right. The simulation uses fixed cells and no search radius, so it does not show a radius larger than a cell, or a closer driver just outside the nine cells. Both need the extra checks in the next sections.
Spatial index designs
| Design | How it works | Good when | Weakness |
|---|---|---|---|
| Fixed grid | Divide the map into equal square cells and keep a list of points per cell | Evenly spread points | Hot cells in cities, empty cells elsewhere |
| Geohash | Encode a location as a short string where a shared prefix means a nearby place | Key-value stores and prefix indexes | Cell edges: near points can have different prefixes |
| Quadtree | Split a square into four whenever it holds too many points | Uneven density, moving points | Rebalancing as points move |
| R-tree | Group nearby points or shapes in nested bounding boxes | Shapes and ranges in databases (such as PostGIS) | More complex to update |
| S2 or H3 cells | Cover the globe with hierarchical cells of near-uniform shape: S2 uses squares, H3 uses hexagons (plus 12 pentagons) | Global services with many resolutions | Library and concepts to learn |
Geohash in one minute
A geohash turns a latitude and longitude into a short string by repeatedly halving the map. Each extra character narrows the location to a smaller box, so a longer shared prefix means a smaller shared box. As commonly published figures, five characters describe a box roughly 5 km across and six characters roughly 1.2 km by 0.6 km (near the equator; boxes get narrower towards the poles).
Two points in the same box share the prefix. But two points a few metres apart on either side of a box edge can have very different prefixes. That is why a prefix search must also read the neighbouring boxes.
Grid vs tree
- A fixed grid or geohash is simple and maps well to key-value stores: the cell is the key. It struggles when density varies a lot, because one cell may hold thousands of points while many are empty.
- A quadtree or R-tree adapts to density, splitting busy areas into smaller pieces, so each leaf holds a similar number of points. It is more complex to build and update, especially for moving points.
How a nearby search works
- Index: each point's location is converted to a cell ID (a grid cell, a geohash or an S2/H3 cell), and the point is stored under that cell.
- Query: convert the search point to its cell and find the cells that overlap the search radius. This includes the neighbouring cells, because the nearest point can be just across a border. The block of nine cells is enough only when a cell is at least as wide as the search radius. If the radius is larger, read every cell that the radius overlaps.
- Candidates: collect the points in those cells, which is a small set.
- Filter and sort: compute the exact distance to each candidate, drop those outside the radius, and sort by distance.
- Widen if needed: if there are too few results, search the next ring of cells. Also widen when the k-th best result is farther away than the nearest edge of the area you have searched, because a closer point could sit just outside that edge. Stop only when the k-th distance fits inside the searched area, measured to its nearest edge.
- Update: a moving point is removed from its old cell and added to the new one when it crosses a border.
Sizing a nearby search
These numbers are illustrative. They show the method, not a real system.
- Update rate: 1,000,000 drivers each reporting every 4 seconds is 1,000,000 / 4 = 250,000 updates per second. Most only change a position inside a cell. A few move the point to a new cell.
- Memory: if each stored position takes about 100 bytes (ID, cell, latitude, longitude, time), 1,000,000 drivers need about 100 MB, which fits on one machine. The update rate, not the size, is what pushes you to partition.
- Load per partition: if one city holds 40,000 of those drivers, its partition sees 40,000 / 4 = 10,000 updates per second.
- Cell size against radius: for a 2 km search radius, cells must be at least 2 km wide for nine cells to be enough. A five-character geohash (about 5 km) works with nine cells. A six-character geohash (about 1.2 km by 0.6 km) is narrower than the radius, so you read a larger block, up to about 5 columns by 8 rows. Smaller cells mean fewer candidates per cell but more cells to read and more cell changes to write.
Geospatial index vs the alternatives
| Concern | Spatial index | Scan and compute distance | Index on latitude and longitude separately |
|---|---|---|---|
| Query cost | Low | Grows with data | Medium |
| Correct near cell borders | Yes, with neighbours | Yes | Yes |
| Handles moving points | Yes | Yes | Yes |
| Handles dense and sparse areas | Yes with trees | Yes | Poorly |
| Extra work | Index maintenance | None | Low |
| Best for | Nearby search at scale | Small data | Simple bounding boxes |
Use a spatial index once a scan is too slow. For small datasets the scan is simplest.
Avoiding a new single point of failure
- Partition the index by region so each city or area has its own servers and a failure stays local.
- Replicate the index, since reads dominate. For moving points, the index is rebuilt quickly from fresh location updates.
- Keep the index small and in memory for hot, short-lived data, with durable storage for history.
You accept that results are approximate by a few seconds for moving points.
Failure cases to design for:
- Index lost after a restart: an in-memory partition starts empty, so searches find nobody until fresh updates arrive. Moving vehicles that report every few seconds refill it quickly, so keep a warm replica, or treat an empty or tiny result as a sign to widen the search or read another replica instead of telling the rider that no drivers exist.
- A hot city partition: partition by load, not by area. Split a busy city further (for example by cell prefix) and let quiet regions share a server.
- A search near a partition border: read both partitions, merge the candidates, then compute the exact distance.
- Replica lag: a replica may show a position from a few seconds ago, so rank with exact distance and confirm with the owner of the record before assigning a driver.
Common mistakes
- Searching only the point's own cell. The nearest item may be across a border. Include neighbours.
- Treating latitude and longitude like flat x and y. A degree of longitude covers less ground towards the poles, and longitude wraps at the date line. Use a great-circle distance, or a geography type such as PostGIS geography, for the final ranking.
- One fixed cell size everywhere. Cities need finer cells than deserts.
- Writing every location update to a disk database. Keep the latest in memory.
- Sorting by cell distance. Always compute the exact distance for the final ranking.
- Forgetting the radius edge. Filter candidates by true distance.
How to talk about geospatial indexing in an interview
- Say that you convert locations to cells and search the point's cell plus its neighbours.
- Name a concrete scheme: geohash, quadtree, or S2/H3, and say why (key-value fit or uneven density).
- Cover moving points, partitioning by region, and computing exact distance on the small candidate set.
- Name the trade-off: a finer grid gives fewer candidates but more cells to search and more updates.