Ситуация и цель
Представьте себе систему поиска пользователей, которая обеспечивает поиск близости от собственной позиции пользователя, которая определяется десятичной комбинацией широты и долготы. Например, позиция жителя Атланты будет представлена как 33.756944,-84.390278
, и поиск по периметру этим пользователем должен выявить других пользователей в его районе в радиусе 10 миль, 50 миль и так далее.
Функция с табличным значением вычисляет расстояния и предоставляет пользователям соответствующие данные, упорядоченные по возрастанию расстояния до пользователя, начавшего поиск. Это всегда живой запрос, сложный и частый. Теперь мы хотим создать какое-то кэширование, чтобы уменьшить нагрузку.
На пути к решениям
До сих пор все пользователи были сгруппированы по целочисленной части их широты/долготы. Идея состоит в том, чтобы создать файлы кеша со всеми пользователями из квадрата сетки, чтобы доступ к соответствующему файлу кеша был бы легким. Если квадрат сетки содержит больше пользователей, чем должно быть в файле кэша, квадрат делится на четыре части или дополнительно делится на восемь частей и так далее. Для полного использования квадрата и его кэш-файла предполагается несколько перекрывающихся квадратов. Одним из недостатков этого подхода является то, что создание сетки и четвертование мегаполисов с высокой плотностью населения и обширных сельских районов в наложенные файлы кэша может быть неоптимальным.
Читая дальше, я наткнулся на такие темы, как поиск ближайших соседей, манхэттенское расстояние и древовидные методы разделения пространства, такие как дерево k-d, дерево квадрантов или двоичное разделение пространства. Кроме того, SQL Server предоставляет свои собственные географические типы данных и функции (хотя я думаю, что чисто математический FLOAT
способ имеет достаточную производительность). И, конечно же, суть заключается в том, чтобы сделать ориентированный на пользователя поиск близости кешируемым.
Вопрос!
Я не нашел много ресурсов по этому вопросу, но я уверен, что я не первый с этим планом. Помните, речь идет не о поиске, а о кешировании.
- Могу ли я отказаться от своего подхода?
- Существуют ли способы выгодного разделения пользователей на географические подразделения равного размера?
- Существует ли наилучшая практика хранения пространственной информации о пользователе для эффективного поиска близости?
- Что вы думаете об упомянутых выше методах (деревья квадрантов и т. д.) и как бы вы связали их с кэшированием?
- Знаете ли вы пример успешного кэширования поиска по близости для конкретного пользователя?