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

Question

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

Answer 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的具体算法参见这里，哦不对，是这里