类似“附近的人”功能,大量数据如何存储和快速查询?

_helloo
  • 154

如题,类似微信这样的大量数据,像附近的人、摇一摇这样的功能,数据存储和查询在那么短时间内是怎么做到的?

回复
阅读 8.4k
1 个回答
✓ 已被采纳

GeoHash粗过滤加勾股定理细过滤,千万级记录可以在几毫秒内搞定。

GeoHash的基本思路是把地图划成块,每个块对应一个Hash code,这样你可以快速的用这个hash code对范围做一个大致的过滤。
实际中GeoHash的做法是这样的:
1、首先把地图按赤道和0经度线划成4块,左上、右上、左下、右下的Hash code分别是二进制00、01、10、11,然后把每块继续四等分,小块的Hash code就是上一级的Hash code加上本级的这两个二进制位,继续等分下去,你就可以得到不同范围不同位置的很多个Hash code。
2、每一级Hash code都对应了一个块的大小,这个尺寸可以用来做粗过滤
3、把地图上需要索引的点按所属的块的Hash code做索引。

查找时,目标点和搜索距离一起可以得到一个合适层级的Hash code,把这个Hash code周围的8个块都算出来,粗筛的范围就这一共9个块。
遍历这9个块中所有地点,每个地点按照勾股定理算距离(如果你想细算就用球面距离公式),你就得到了一个精确列表。

使用这个方法有些地方需要注意:
1、GeoHash是按照经纬度范围生成的,不是实际距离,所以针对不同纬度下的点要做一些修正。
2、由于维度在两极会回绕,所以对于南北极点附近的点,基本上你就要做一个全表扫描了,对于日界线附近的点情况也类似,当然除非你做地理学术方面的应用,这种情况基本可以忽略。

GeoHash的具体算法参见这里,哦不对,是这里

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