18. Geospatial Indexing
1
The picture to keep in your head2
18.1 Why does a normal latitude/longitude index fail?3
18.2 What are spatial indexes?4
18.3 How do "nearby within radius" queries work?5
18.4 How do you update moving drivers?6
18.5 How do you shard by region?7
Memory card and where the analogy breaks8
Practice: five levels9
Interview questions10
Solutions11
Sources12
Code lab18. Geospatial Indexing
Memory card and where the analogy breaks
3 min read+10 XP
The memory card (tear this page out)
| # | Question | Memory code |
|---|---|---|
| 18.1 | Why a lat/lng index fails? | One index sorts one way; a map needs two |
| 18.2.1 | Geohash? | Each extra letter zooms in; a shared start means the same square |
| 18.2.2 | Quadtree? | Split the square only where it's crowded |
| 18.2.3 | S2 and H3? | S2 wraps the world in a cube; H3 tiles it with honeycomb |
| 18.3 | Radius queries? | Search nine squares, then measure; never trust the border |
| 18.4 | Moving drivers? | Keep only where they are now, and move them only when they cross a line |
| 18.5 | Sharding by region? | Shard by place, split the busy places, and ask both sides at a border |
The whole chapter in one line: Turn two coordinates into one cell key, search the cell and its neighbours, measure exactly, keep moving points in memory, and shard by place.
Where the analogy breaks
- A paper map has one fixed grid. Software can use many grids at once, at different sizes, or a grid that adapts to density (quadtree).
- A map is flat. The Earth isn't: longitude degrees shrink as you go north, so distances need the haversine formula, and cells near the poles get distorted (which S2 and H3 handle better).
- A map desk looks things up when asked. A real system is also flooded with updates, thousands of pings a second, which shapes the design as much as the queries do.
Quick check
Five questions on this chapter. Pick an answer, then check it.
quiz