附近的商店

看着每天的感染数据在下降，上海解封的日子快到了。打开美团看看附近店铺有没有好吃，准备解封大吃特吃一顿。排序按照距离优先，还有附近几公里之内的店铺。想了解这个功能怎么实现的，查了网上资料，得到的常用的算法是 geohash 和 S2。

Geohash

https://www.jianshu.com/p/2fd0cf12e5ba
https://halfrost.com/go_spatial_search/
https://phrozen.github.io/geohash/

第二个链接比较详细地介绍了 geohash 的原理（学习一下Z 阶曲线），第三个链接用于展示全球的 geohash 编码地图。比如说我在 wtw3x2，该编码是通过规则定义的 base32 转换的，通过反向转换可以得到我的经纬度，而 geohash 就是定义了这个规则，将经纬度的二维数据转换成一维数据，便于存储以及后续的计算。

代码参考链接1

在实际应用当中，美食店的位置坐标都会在注册时提供给平台，当我要查找附近的饭店的话，软件获得我的坐标然后在我附近的1.5km附近展示店铺。假设平台有一张表，简单的3个字段(店铺id，店铺的经度，店铺的维度)，当用户要查询的时候，用什么方案能快速给用户响应结果呢？

https://www.cnblogs.com/mgbert/p/4146538.html

这篇2014年的文章，介绍了自己使用 mysql 处理上面的问题，sql 很好的使用勾股定理以及对经纬度的数据做双向复合索引，这个方案在2014年4G刚普及那会是没什么问题的。不过放在2022年就不是很适合了，不过好在有其他的比较好的方案，redis 也有 geohash 功能，在速度方面可以比 mysql 方案要好。

geoadd # 增加坐标信息
geodist # 计算两点的距离
geopos # 获取集合中元素的经纬度坐标
geohash  # 获取元素 hash 值
georadiusbymember # 查询指定元素附近的其它元素

2021年美团的活跃商家数量达880万，加上用户的数据可能会有千万或上亿条。如果使用 Redis 的 Geo 数据结构，它们将全部放在一个 zset 集合中。在 Redis 的集群环境中，节点数据的同步以及迁移，当遇到单个 key 的数据过大，会对集群的产生较大的影响，在集群迁移时会出现卡顿现象，影响线上服务的正常运行。所以官方建议 Geo 的数据使用单独的 Redis 实例部署，不使用集群环境。

但是在实际业务环境中，不能单点部署时，就需要对 Geo 数据进行拆分，按国家、省、市等进行拆分。在人口特大城市甚至可以按区（例如：上海浦东浦西鸳鸯锅）拆分，这样就可以显著降低单个 zset 集合的大小。使用redis做缓存查询，数据库做数据持久化，增加定时任务用于redis和数据库的店铺位置信息进行增删改 *** 作，保证一定时间内两边数据一致。

Geohash 利用 Z 阶曲线进行编码，可将二维或者多维空间里的所有点都转换成一维曲线，并且 Z 阶曲线还具有局部保序性。Z 阶曲线通过交织点的坐标值的二进制表示来简单地计算多维度中的点的z值。一旦将数据被加到该排序中，任何一维数据结构，例如二叉搜索树，B树，跳跃表或（具有低有效位被截断）哈希表都可以用来处理数据。通过 Z 阶曲线所得到的顺序可以等同地被描述为从四叉树的深度优先遍历得到的顺序，搜索查找邻近点比较快。可以说基本满足互联网附近的功能业务。

S²

Geohash 有12级，从5000km 到 3.7cm，每一级的变化比较大。Geohash 字符串就比较难选，选择不好每次判断可能就还需要取出周围的8个格子再次进行判断。而 S2 有30级，从 0.7cm² 到 85,000,000km² 。中间每一级的变化都比较平缓，接近于4次方的曲线，所以选择精度不会出现 Geohash 选择困难的问题。

Geohash 需要 12 bytes 存储，而S2 的存储只需要一个 uint64 即可。S2 库里面不仅仅有地理编码，还有其他很多几何计算相关的库。地理编码只是其中的一小部分。S2 还可以解决各种向量计算，面积计算，多边形覆盖，距离问题，球面球体上的问题，解决多边形覆盖的问题。比如给定一个城市，求一个多边形刚刚好覆盖住这个城市。

关于这个算法，个人感觉更偏向于 GIS 方面使用，不管是降维曲线的选择还是其背后的数学原理都是比 geohash 复杂得多。geohash 适合附近的店铺之类的非精确度查询的业务使用，S2 更适合高德地图，优步和 GIS 方面的业务使用。代码方面 C++、java、python 都是实现的，可自行搜索相关资料。