как WeChat"Люди неподалеку", Мэйтуань«Рестораны поблизости», Прокат велосипедов Alipay"ближайшая машина"Как она разработана и реализована?

1. Используйте базу данных, чтобы найти людей поблизости

Мы все знаем, что в любом месте на Земле можно использовать двумерные изображения.широта и долготапредставлять диапазон долготы

, диапазон широт, положительная и отрицательная широта ограничена экватором, север положителен, а юг отрицателен, а долгота положительна и отрицательна нулевым меридианомДля границы восток положительный, а запад отрицательный. Например, координаты широты и долготы памятника народным героям в Пекине равны, все положительные числа, потому что Китай расположен в северо-восточном полушарии.

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

Итак, мы можем легко написать следующий оператор псевдо-SQL:

SELECT id FROM positions WHERE x0 - r < x < x0 + r AND y0 - r < y < y0 + r

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

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

См. ниже

Мы почти можем написать следующий оптимизированный оператор SQL:

SELECT	* FROM	users_location WHERE	latitude > '.$lat.' - 1 	AND latitude < '.$lat.' + 1 AND longitude > '.$lon.' - 1 	AND longitude < '.$lon.' + 1 ORDER BY	ACOS(		SIN( ( '.$lat.' * 3.1415 ) / 180 ) * SIN( ( latitude * 3.1415 ) / 180 ) + COS( ( '.$lat.' * 3.1415 ) / 180 ) * COS( ( latitude * 3.1415 ) / 180 ) * COS( ( '.$lon.' * 3.1415 ) / 180 - ( longitude * 3.1415 ) / 180 ) 	) * 6380 ASC 	LIMIT 10 ';

Чтобы соответствовать высокопроизводительному алгоритму прямоугольной области, в таблицу данных также необходимо добавить координаты широты и долготы.двунаправленный составной индекс (x, y), что обеспечивает максимальную оптимизированную производительность запросов.

2. Краткое введение в алгоритм GeoHash

Это более распространено в промышленности и используется дляСортировать по географическому расстояниюалгоритм дляRedisЭтот алгоритм также используется. Алгоритм GeoHash будет2D широта и долготаданные сопоставляются сОдномерныйЦелое число, так что все элементы будут монтироваться на линию, а расстояние между двумерными координатами, близкими к расстоянию, будет очень близко к одномерной точке. когда мы хотим вычислить«Люди рядом», сначала сопоставьте целевое положение с этой линией, а затем получите ближайшие точки на этой одномерной линии.

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

После раздела земли нам нужно ее закодировать:

После кодирования в таком порядке, если вы внимательно присмотритесь, вы обнаружите некоторые закономерности:

• Среди всех кодов в горизонтальном направлении,2 и 4 одинаковые, например, первая строка первой строки0101и второй0111, их 2-я и 4-я позиции обе1;
• Из всех кодов, стоящих вертикально,Биты 1 и 3 увеличиваются, например, первая строка первой строки0101, если 1-й и 3-й бит вынесены отдельно, то есть00, аналогично смотрим вторую строку в первой строке0111, таким же образом подбираются 1-й и 3-й биты как01, что бывает00увеличить на единицу;

По такому правилу мы кодируем каждый квадратик в определенном порядке, чтобывыгодаочевидно: каждая координата элемента может быть какУникально идентифицируетНа этой закодированной карте ни один из них неПоказать конкретные места, поскольку территория общая, я могу сказать, что я рядом с парком, но вы не будете знать, где именно.

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

,через это целое число мы можем восстановить координаты элемента.Чем длиннее целое,тем меньше программа потери восстанавливаемого значения координат. за"Люди неподалеку"Для этой функции потеря бита долготы незначительна.

НаконецBase32

Операция кодирования превращает его в строку, например, приведенная выше строка становитсяwx4g0ec1.

существуетRedisВ, широта и долгота использования52Целое число битов кодируется и помещается в zset.valueЭлементарноkey,scoreдаGeoHashиз52Битовое целое значение. zset'sscoreХотя это число с плавающей запятой, для52Для целых значений бит его можно хранить без потерь.

