18. Geospatial Indexing
The picture to keep in your head
Every question below is answered twice: first on the map, so you can picture it, then in the system, so you know exactly how it works. Each answer ends with a memory code to lock it in.
The picture to keep in your head
Think of an old city map book. The city is split into grid squares: A1, A2, B4, C7. The index at the back says "MG Road: page 12, square B4". You don't search the whole city for MG Road; you go straight to B4.
Now someone asks, "Which delivery riders are near the store?" You don't check every rider in the city. You look in the store's square, B4. And because a rider could be just across the line in B5 or C4, you also glance at the eight squares around it. Then, for the handful of riders you found, you measure the real distance.
That's geospatial indexing: turn "near me" into "in my square or the squares around it", then measure exactly.
Our running example: the grocery app's delivery riders in Bengaluru. When an order comes in, the app must find riders within 2 km of the store, fast, while thousands of riders are moving and sending their location every few seconds. The numbers in this chapter (10,000 riders on shift, a ping every 4 seconds) are assumptions for practice.
| On the map | In the system |
|---|---|
| Searching every street in the city | A full scan, or an index on one coordinate only |
| Grid squares with names like B4 | Geohash cells, quadtree squares, S2 or H3 cells |
| Smaller squares on a zoomed-in page | A longer geohash, a deeper quadtree level |
| Glancing at the eight squares around B4 | Searching a cell plus its neighbours |
| Measuring with a ruler at the end | The exact distance filter (haversine) |
| Riders moving between squares | Location updates |
| One map desk per city | Sharding by region |
Figure: cells narrow the search; the real distance decides the answer.