Farah wants the nearest chai stall
Farah builds ChaiMap, an app that answers one question: where is the nearest good chai stall? A year later she adds ChaiRide, which books an auto-rickshaw to take you there. (Farah, both apps and every number here are made up for teaching.)
Think about how you find the nearest stall in a big city. You don't measure the distance to every stall in the country. You narrow down to your neighbourhood, then compare the few stalls in it. Location systems do the same thing: chop the map into cells, index things by cell, and search your cell and its neighbours.
Farah's journey raises every question this topic asks:
| Problem |
Idea it forces |
| "The nearby query scans half of India" |
Why plain indexes fail |
| "How do I cut up the map?" |
Geohash |
| "The stall 50 m away didn't show up" |
Searching neighbouring cells |
| "Mumbai has 1,000 stalls per square km, my village has 3" |
Quadtrees, S2, H3 |
| "Build it for real" |
A proximity service for static places |
| "Autos move every 4 seconds" |
A write-heavy live-location pipeline |
| "Two riders got the same auto" |
Locking the matched driver |
| "The nearest auto was across the river" |
Ranking by road ETA |
This guide follows Search. Its ride-matching part connects to BookMyShow for the "reserve a scarce thing" pattern.
1. "The nearby query scans half of India": why plain indexes fail
Farah's first query:
SELECT * FROM places WHERE lat BETWEEN ... AND lon BETWEEN ...
The database uses one index, on latitude or longitude. Latitude alone matches a thick horizontal band right across the planet, through Mumbai, Kolkata and a dozen countries. Two separate one-dimensional indexes can't serve a two-dimensional range well. Farah needs an index that keeps points that are near each other on the map near each other in the index.
2. "How do I cut up the map?": geohash
You've reached the free preview of this post.
Subscribe to the Blogs plan (₹99/mo) — or use any Algomi Suite, Career, Investor, or Trader plan — to keep reading.
See plans
