how to optimize a geolocation database in mysql for euclidean distance search/query

i am usi开发者_JS百科ng mysql to store geolocation data. i would like to know how to optimize the table holding the (x,y) coordinates so that queries will be optimized against it. (the x,y will be lat/long).

for example, i have a table with the following fields: id, x, y, notes.

at sometime later, i will perform a query: select * from geoloc where sqrt( (x-@x)^2 + (y-@y)^2 ) < delta

please note, i have no idea how the actual SQL statement will work right now, so the above is just a very rough idea of what i want.

so what do i have to do to optimize this table for this type of query? any pointers are greatly appreciated.

You'll have a hard time optimizing for that kind of query. A better option would be to compute a bounding box from the (x,y) coordinates and delta passed in. Then query for any locations where the coordinates fall in that box. That query would be much simpler and would be able to use any indexes you might have on the x and y fields.

Of course the results from that query aren't as exact since it's a bounding box rather than a circle. If you want better results, you can take the results from the bounding box query, then use the slower euclidean method to filter out the ones that don't fall into the circle.

Maybe you could try Voronoi diagrams. Take a look here http://www.cs.sunysb.edu/~algorith/files/nearest-neighbor.shtml