Get elements from database based on distance from a point

Question

Im pretty new to backend web design, but I am building a webapp and will have a database of locations. As the database gets big, I realized that if I want people to be able to access the database and say, for example, see points around them, it would take a long time to go through every element and check the distance from them to any given point.

Does anyone know of a way to quickly check the database, but maybe only relevant locations?

Im using python, django, and SQL if that makes any difference.

Answer 1

The way to quickly access data in a database is adding keys. But “regular“ keys operate on a strict ordering of possible values, i.e. a 1D domain. Geographical locations would require 2D access. There are basically two approaches you can use:

• Use specific 2D functionality provided by your DBMS, e.g. Spatial Extensions for MySQL.
• Use space-filling curves like the Z-order curve for your index, so that close points will correspond to a small number of small intervals in the index space.

You might also want to look at related tags, e.g. geographical-information and nearest-neighbor, or at related questions like the one about K-Nearest neighbours. And you might want to give more details on the database system you're working with.