打开美团看看附近店铺有没有好吃，排序按照距离优先，还有附近几公里之内的店铺。想了解这个功能怎么实现的，查了网上资料，得到的常用的算法是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.5km 附近展示店铺。假设平台有一张表，简单的3个字段(店铺id，店铺的经度，店铺的维度)，当用户要查询的时候，用什么方案能快速给用户响应结果呢？这篇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小结
Geohash很好的利用Z阶曲线进行编码，可将二维或者多维空间里的所有点都转换成一维曲线，并且Z阶曲线还具有局部保序性。Z阶曲线通过交织点的坐标值的二进制表示来简单地计算多维度中的点的z值。一旦将数据被加到该排序中，任何一维数据结构，例如二叉搜索树，B树，跳跃表或（具有低有效位被截断）哈希表都可以用来处理数据。通过Z阶曲线所得到的顺序可以等同地被描述为从四叉树的深度优先遍历得到的顺序，搜索查找邻近点比较快。可以说基本满足互联网附近的功能业务。
S²
S²算法讲解与对比
Geohash有 12 级之分，从 5000km 到 3.7cm，每一级的变化比较大。Geohash字符串就比较难选，选择不好每次判断可能就还需要取出周围的 8 个格子再次进行判断。而S²有 30 级之分，从 0.7cm² 到 85,000,000km² 。中间每一级的变化都比较平缓，接近于 4 次方的曲线，所以选择精度不会出现Geohash选择困难的问题。Geohash需要 12 bytes 存储，而S²的存储只需要一个uint64即可。S²库里面不仅仅有地理编码，还有其他很多几何计算相关的库。地理编码只是其中的一小部分。S2还可以解决各种向量计算，面积计算，多边形覆盖，距离问题，球面球体上的问题，解决多边形覆盖的问题。比如给定一个城市，求一个多边形刚刚好覆盖住这个城市。
场景选择
关于这个算法，个人感觉更偏向于GIS方面使用，不管是降维曲线的选择还是其背后的数学原理都是比geohash复杂得多。geohash适合附近的店铺之类的非精确度查询的业务使用，S²更适合高德地图、优步和GIS方面的业务使用。代码方面 C++、java、python 都是实现的，可自行搜索相关资料。