3. Использование гео в Redis

Далее цитируется из

Ссылка 1 - Глубокие приключения Redis

в настоящее время используетRedisпровестиГео-запрос, мы должны иметь в виду, что его внутренняя структура на самом деле простоzset(skiplist). через zsetscoreСортировка, чтобы получить другие элементы рядом с координатами

, поставивscoreИсходные координаты элемента можно получить, восстановив его до значения координат.

Redis предоставляет всего 6 команд Geo, которые легко освоить.

Увеличивать

geoaddКоманда содержит имя коллекции и несколько троек имен широты и долготы.Обратите внимание, что здесь можно добавить несколько троек.

127.0.0.1:6379> geoadd company 116.48105 39.996794 juejin(integer) 1127.0.0.1:6379> geoadd company 116.514203 39.905409 ireader(integer) 1127.0.0.1:6379> geoadd company 116.489033 40.007669 meituan(integer) 1127.0.0.1:6379> geoadd company 116.562108 39.787602 jd 116.334255 40.027400 xiaomi(integer) 2

Но это очень странно. Redis напрямую не предоставляет команды удаления Geo, но мы можем управлять данными Geo с помощью команд, связанных с zset, поэтому можно использовать удаление элемента.zremкоманда.

расстояние

geodistДирективу можно использовать для вычисления расстояния между двумя элементами, содержащими имя коллекции, 2 имени и единицы измерения расстояния.

127.0.0.1:6379> geodist company juejin ireader km"10.5501"127.0.0.1:6379> geodist company juejin meituan km"1.3878"127.0.0.1:6379> geodist company juejin jd km"24.2739"127.0.0.1:6379> geodist company juejin xiaomi km"12.9606"127.0.0.1:6379> geodist company juejin juejin km"0.0000"

Мы видим, что Nuggets ближе всего к Meituan, потому что они оба находятся в Wangjing. Единицей расстояния может бытьm,km,ml,ft, которые представляют метры, километры, мили и футы соответственно.

получить позицию элемента

geoposКоманда может получить координаты широты и долготы любого элемента в коллекции, а также получить несколько одновременно.

127.0.0.1:6379> geopos company juejin1) 1) "116.48104995489120483" 2) "39.99679348858259686"127.0.0.1:6379> geopos company ireader1) 1) "116.5142020583152771" 2) "39.90540918662494363"127.0.0.1:6379> geopos company juejin ireader1) 1) "116.48104995489120483" 2) "39.99679348858259686"2) 1) "116.5142020583152771" 2) "39.90540918662494363"

Заметим, что полученные координаты широты и долготы иgeoaddВ введенных координатах небольшая ошибка, причина в том, чтоGeohashОдномерное отображение двумерных координат происходит с потерями, и будут небольшие различия в значениях, восстановленных посредством отображения. за"Люди неподалеку"Для этой функции эта ошибка вообще не проблема.

Получить хеш-значение элемента

geohashВы можете получить закодированную строку широты и долготы элемента, как упоминалось выше, этоbase32кодирование. Вы можете использовать это закодированное значение, чтобы перейти кhttp://geohash.org/${hash}для прямого позиционирования вGeohashСтандартное закодированное значение .

127.0.0.1:6379> geohash company ireader1) "wx4g52e1ce0"127.0.0.1:6379> geohash company juejin1) "wx4gd94yjn0"

давайте откроем адресhttp://geohash.org/wx4g52e1ce0, и обратите внимание, что карта указывает на правильное местоположение:

Очень хорошо, это место, очень точно.

близлежащие компании

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

# 范围 20 公里以内最多 3 个元素按距离正排，它不会排除自身127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 asc1) "ireader"2) "juejin"3) "meituan"# 范围 20 公里以内最多 3 个元素按距离倒排127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 desc1) "jd"2) "meituan"3) "juejin"# 三个可选参数 withcoord withdist withhash 用来携带附加参数# withdist 很有用，它可以用来显示距离127.0.0.1:6379> georadiusbymember company ireader 20 km withcoord withdist withhash count 3 asc1) 1) "ireader" 2) "0.0000" 3) (integer) 4069886008361398 4) 1) "116.5142020583152771" 2) "39.90540918662494363"2) 1) "juejin" 2) "10.5501" 3) (integer) 4069887154388167 4) 1) "116.48104995489120483" 2) "39.99679348858259686"3) 1) "meituan" 2) "11.5748" 3) (integer) 4069887179083478 4) 1) "116.48903220891952515" 2) "40.00766997707732031"

