Задача достаточно тривиальная, но удобного решения я не нашёл.

Итого есть таблица например магазинов вида:

Имя магазина ---- Широта --- Долгота

Задача: если я живу в координатах X,Y то как мне найти 10 ближайших ко мне магазинов?

Задача в принципе решена, т.е. формулы для рассчёта расстояния между координатами есть, но... таблица очень большая - десятки миллионов записей, подставлять в формулу 10 миллионов значений - очень долго... Наверное, надо перевести координаты в полярные (сферические) взять какую-то условную длину от точки и проиндексировать её, или несколько таких длин... Может как-то можно и по другому... 

Я так понимаю, что в таком случае, придется все равно каждый раз вычислять радиус от заданной точки.

Вот первое что приходит в голову, а почему бы не ввести еще временную координату, я про часовой пояс. Сначала делать выборку по часовому поясу во временную таблицу, а потом уже в ней искать по координатам. 

Есть другой выход. Отсортировать список сначало по координате X, затем по координате Y.  Твои Координаты известны. 
Составляеш множество магазинов которые близки по координате X. Затем множество магазинов близких по координате Y. Делаеш "логическое И" двух множеств и получаеш список магазинов близких к твоим координатам.   

Vit, работа идёт при помощи базы данных? или обработка "вручную"?

Раз карта - плоскость, то может разбить на квадраты? 
 

После непродолжительного гугления обнаружил следующую статью:
Nearest Neighbour Queries.
К сожалению, там описывается только алгоритм, но не реализация с помощью РСУБД.
Также выяснилось, что некоторые базы данных имеют расширения для задач GIS и spatial search, например Oracle и PostgreSQL. 

MS SQL Server



Карта шар... Земной шар...



Это интересная идея надо подумать...
 

Ничего хорошего не получится в общем случае - квадраты на шаре так себе квадраты. Впрочем  если надо выбрать 10 из 10 миллионов на глобусе (Антарктида и Арктика, надо понимать, не в счет) - сойдет.

Навскидку - я бы пошел таким путем: разбиение на перекрывающиеся области, форма их - в первом приближении квадраты. Причем перекрытие соседних областей составляет порядка 2/3 стороны (т.е. каждая область как бы состоит из 9 малых "суб-областей"), а количество точек (магазинов) в области порядка 400, причем в каждой "суб-области" не менее 20 (это фактически параметры деления на области, которые могут быть квадратами или прямоугольниками, не обязательно одинакового размера). Тогда можно сразу проводить поиск только в той области, где заданная точка в центральной "суб-области". 

Раз используешь СУБД, посмотри, как там реализована работа с пространственными объектами.
Что касается сортировки и быстрого поиска, см. R-tree, Quad-tree, k-D-tree. 
А начсчёт формы земли (а это кстати совсем не сфера) и вычисления расстояний см. инфу о проекции Гаусса-Крюгера и др. 

Здесь однозначно делить на прямоугольники и субпрямоугольники  величина прямоугольника может вариировать в зависимости от густонаселённости.
Оптимальное количество ступеней найти экспериментальным путём (думаю 50 будет более чем достаточно). При выборке искать в квадратах-соседях.

 

Вот, набросал алгоритмик. Совсем без вычислений 
Аж интересно стало  С удовольствием бы с базой поиграл )))


таблица "rectangles"
-------------------------------------
| id_rectangle | parent_id_rectangle | level | x1 | x2 | y1 | y2 |


таблица neighbours
-----------------------------------
| id_rectangle | id_neigbour |


таблица shops
--------------------------------
| id_shop | id_rectangle (самый низкий уровень)|




Теперьмы нашли достаточное количество самых близких магазинов и можем мерить расстояния уже только между ними. Количество сокращается с нескольких миллионов до нескольких десятков. Океаны можно на квадраты не делить, только континтнты и вообще только места, где магазы есть. Просто надо правильно расставить соседей в таблице.
          

Присоединённый файл ( Кол-во скачиваний: 5 )
 neigbourhood.gif 14,33 Kb

Вообще, лучше на тре/шестиугольники делить. Так соседи всегда будут точно определены.. 

Для нахождения ближайшей точки из заданного множества обычно используются диагораммы Вороного (триангуляция Делоне --- двойственная операция). В сети можно найти кучу готовых реализаций и описаний (в том числе на русском). Для поиска 10 ближайших точек алгоритм нужно немного доработать. 

Задача оптимизации поиска на карте решается только пространственным индексированием. Индексы можно придумать самые разные. Самый простой способ, действительно, разбиение на одинаковые прямоугольники (неважно что на шаре они не очень прямоугольные, главное просто определяется попадание). Этот способ самый простой по реализации и скромный по занимаемой памяти. Но не очень эффективный, ессли речь идет о миллионах объектов, да еще очень неравномерно распределенных. 
Чуть более сложный способ - дерево - двоичное или тернарное, это уже как не в лом писать. Принцип - те же квази-квадраты, но не одинаковые, а уменьшаемые в 2\4 раза по мере углубления в дерево. Т.е. как только объектов в большом квадрате становится больше чем некоторое N, разбиваем его.
Я бы начала с четвертушек шарика.

Вариант с сортировкой по x, потом по y, ничего не даст...

Есть вероятность что в СУБД уже есть встроенное расширение для работы с пространственными данными, тогда там должно быть реализовано индексирование.

Добавлено @ 19:40 
sergej.z, уже примерно это написал, сразу не заметила. Только не согласна насчет тре\шестиугольников, градусные квадраты эффективнее.