背景

为了向用户提供天气服务，计划接入三方天气 API，但有些三方的 API 按调用次数收费；为了节省成本，考虑使用缓存以减少调用次数。具体如何实现呢？

考虑到用户的请求参数经度和纬度两个参数，直接使用经纬度作为缓存的 key 显然不合适，因为经纬度是连续的、无限的，因此需要使用空间索引技术。

首先想到的自然是 GeoHash，它是空间索引的一种实现，将地球上的二维经纬度映射到一维的整数空间，然后使用整数空间进行索引。

GeoHash 和 Redis

资料一

https://medium.com/groupon-eng/scaling-millions-of-geospatial-queries-per-minute-using-redis-7c05bcf6b4db

GEOADD command can be used to index spatial entities in Redis.

The time complexity for this command is O(log(N)) for each item added, where N is the number of elements in the sorted set.

To perform a spatial search of entities GEORADIUS or GEORADIUSBYMEMBER can be used in Redis 3.> 2.0 (and above) and GEOSEARCH or GEOSEARCHSTORE can be used in Redis 6.2 (and above).

The time complexity for these commands is approximately O(N+log(M)) where N is the number of > elements inside the bounding box of the circular area delimited by center and radius, and M is > the number of items inside the index.

There are plenty of solutions available for implementing spatial searches.

Data structures like Quadtree, R-tree, and K-d tree can be used to index the entities.

Geospatial indexers like S2 and H3 can be used for similar queries.

疑问：

• 为什么 GEOADD 复杂度是 O(log(N))，为什么 ZADD 复杂度是 O(log(N))，两者有什么关系？
• 为什么 GEORADIUS 复杂度是 O(N + log(M)), 为什么 ZRANGE 复杂度是 O(N+log(M))，两者有什么关系？

解答：

• ZADD 与 ZRANGE 的时间复杂度：Redis中Sorted-Set时间复杂度和实战
• GEOADD 底层基于 ZADD，所以复杂度相同；
• GEORADIUS 底层基于 ZRANGE，但是更复杂，所以复杂度相同，但由于会搜索周边 9 个方格，因此系数更大；

资料二

https://www.memurai.com/blog/geospatial-queries-in-redis

Redis 不存储原始的坐标

GEOADD cities -122.34 47.61 Seattle ZRANGE cities 0 -1 WITHSCORES GEOHASH cities Seattle GEOPOS cities Seattle

Notice that we provided –122.34 as longitude and 47.61 as latitude when calling GEOADD, but > received –122.33999758958816528 and 47.61000085169597185, respectively, in return.

This is an unfortunate consequence of Redis using a 52-bit geohash to store the coordinates:

Redis does not store the raw set of coordinates that we provide, but instead decodes the internally stored geohash to generate a GEOPOS response.

资料三

• https://luoming1224.github.io/2019/04/08/%5Bredis%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%5Dredis%E4%B8%ADGeo%E5%91%BD%E4%BB%A4%E4%BB%8B%E7%BB%8D/
• https://luoming1224.github.io/2019/04/04/[redis%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0]GeoHash%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3%E5%8F%8A%E5%85%B6%E5%AE%9E%E7%8E%B0/
• https://developer.aliyun.com/article/62844#slide-16
• https://blog.huangz.me/diary/2015/annotated-redis-geo-source.html

GeoSearch 原理 geohash编码越长精度越高，相反编码越短，表示的范围越大，前缀相同的字符串表示的范围接近，根据中心点位置和搜索范围> 距离计算geohash编码的长度和geohash编码，然后搜索以该geohash编码为前缀的点以及周边８个范围内的点，返回满足要求> 的点。

函数geohashGetAreasByRadiusWGS84根据中心点位置和搜索范围距离计算geohash编码的长度和geohash编码，以及在> geohash长度编码的基础上，计算周边8个区块的geohash。

函数membersOfAllNeighbors对中心点以及它周边八个方向进行查找，找出所有范围内的元素，返回满足搜索距离范围的点。> 该函数中依次对中心点及周边8个区块调用membersOfGeoHashBox函数。

