欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

附近的人怎么计算出来的?

程序员文章站 2022-03-24 15:45:31
...
比如: 饿了么搜索附近的餐厅,qq,微信附件的人,后端怎么搜索出来的呢
数据库里面有1w条餐厅的坐标记录,当用户打开附件的餐厅的时候,搜集到用户的坐标,比如针对某一个店的话,两点的坐标,计算球面距离是好计算的,问题是,有1w条店,怎么找出来附件500米,1000米 ,2000米....

回复内容:

实现方案有很多:
1. mysql的空间数据库:
Mysql gis 空间数据库功能详解学习
2. solr空间索引天然支持按经纬度索引,按位置查询,按距离排序;
tech.meituan.com/solr-s
3. redis新版本也支持geohash了;
Redis GEO 特性简介 一般都采用Geohash算法,用一个字符串表示二维坐标,并且两个点越接近,这两个Geohash的字符串前缀相同的位数就越多(这句话可能不太严谨),这样查询的效率就会高很多。
Geohash 一般都是Geohash算法,不过这个算法的问题是可能很近的但是分在不同格子里就捞不到了,会选取周围8个格子来计算,另外就是这个算法不好按照范围搜,比如附近xx米。

第二种算法是附近xx米是一个圆,计算出圆的外接正方形的经纬度范围,就是当前位置为中心边长是xx*2的一个正方形的经纬度范围,然后在数据库里通过大于小于条件来捞落入正方形内的POI(店铺),然后,要严谨的话把四个角边缘的数据剔除(通过计算距离就可以,这时候数据量很少,不需要全表扫描计算,就很快了),精度要求不高的话,不需要剔除直接就能用了,这种做法只要把数据库中经度和纬度两个字段做索引,应付一般数据量足够了,做法也简单直白,题主只有1W条数据,这种方法妥妥的。

第三种就是利用数据库的空间索引来做,貌似MySQL本身就支持的,用R Tree实现的,效率更高。 1、把经纬度换成整数。
2、不算圆型算方型,避开乘方根号运算,直接 between 经度 and between 纬度。
3、确定了这个方内的人后,再进行乘方(但不开根号)排序就行。 查找 1000 米以内的人,数据库设计和查询如何实现这个功能? - 数据库设计 快使用开源工具,横横哈嘿,快打开源代码,嘿嘿哈横。 用mongodb,自带这类算法 大家的坐标保存起来,然后把你的坐标与大家的坐标求距离就行了。 geohash | rtree 方案:geohash + redis set

时间复杂度:O(1)

空间复杂度:O(n),挺省的,因为redis的key很短,参考下表:
附近的人怎么计算出来的?
相关标签: 2000 1000 500