Ask HN: Storing spatial data in SQL

What's the best way to store spatial data in SQL in a way where the query "find all points within x miles of point a" can be performed efficiently.

My initial approach is to store latitude and longitude, and create an index on both longitude and latitude. However, since I'd be querying both longitude and latitude with a range, only one of the indexes would be useful. Basically, the index could narrow down the search to one vertical bar of the entire earth, and then a table scan to find the locations within that bar. (Of course, clustering on latitude first would have the opposite effect: one horizontal band of the earth, and then within the band would be a table scan).

I know there are spatial data types in some of the SQL implementations, but can anything really ever be more efficient than that when doing a "find all points within x miles" type query? If so, how's this possible?