18.1 Why does a normal latitude/longitude index fail?

On the map: Suppose the map book's index only lists streets by how far north they are. Ask for "near the store" and it hands you every street at that height, right across the city from east to west. You still have to go through them one by one to find the ones that are also near the store east-to-west.

In the system: Store riders in a table with lat and lng columns and ask:

A B-tree index (Chapter 9) sorts by one thing at a time. An index on lat finds the whole band of riders at that latitude, then checks lng row by row. A composite index on (lat, lng) doesn't really help either: it's sorted by lat first, so a range on lat still forces a scan through every lng inside that range.

Figure: a B-tree sorts by one thing at a time, so a two-dimensional "box" query turns into a band scan.

Two more problems with raw coordinates:

• Distance isn't simple. One degree of latitude is about 111 km everywhere, but one degree of longitude shrinks as you go north: about 108 km at Bengaluru's latitude (12.97°N) and about half that at 60°N. A box in degrees isn't a circle in kilometres.
• "Nearest" needs sorting by distance, which an index on raw columns can't do.

What we need is a way to turn two numbers (lat, lng) into one key where nearby places get similar keys. Then an ordinary index, or a plain dictionary, can find them.

Memory code: "One index sorts one way; a map needs two."