Open Yelp, ask for coffee shops within a mile, and results come back instantly. Under that simple request is a genuinely hard database question: how do you efficiently find all points near a given point when you have tens of millions of points and a globe to spread them across. A plain database index does not help here, because "near" is a two-dimensional idea and ordinary indexes are one-dimensional.
The core problem
Suppose every place is a row with a latitude and longitude. To find places near you, the brute-force approach computes the distance from you to every single place and keeps the close ones. That is a full scan on every search. It works for a thousand rows and dies at ten million. You need a way to prune, to look only at places that could plausibly be near, without touching the rest.
The difficulty is that a normal B-tree index on latitude, or on longitude, only orders one axis. You can quickly find places in a latitude band, but they could be on the other side of the planet by longitude. Two-dimensional proximity needs a two-dimensional index.
Key design decisions
