You asked for 4 km. The database read 600.

transcript

You ask your database for shops near one customer. It reads a strip across all of India.

20 million places. Illustrative, but realistic. One index, on latitude, then longitude. Looks perfect. The query is a small box. 4 kilometres by 4.

But here's the catch. A B-tree sorts by one key. Longitude only sorts within the exact same latitude. And no two shops share an exact latitude.

So it uses latitude, and nothing else. A strip 4 kilometres tall. From the Arabian Sea to the Bay of Bengal. About 600 wide. That's 150 times the box. Tens of thousands of rows, for a few hundred.

Add a second index? Now you read two strips. Then intersect two huge sets. Still slow. The fix: give nearby places nearby keys. Cells. Near here becomes a few short ranges. Then check exact distance.

A B-tree is a line. Near is a circle. Use cells.

Full breakdown in the lecture.