What is the best way to store a group of coordinates, for quick lookup based on proximity?

Question

I need to store a group of coordinates in a database. I also need to query the database, given a coordinate that may or not be in the database, and get a list of coordinates within a certain proximity.

What's the best way to go about doing this? I've heard that the world map can be broken into hexagons, with each coordinate assigned to a hexagon, but I don't need to store the entire world map at this point (also what if two points are close to each other but in different hexagons?)

The app is similar to a food delivery app, so accuracy within a couple miles is important.

user_1643676 · Answer

Depending on the db server you are using, there are geography types.

For instance MsSql has the point type: https://docs.microsoft.com/en-us/sql/t-sql/spatial-geography/point-geography-data-type?view=sql-server-ver15

Point ( Lat, Long, SRID )

You can then use this guide: https://docs.microsoft.com/en-us/sql/relational-databases/spatial/query-spatial-data-for-nearest-neighbor?view=sql-server-ver15 to create the proper indexes and query for the nearest neighbors (however many you require)

MySql also supports spatial data, as can be seen here: https://dev.mysql.com/doc/refman/8.0/en/spatial-types.html

Most db flavors do, so just Google spatial data for the database of your choice.

Important: don't try to recreate them yourself in a custom way. The built in solution is optimized for these queries. Any custom implementation with other types, will most certainly be slower.

What is the best way to store a group of coordinates, for quick lookup based on proximity?

1 Answers

Important: don't try to recreate them yourself in a custom way. The built in solution is optimized for these queries. Any custom implementation with other types, will most certainly be slower.