long_range和lat_range为地球经纬度的范围；hash->bits用户保存最终二进制编码结果，hash->step是经纬度划分的次> 数，在redis中该值为26，即经度/纬度的二进制编码长度为26，最终经交叉组合而成的地理位置的二进制编码为52位。Base32> 编码为每5bits组成一个字符，所以最终的GeoHash字符串为11位。

为什么是52位？因为在redis中是把地理位置编码后的二进制值存入zset数据结构中，double类型的尾数部分长度为52位。

Redis 的设计思路推演

GeoHash 除了可以对空间进行编码之外，还有两个关键特性，使得 Redis 可以通过组合 GeoHash 与 ZSET，实现空间索引功能，这两个特性是：

• 哈希可以有任意精度；

• 相近点有相似的前缀，这使得可以通过比较 geohash 值查找附近的点； 思路推演：

• 当只使用 GeoHash 时，我们可以很方便的判定两个点是否在属于同一个区域：

  • GeoHash(point1, precision=7) == GeoHash(point2, precision=7)

• 如果将 hash 值相同的点放入 set，那么就可以实现“周边搜”：

  • 首先计算要搜索点都 geohash 值；
  • 然后以该值作为 key 去查找对应的 set；

• 上述方法，需要预先指定 geohash 的精度，存储和查询时都必须以相同的精度进行，假如：

  • 存储时：sadd(GeoHash(point1, precision=7), point1);
  • 读取时：执行 smembers(GeoHash(point1, precision=6)), 由于精度不同，geohash 值不同，此时无法将 point1 查找出来;

• 假如用上述方法实现地图搜索功能，意味着，如果以 3KM 的网格存储，那么查询也必须以 3KM 进行查，这样的限制太大；

• 此时可以利用“相近点有相似前缀”特性，对 geohash 进行排序，也就是用 geohash 作为索引：

• 此时，如果存储时精度为 7，那么搜索可以支持大于等 7 的任意精度；

• 在 Redis 中，支持排序的显然是 ZSET，因此，Redis 最终在 3.2 版本选择了组合 GeoHash 和 ZSET 实现了相关的空间索引功能； 看起来很完美，但是，GeoHash 只是对大部分点来说，编码相似距离也相近，实际它存在突变性，也就是编码相邻但距离可能很远：

GeoHash 存在缺陷：https://www.jianshu.com/p/1ecf03293b9a

疑问：

• 怎么找周围 8 个区域的 GeoHash？

GeoHash 的缺陷及解决

• https://patents.google.com/patent/CN103383682A/zh
• https://www.developers.pub/article/637

Google S2/Uber h3

• https://juejin.cn/post/6921977063477870606
• https://github.com/halfrost/Halfrost-Field/blob/master/contents/Go/go_s2_CellID.md
• https://www.jianshu.com/p/3dbaf73a09af
• https://blog.csdn.net/qq_43777978/article/details/116800460
• https://blog.csdn.net/alinyua/article/details/105803546 为什么能够做网格空间索引的形状只有三角形、矩形和六边形(https://www.biaodianfu.com/uber-h3.html):

H3是一种基于网格的空间索引，但跟普通的矩形网格索引不同的是，他的每一个网格都是正六边形。为啥要选正六边形呢，因为在基于网格的空间索引中，使用的多边形的边数越多，则一个网格越近似圆形，做缓冲区查询、kNN查询什么的也就越方便。而做网格索引又要求空间能够被网格铺满，不能有缝隙。根据初中数学知识，我们知道一个多边形的内角和公式为：

𝜃=(𝑥–2)∗180∘

其中，x为多边形的边数，𝜃为多边形的内角和。则一个正多边形的每个角的角度为 𝜃𝑥=(𝑥–2)∗180∘𝑥，而如果需要多边形能够铺满空间，则在多边形的顶点相交处，设每个顶点有y个多边形相交，需要满足以下等式：

360∘𝑦=(𝑥–2)∗180∘𝑥

以上等式的求解过程我不再赘述，这个等式只有三组整数解：x=3,y=6；x=4,y=4；x=6,y=3。

因此，能够做网格空间索引的形状只有三角形、矩形和六边形，而六边形因为边数最多，最接近圆，所以理论上来说在某些场景下是最优的选择。

其它

什么是WGS84坐标系

https://zhuanlan.zhihu.com/p/97363931