R-Tree Visualizer

Enter a latitude and longitude and watch an R-tree — the spatial index MySQL and PostGIS actually use — find the places near you. Instead of a fixed grid, it groups nearby points into bounding boxes and only opens the boxes that overlap your search area.

How an R-tree works

An R-tree groups objects into minimum bounding rectangles (MBRs) — boxes inside boxes, up to the root. It splits a node when the node gets too full, not when space gets crowded, so the tree stays balanced (every leaf at the same depth) and each node maps neatly onto one disk page. That is exactly why databases pick an R-tree over a quadtree for spatial indexes.

The trade-off

Because the boxes are drawn around the data, sibling boxes can overlap, so a search sometimes walks down more than one branch.
Run the same location in the quadtree and compare: same matches, but the R-tree opens far fewer nodes and stays much shallower.

Full write-up: MySQL Internals.