What is a good way to store geographical data for distance calculations

Question

What would be the best way to store data in a database for geographical calculations? Say I have an ItemsForSale table paired to a Users table which holds their geo location. I know I can use latitude and longitude to look up items that are within a certain mile radius by using Lambert's formula for long lines or the Haversine formula but I am not sure if there is a better approach for this.

Answer 1

I'm not sure standard databases like MySql provide spacial indexing. You need to put them in a persistent spacial index. Like M-trees. Spacial indexes are efficient data structures that can perform range queries over distance metrics.

• Wikipedia M tree
• Stack Overflow: Storing coordinates in a smart way to obtain the set of coordinates within a certain range from (lat_,lon_)

You might be able to find an implementation of M-tree or other spacial indexing data structures like K-D trees.

EDIT: After Martijn Pieters mentioned MySql having spatial indexes, I looked it up. Turns out it does have a R-tree but the support doesn't seem great. I only use innodb because mostly I end up requiring row level locks.

MySQL 5.6 implements an additional set of functions that can help create geo-enabled applications with MySQL. Storing polygons boundaries (ZIP code boundaries for example) is efficient and the new spatial functions (st_within, st_contains, etc) will produce correct results and will use spatial (rtree) indexes (for MyISAM tables only). The OpenGIS standard is very common and it is easy to obtain the data in this format or use the standard application which can “talk” this language. Unfortunately, st_distance function is not very usable for calculating distance between 2 points on Earth and it does not use an index. In this case it is still more feasible to calculate distances manually using the harvesine formula. Hopefully this will be fixed in the next mysql release.

• Using the new spatial functions in MySQL 5.6 for geo-enabled applications