Обычно это делается с использованием R-дерева структуры данных
В dbs, таких как mysql или postgresql, есть ГИС-модули, использующие r-дерево под капотом для быстрого поиска местоположений в определенной близости от точки на карте.
С http://en.wikipedia.org/wiki/R-tree:
R-деревья - это древовидные структуры данных, которые
похожи на B-деревья, но используются
для методов пространственного доступа, то есть для
многомерная индексация
Информация; например, (X, Y)
координаты географических данных.
обычное реальное использование R-дерева
может быть: «Найти все музеи в течение 2
километров (1,2 мили) моего нынешнего
место».
Структура данных разделяет пространство с
иерархически вложенный, и, возможно,
перекрытие, минимальное ограничение
прямоугольники (MBR, иначе известные как
ограничивающие прямоугольники, то есть "прямоугольник", что
«R» в R-дереве обозначает).
R-дерево Priority (PR-дерево) - это вариант с максимальным временем работы:
"O((N/B)^(1-1/d)+T/B) I/Os, where N is the number of d-dimensional (hyper-)
rectangles stored in the R-tree, B is the disk block size, and T is the output
size."
На практике большинство реальных запросов будут иметь гораздо более быстрое среднее время выполнения.
Кстати, в дополнение к другому опубликованному коду, есть несколько интересных вещей, таких как SpatiaLite и Модуль SQLite R-tree