Быстрый поиск в БД ближайших меток

Пост в архиве.

Дмитрий

24 ноября 2011, 10:11

Здравствуйте!

Почему-то нигде не смог найти обсуждение этого, как мне кажется, первоочередного вопроса.

Пусть в БД хранится, скажем, 1000 меток. Как быстро выбрать ближайшие, чтобы отобразить их на том участке карты который смотрит пользователь?

Единственное что нашел: считать расстояние между центром карты и каждой(!) хранящейся точкой:

SELECT address, name, lat, lng, ( 6371 * acos( cos( radians('%s') ) * cos( radians( lat ) ) 
* cos( radians( lng ) - radians('%s') ) + sin( radians('%s') ) * sin( radians( lat ) ) ) ) AS distance 
FROM markers HAVING distance < '%s' ORDER BY distance LIMIT 0, 20

Или надо капать в сторону кластеризации? Как правильно?

5 комментариев

Авторизуйтесь, чтобы оставить комментарий

Sergey Konstantinov

28 января 2016, 05:31

Существуют специальные SPATIAL расширения баз данных, например, PostGIS для PostgreSQL. Попробуйте посмотреть в эту сторону.

Михаил Королев

28 января 2016, 05:31

Если не нужна большая точность а именно выбрать top 10..20..100 ближайших - имхо можно вообще не считать расстояния а использовать простую разницу координат, полагая что она пропорциональна расстоянию. единственное что придётся предусмотреть - переход через 0.

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

thekashey

28 января 2016, 05:31

Во первых в Posgress, MySQL и даже в Oracle есть тип данных spatial.

В общем случае это некая метафизический формат данных которых хранит сущьности определенные в 2д пространстве.

Одновременно может хранить и точку, и полигон и полигон с дыркой. При этом правильно отработать эту самую дырку.

Если у вас 1000 точек и есть интерес к красивому и правильному програмингу - поиск в помощь.

Если точек или больше, или меньше, или вас немного не устраивает что spatial во всех базах ЖУТКО тормозит :)

thekashey

28 января 2016, 05:31

То давайте работать по старинке.

вариант 1. Записываем в базу lat и lng

Выбор из базы - SELECT ... WHERE lat between y1 and y2 and lng between x1 and x2

Где эти x1-y2 есть bounds видимого куска карты.

И надо будет не забыть повесить двойной индекс на эти два поля.

Работает изумительно для относительно больших обьемов данных( десятки тысяч записей )

Минус - обновление с сервера при каждом драге карты.

Тут можно решить либо через расширение тех bounds что отдаются на сервер, а потом не делать обновления пока не вышли из зоны "расширения".

Либо, лучше, как-то фиксировать зоны запросов. Чтобы всегда запрашивались дискретные куски. Примерно так как на карте тайлы.

Об остальном можно пояндексить интернеты, например хабрахабр.

mkw

28 января 2016, 05:31

Что то запрос не срабатывает подозреваю нужно конвертировать даные?

SELECT* frommap_cord WHERE cord_lat between 76.718215942382and 77.27096557617 and cord_lon between 43.339123639687 and 43.18330624940;