Spatial data structures are great, and heavily used in all kinds of mapping applications. Most of the systems I've worked with used the more constrained quadtree structure, where the map is divided into uniformly-sized tiles, and a level-of-detail hierarchy is built. This is good for raster data, where each tile is a picture and the whole world is covered by tiles. The R-tree has great advantages when the complexity is not uniformly distributed across the map, for example, vector road data, where vast areas on earth have no data, and most of the data is concentrated in small urban areas.
I believe PostGIS, which adds spatial operations to Postgres, uses an R-tree as its spatial index.
An improvement on the R-tree, the R(star)-tree, uses a different node splitting algorithm and includes re-insertions (similar to balancing a B-tree), reducing both coverage and overlap. The insertion complexity is greater, but in general, R(star)-tree query performance tends to be a bit better for mapping applications. Generally, maps don't change that often, so building the tree tends to happen far less often than querying it.
There are many more specialized spatial data structures available, for example, Kd-trees, which can be perfectly balanced and are useful for storing point data.
If you're really interested in this stuff, the holy bibles for spacial data structures (which I keep in a special place on my bookshelf) are a pair of books written by H. Samet: The Design and Analysis of Spatial Data Structures, and Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS.
EDIT: Formatting, and apparently you can't write the asterisk character on HN
R-Tree paper (1984): http://postgis.org/support/rtree.pdf
R(star)-Tree (1990): http://epub.ub.uni-muenchen.de/4256/1/31.pdf
PostGIS: http://postgis.net
H.Samet textbooks: http://www.cs.umd.edu/~hjs/design.html
I believe PostGIS, which adds spatial operations to Postgres, uses an R-tree as its spatial index.
An improvement on the R-tree, the R(star)-tree, uses a different node splitting algorithm and includes re-insertions (similar to balancing a B-tree), reducing both coverage and overlap. The insertion complexity is greater, but in general, R(star)-tree query performance tends to be a bit better for mapping applications. Generally, maps don't change that often, so building the tree tends to happen far less often than querying it.
There are many more specialized spatial data structures available, for example, Kd-trees, which can be perfectly balanced and are useful for storing point data.
If you're really interested in this stuff, the holy bibles for spacial data structures (which I keep in a special place on my bookshelf) are a pair of books written by H. Samet: The Design and Analysis of Spatial Data Structures, and Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS.
EDIT: Formatting, and apparently you can't write the asterisk character on HN
R-Tree paper (1984): http://postgis.org/support/rtree.pdf
R(star)-Tree (1990): http://epub.ub.uni-muenchen.de/4256/1/31.pdf
PostGIS: http://postgis.net
H.Samet textbooks: http://www.cs.umd.edu/~hjs/design.html