Как знакомые нам сервисы Google Maps и Yandex Maps предлагают нам то, что мы обычно ищем и сортируют результаты поиска по расстоянию от текущего нашего местоположения?
Давайте разбираться на примере поиска ближайших ресторанов...
Есть два ключевых сервиса:
- Business Service:
- добавление/удаление/обновление информации о ресторанах
- предоставление детальной информации о ресторане клиентам
- Local Based Service:
- возвращение списка близлежащих ресторанов на основе текущего местоположения и заданного радиуса
Первое над чем надо подумать, над тем, как организовать хранение адресов ресторанов чтобы сервис Local Based Service мог эффективно их искать.
Хранить широту и долготу каждого ресторана? Придется во время поиска ресторанов рассчитывать расстояние между ресторанами и текущем местоположением пользователя, что не совсем эффективно.
Один из способов ускорить поиск — это использовать алгоритм геохеширования [1]
Идея заключается в следующем:
1. Делим планету на 4 части (см. диаграмму выше), где
- диапазон широты [-90, 0] = 0
- диапазон широты[90, 0] = 1
- диапазон долготы[-180, 0] = 0
- диапазон долготы[180, 0] = 1
2. Далее каждый квадрант делим еще на четыре части и по такому же принципу присваиваем биты долготы и широты.
3. В процессе добавление ресторана в нашу системы мы генерируем его геохеш и записываем в базу данных.
Когда мы захотим найти все рестораны на территории Европы и Азии мы просто можем сформировать такой запрос:
SELECT * FROM geohash_index WHERE geohash LIKE `11%`
Геохеш имеет свои недостатки и ограничения, есть и другие более эффективные алгоритмы, но это уже другая история...
СПРАВОЧНЫЕ МАТЕРИАЛЫ:
[1] Geohash: https://en.wikipedia.org/wiki/Geohash
