"Show restaurants within 3 km of me." "Find the free riders closest to this restaurant." These are the most common queries Tiffin runs, and a plain database index is bad at them.
The reason: a B-tree sorts on one dimension. An index on latitude finds every restaurant in a thin horizontal strip across the whole country. An index on longitude finds a thin vertical strip. Neither finds "near this point", which needs both at once. Scanning one strip and filtering by the other works for a small city and falls over for a big one.
The fix is to turn two dimensions into one, in a way that keeps nearby points near each other. Geohashes do that with a string. Quadtrees do it with a tree. Both rest on the same idea: divide the map into boxes, then divide the boxes into smaller boxes.
Geohash: halving the world, one bit at a time
Start with the whole world: longitude from -180 to 180, latitude from -90 to 90.
- Is the point's longitude in the left half or the right half? Write 0 for left, 1 for right. Keep only that half.
- Now the same question for latitude: bottom half 0, top half 1. Keep that half.
- Alternate, longitude then latitude, halving the box each time.
- Every 5 bits become one character in a base-32 alphabet:
0123456789bcdefghjkmnpqrstuvwxyz(no a, i, l or o).
Each bit halves the box. Each character divides it into 32. So a longer geohash is a smaller box, and every geohash's prefix is the bigger box that contains it.