I'm hoping to use PostgreSQL (because I'm using Heroku;) ), but I read up on how MS Sql Server implements spatial indexes. Basically, it recursively divides the coordinate system into quadrants. Then, when looking for a range of coordinates, it can figure out which quadrants are covered by that range and efficiently query them using b-trees. Very cool. I wonder if PostgreSQL spatial support works similarly...