Эффективный выбор ближайшей (дистанционной) записи из базы данных

Question

У меня есть база данных с 40 тысячами мест и сейчас она растет.

Предполагая, что я красная точка

Я хочу иметь возможность получитьближайшая запись как можно быстрее.

Однако расстояние до следующего элемента может быть любым.И там также может быть 0-н совпадений.Но мне нужно загрузить все 40000 результатов, когда я просто ищу 1?

Как отсортировать записи по расстоянию?Это должно быть сделано в MYSQL или PHP?Этот расчет происходит почти при каждом запросе, на пользователя, на страницу, поэтому решение должно быть быстрым.

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

Answer 1

эта проблема рассматривается в этой презентации Scribd (теория + математические формулы + Mysql): Geo Distance с MySQL

Я надеюсь, что это покрывает все, что вам нужно

Answer 2

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

Если вы хотите ясное и быстрое решение, посмотрите на Пространственные расширения MySQL .Они сделаны именно для того, что вы хотите сделать.Они поддерживают:

• Новый тип столбца 'Точка'
• Специальный тип индекса, оптимизированный для дистанционных запросов
• Оператор расстояния.

В этом руководстве приведено несколько примеров:

CREATE TABLE address (
  address CHAR(80) NOT NULL,
  address_loc POINT NOT NULL,
  PRIMARY KEY(address),
  SPATIAL KEY(address_loc)
);
CREATE TABLE cab (
  cab_id INT AUTO_INCREMENT NOT NULL,
  cab_driver CHAR(80) NOT NULL,
  cab_loc POINT NOT NULL,
  PRIMARY KEY(cab_id),
  SPATIAL KEY(cab_loc)
);

SELECT
  c.cab_driver,
  ROUND(GLength(LineStringFromWKB(LineString(AsBinary(c.cab_loc),
                                             AsBinary(a.address_loc)))))
    AS distance
FROM cab c, address a
WHERE a.address = 'Foobar street 110'
ORDER BY distance ASC LIMIT 1;

Answer 3

Нет эффективного способа найти расстояние, кроме как методом проб и ошибок.То есть, используя MySQL, вы не можете ранжировать записи по расстоянию от цели, а затем выбрать верхнюю.Лучший способ - выбрать расстояние, которое, по вашему мнению, будет в пределах ближайшей записи.Слишком большое число, и вы получите слишком много записей, слишком маленькое число, и вы не получите никаких.Допустим, вы выбрали 40 единиц.

WHERE xcoord BETWEEN n - 40 AND n + 40 AND ycoord BETWEEN n - 40 AND n + 40

Теперь у вас есть все записи с координатами внутри поля 80 x 80 с вашей целью в качестве центра (поле будет немного перекошено, есливы работаете по широте и долготе, но это не имеет значения).Теперь используйте уравнение Хаверсайна, если вы работаете с широтой и долготой, или Пифагор, если оно просто декартово, чтобы вычислить расстояние между целью и каждой из точек.

Answer 4

Создайте «ограничивающий прямоугольник» для использования в предложении WHERE в своем запросе SQL, как описано в этой статье о Movable Type (с примерами кода PHP), затем включите формулу Haversine в свой запрос для вычисленияфактические расстояния, и упорядочить результат по расстоянию ASC.Ближайшее место будет первым возвращением в наборе результатов.

Это ограничивающая рамка, которая помогает вашей производительности, потому что это означает, что вы выполняете дорогостоящий расчет расстояния только на небольшом подмножестве ваших данных

Если первоначальный запрос не возвращает никаких записей, расширьте ограничивающую рамку и повторяйте запрос до тех пор, пока не получите ответ.