Redis Geo

我们知道从 Redis 3.2 版本开始呢，推出了 GEO 这种表达地理空间的数据类型，使用如下指令，就可将某一对象的经纬度信息写入 Redis 当中：

geoadd key lng lat member [lng lat member ...]

• key 为地理空间数据的键名称，对应Redis数据结构中的ZSET 的键（不是说GEO咋变成了ZSET？请看后续）

• lng 表示经度

• lat 表示纬度

• member 表示此经纬度对应的成员

那么，有了这个数据类型，我们就可以很轻松地实现一些功能，比如：

• 查找附近的人？附近的店铺？附近的共享单车？附近的共享充电宝？

• 距离我最近的xxx？

Redis 也提供了非常丰富的指令，帮助我们实现这些功能，比如：

geosearch key fromlonlat lng lat byradius radius unit [withcoord] [withdist] [withhash] [count n] [asc|desc]

geosearch key frommember member byradius radius unit [withcoord] [withdist] [withhash] [count n] [asc|desc]

• key 为数据键名

• fromlnglat lng lat 表示根据坐标搜索，lng lat 为搜索原点

• frommember member 表示根据成员搜索，member 为搜索原点

• byradius radius unit 表示搜索半径，radius 为数值，unit 为单位

  • radius 为数值，如 500

  • unit 为单位，可取值 m | km | mi | ft 分别对应米、千米、英里、英尺

• withcoord 可选，返回结果包含坐标

• withdist 可选，返回结果包含与原点距离

• withhash 可选，返回包含排序用的原始 Geohash 值

• count n 可选，限制返回结果数量，如 count 1 返回1个

• asc|desc 可选，按与原点距离由近到远（asc）或由远到近（desc）排序

OK，到这完全满足前面提到的场景了，那么，Redis Geo 是如何实现这些功能呢？它背后的逻辑到底如何？

相信你已经关注到了一个名词“Geohash”，是的，Redis 通过 Geohash 实现地理空间搜索。

Geohash

是什么

AI 味十足的一段定义，不过却也说清楚了 Geohash 的定义和作用。

Geohash 是一种将二维坐标编码得到一维字符的算法，编码结果表示为一块地理网格，注意，坐标表示一个精确的点，而编码得到的字符串表示的是一个区域，是一个面，通过字符串前缀匹配，相似度越高的坐标在地理空间上越近。

有个这个基本特征之后，就可以利用这个规则来做地理空间上的搜索、比较等功能。

地理知识

我们都知道，地球是一个球体，地球表面经线纬线纵横交错，组成现在最基础的全球坐标体系和时区体系。

• 经线，以经过伦敦格林尼治天文台的经线作为 0 度经线（又叫本初子午线），以 0 度经线为基准：

  • 往东为东半球，称为东经，经度范围在 (0°, 180^°] 之间

  • 往西为西半球，称为西经，经度范围在 [-180°, 0°) 之间

• 纬线，以赤道作为 0 度纬线：

  • 往北为北半球，称为北纬，维度范围在 (0°, 90°] 之间，北纬90°即为北极点

  • 往南为南半球，称为南纬，维度范围在 [-90°, 0°) 之间，南纬90°即为南极点

编码算法

核心思想

Geohash 的核心思想是：区间二分

1. 将坐标体系看做一个二维平面网格

2. 利用二分法，将定位坐标落到网格

3. 根据网格经纬度与定位坐标的关系，计算得到一个二进制位

   1. 经度落在二分右区间取 1 否则取 0

   2. 维度落在二分右区间取 1 否则取 0

4. 该网格内部继续细分坐标得到精确度更高一层的平面网格

5. 再利用二分法，将坐标落入网格，计算得到下一个二进制位

6. 递归，直到达到目标精度

7. 最终递归的层级，就是二进制编码的位数，从左往右，得到二进制编码

二进制编码

举个栗子：定位以腾讯大厦，维度 22.540366 经度 113.934559（别问找不到企鹅岛地址...）

经度二进制编码，

与中点比较

维度编码同理，取坐标维度 22.540366 与维度范围 [-90°, 90°] 计算，最终得到编码

经度：11010 00100 00010 表示 [113.92822265625°, 113.939208984375°] 经度范围

维度：10100 00000 00111 表示 [22.5384521484375, 22.5439453125] 维度范围

二进制合并

得到经纬度二进制编码后，从第 0 位开始，依次交叉合并，偶数位放经度，奇数位放维度

经度: 1  1  0  1  0  0  0  1  0  0  0  0  0  1  0
维度:   1  0  1  0  0  0  0  0  0  0  0  0  1  1  1

结果: 111001100000001000000000011101

Base32 编码

合并二进制后，为了压缩长度，再将二进制编码成 Base32 字符

十进制:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Base32:  0 1 2 3 4 5 6 7 8 9 b  c  d  e  f  g

十进制:  16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Base32:  h  j  k  m  n  p  q  r  s  t  u  v  w  x  y  z

二进制 5 位一组，每组对应 Base 32 一个字符，进制转换

二进制: 11100 11000 00001 00000 00000 11101
十进制: 28    24    1     0     0     29
Base32: w     s     1     0     0     x

最终，维度 22.540366 经度 113.934559 的 Geohash 值为：ws100x

Redis Geo 实现原理

前文提到 Zset ，Geo 其实就是通过包装 Zset 来实现的，所以严格来说 Geo 也不能称为一种新的数据类型，那么， Zset 如何存储地理关系呢？

Redis 将经纬度通过 Geohash 算法转换成一个 52 位的二进制编码，再转成十进制的一个大整数，当做排序权重 sorce ，这样即可存储空间顺序关系。

当需要做范围搜索时，将搜索区域的坐标转换得到 sorce 取值范围，在 Zset 中进行范围搜索即可。

Geohash 局限性

单位经度距离

我们知道，地球是个球体，赤道上的单位经度实际距离是最大的，越靠近两极地维度上的单位经度实际距离会逐渐减小

区间边界问题

如图示

A 与 B 在同一个区域内，它们的编码相似度更高，但实际距离更远；

A 与 CDE 不在同一个区域内，它们编码相似度更低，但实际距离更近。

解决办法

对于这两个问题，可以采取一些办法，来提高计算或搜索的经度，比如：

• 可以使用更高的经度，经度越高，覆盖的区域面积越小，误差自然就越小；

• 搜索时，连带相邻的8块区域一起搜索，再计算对象之间的实际距离；

• 先扫一遍，得到多个坐标，再通过其他地理空间算法，如 Haversine 、Vincenty，计算坐标之间的实际距离。

以上。