КромеgeoradiusbymemberДиректива запрашивает близлежащие элементы на основе элемента,RedisОна также обеспечивает запрос близлежащих элементов на основе значений координат. Эта команда более полезна. Она может вычислять «близлежащие автомобили», «близлежащие рестораны» и т. д. на основе позиционирования пользователя. его параметры иgeoradiusbymemberВ основном то же самое, за исключением изменения целевого элемента на координаты широты и долготы:

127.0.0.1:6379> georadius company 116.514202 39.905409 20 km withdist count 3 asc1) 1) "ireader" 2) "0.0000"2) 1) "juejin" 2) "10.5501"3) 1) "meituan" 2) "11.5748"

Меры предосторожности

В картографическом приложении могут быть миллионы данных об автомобилях, ресторанах и людях.RedisизGeoструктуры данных, они будутвсе в одномколлекция zset. существуетRedisВ кластерной среде коллекция может быть перенесена с одного узла на другой.Если данные одного ключа слишком велики, это сильно повлияет на миграцию кластера.В кластерной среде объем данных соответствующий одному ключу не должен превышать 1М. В противном случае миграция кластера зависнет, что повлияет на нормальную работу онлайн-сервисов.

Поэтому здесь предлагаетсяGeoИспользование данныхРазвертывание отдельного экземпляра Redis, не используйте кластерную среду.

Если объем данных превышает 100 миллионов или даже больше, необходимоGeoДанные разбиты по странам, провинциям, городам и даже по районам в мегаполисах. Это может значительно уменьшить размер одной коллекции zset.

Связанное Чтение

1. Redis(1) — 5 основных структур данных —Уууу, мы должны думать об этом все время.com/2020/02/28/…
2. Redis(2) - пропустить таблицу -Уууу, мы должны думать об этом все время.com/2020/02/29/…
3. Redis(3) — подробное изучение распределенных блокировок —Уууу, мы должны думать об этом все время.com/2020/03/01/…
4. Reids(4) - Волшебный HyperLoglog для решения статистических задач -Уууу, мы должны думать об этом все время.com/2020/03/02/…
5. Redis(5) — фильтрация данных на миллиардном уровне и фильтр Блума —Уууу, мы должны думать об этом все время.com/2020/03/11/…

использованная литература

1. «Redis Deep Adventure» — Цянь Венпин / Автор —book.Douban.com/subject/303…
2. Запрос широты и долготы MySQL и пример учебника по оптимизации производительности запросов sql для пользователей поблизости в пределах 2 км -Блог Woohoo.cn на.com/yurt kids/afraid/41…
3. Принцип и реализация алгоритма Geohash -woohoo.brief.com/afraid/2 возражение 0 есть 12 ой...
4. Объяснение обучения алгоритму GeoHash, анализ и анализ принципов -zhuanlan.zhihu.com/p/35940647

• Эта статья была включена в мою серию Github Programmer Growth.[Больше, чем Java], изучение не только кода, добро пожаловать в звезду:GitHub.com/Мы должны продолжать думать/mor…
• Личный публичный аккаунт:wmyskxz,Личный независимый блог доменных имен: wmyskxz.com, настаивайте на оригинальном выводе, отсканируйте приведенный ниже код, чтобы следовать ему, 2020, расти вместе с вами!

Большое спасибо за ваши талантыпосмотреть здесь, если вы считаете, что эта статья хорошо написана, подумайте"У меня нет трех сердец" это что-тоесли,Ставьте лайки, подписывайтесь, делитесь и оставляйте сообщения!

Творить не легко Ваша поддержка и признание - самая большая мотивация для моего творчества Увидимся в следующей статье!

В этой статье используетсяmdniceнабор текста