前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、引入

地图元素的位置数据使用二维的经纬度表示，经度范围 (-180, 180]，纬度范围 (-90, 90]，纬度正负以赤道为界，北正南负，经度正负以本初子午线 (英国格林尼治天文台) 为 界，东正西负。比如掘金办公室在望京 SOHO，它的经纬度坐标是 (116.48105,39.996794)， 都是正数，因为中国位于东北半球。

当两个元素的距离不是很远时，可以直接使用勾股定理就能算得元素之间的距离。我们 平时使用的「附近的人」的功能，元素距离都不是很大，勾股定理算距离足矣。 不过需要注 意的是，经纬度坐标的密度不一样 (经度总共 360 度，纬度总共 180 度)，勾股定律计算平方差时之后再求和时，需要按一定的系数比加权求和。

问题1：现在，如果要计算「附近的人」，也就是给定一个元素的坐标，然后计算这个坐标附近的其它元素，按照距离进行排序，该如何下手? 如果现在元素的经纬度坐标使用关系数据库 (元素 id, 经度 x, 纬度 y) 存储，你该如何计算?

答案： 首先，你不可能通过遍历来计算所有的元素和目标元素的距离然后再进行排序，这个计算量太大了，性能指标肯定无法满足。一般的方法都是通过矩形区域来限定元素的数量，然后对区域内的元素进行全量距离计算再排序。这样可以明显减少计算量。

问题2：如何划分矩形区域？

答案：可以指定一个半径 r，使用一条 SQL 就可以圈出来。当用户对筛出来的结果不满意，那就扩大半径继续筛选

select id from positions where x0-r < x < x0 + r and y0 - r  < y < y0 + r

问题3：如何提高上面的性能？

答案：，为了满足高性能的矩形区域算法，数据表需要在经纬度坐标加上双向复合索引 (x, y)， 这样可以最大优化查询性能。

问题3：真的要用数据库吗？不会有性能方面的担忧吗？

答案：数据库查询性能毕竟有限，如果「附近的人」查询请求非常多，在高并发场合，这肯定不是一个很好的方案。

问题4：那用什么来计算地理位置呢?

答案：GeoHash 算法

2、GeoHash 算法

业界比较通用的地理位置距离排序算法是 GeoHash 算法，Redis 也使用 GeoHash 算 法。

问题1：GeoHash 算法 大概是怎样的?

答案：GeoHash 算法将二维的经纬度数据映射到一维的整数，这样所有的元素都将在挂载到一 条线上，距离靠近的二维坐标映射到一维后的点之间距离也会很接近。当我们想要计算「附 近的人时」，首先将目标位置映射到这条线上，然后在这个一维的线上获取附近的点就行了。

问题2：那这个映射算法具体是怎样的呢?

答案：它将整个地球看成一个二维平面，然后划分成了一系 列正方形的方格，就好比围棋棋盘。所有的地图元素坐标都将放置于唯一的方格中。方格越小，坐标越精确。然后对这些方格进行整数编码，越是靠近的方格编码越是接近。

问题3：那如何编码呢?

答案：

1、一个最简单的方案就是切蛋糕法。设想一个正方形的蛋糕摆在你面前，二刀下去均分分成四块小正方形，这四个小正方形可以分别标记为 00, 01, 10,11 四个二进制整数。

2、然后对 每一个小正方形继续用二刀法切割一下，这时每个小小正方形就可以使用 4bit 的二进制整数 予以表示。然后继续切下去，正方形就会越来越小，二进制整数也会越来越长，精确度就会越来越高。

问题4：真实场景只有上面的编码方式吗？

答案：上面的例子中使用的是二刀法，真实算法中还会有很多其它刀法，最终编码出来的整数数字也都不一样。编码之后，每个地图元素的坐标都将变成一个整数，通过这个整数可以还原出元素的坐标，二进制整数越长，还原出来的坐标值的损失程度就越小。对于「附近的人」这个功能而言，损失的一点精确度可以忽略不计。

问题5：GeoHash内部结构是怎么存储的？

答案：GeoHash 算法会继续对这个二进制数做一次 base32 编码 (0-9,a-z 去掉 a,i,l,o 四个字母) 变 成一个字符串。

在 Redis 里面，经纬度使用 52 位的二进制整数（使用zset获取到的是十进制数哦）进行编码，放进了 zset 里面，zset 的 value 是元素的 key，score 是 GeoHash 的 52 位二进制整数(十进制哦)值。zset 的 score 虽然是浮点数， 但是对于 52 位的整数值，它可以无损存储。

在使用 Redis 进行 Geo 查询时，我们要时刻想到它的内部结构实际上只是一个 zset(skiplist)。通过 zset 的 score 排序就可以得到坐标附近的其它元素 (实际情况要复杂一 些，不过这样理解足够了)，通过将 score 还原成坐标值就可以得到元素的原始坐标。

问题6：为什么是52位呢？

Redis 中实现

#define GEO_STEP_MAX 26
long = ((longitude - (-180)) / (180 - (-180))) * (1 << GEO_STEP_MAX)
lat = ((latitude - (-85))/ (85- (-85))) * (1 << GEO_STEP_MAX)  
//这里维度的范围不是[-90, 90], 因为高纬度地区几乎没有人居住，所以这部分区域实际是被忽略了实际这也是一种巧妙优化手段

1、经纬度划分的次数，在redis中该值为26，即经度/纬度的二进制编码长度为26，最终经交叉组合而成的地理位置的二进制编码为52位。Base32编码为每5bits组成一个字符，所以最终的GeoHash字符串为11位。

2、根据精度速查表，只要有52个bits，误差已经可以降低到0.5米以下，所以不需要在更多bits了

2.1、GeoHash特点

1、首先，geohash 用一个字符串表示经度和纬度两个坐标

2、geohash 表示的并不是一个点，而是一个矩形区域。 这个矩形区域内所有的点（经纬度坐标）都共享相同的GeoHash字符串，这样既可以保护隐私（只表示大概区域位置而不是具体的点）

3、GeoHash值的前缀相同的位数越多，代表的位置越接近（反之，却不成立），可以方便索引。字符串相似的表示距离相近，这样可以利用字符串的前缀匹配来查询附近信息。如，一个在城区，一个在郊区，城区的GeoHash字符串之间比较相似，郊区的字符串之间也比较相似，而城区和郊区的GeoHash字符串相似程度要低些

4、编码的前缀可以表示更大的区域。例如wx4g0ec1，它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索。字符串越长，表示的范围越精确

2.2、GeoHash编码长度与精度的关系图

geoHash length ：

⬤ 精度 4，范围可以精确到20Km

⬤ 精度 8，范围可以精确到19m

在纬度相等的情况下：

◯ 经度每隔0.00001度，距离相差约1米；

◯ 每隔0.0001度，距离相差约10米；

◯ 每隔0.001度，距离相差约100米；

◯ 每隔0.01度，距离相差约1000米；

◯ 每隔0.1度，距离相差约10000米。

在经度相等的情况下：

◯ 纬度每隔0.00001度，距离相差约1.1米；

◯ 每隔0.0001度，距离相差约11米；

◯ 每隔0.001度，距离相差约111米；

◯ 每隔0.01度，距离相差约1113米；

◯ 每隔0.1度，距离相差约11132米。

2.3、GeoHash算法的步骤

经度范围是东经180到西经180，纬度范围是南纬90到北纬90，我们设定西经为负，南纬为负，所以地球上的经度范围就是[-180， 180]，纬度范围就是[-90，90]

2.3.1、将经纬度变成二进制

比如这样一个点（39.92324, 116.390705）

2.3.1.1、纬度的二进制编码

如果给定的纬度x（39.92324）属于左区间，则记录0，如果属于右区间则记录1，这样随着算法的进行会产生一个bit序列，序列的长度跟给定的区间划分次数有关。

1）区间[-90,90]进行二分为[-90,0),[0,90]，称为左右区间，可以确定39.92324属于右区间[0,90]，给标记为1；

2）接着将区间[0,90]进行二分为 [0,45),[45,90]，可以确定39.92324属于左区间 [0,45)，给标记为0；

3）递归上述过程 39.92324总是属于某个区间[a,b]。随着每次迭代区间[a,b]总在缩小，并越来越逼近 39.92324；

4) 以此类推，直到精度符合要求为止，得到纬度编码为 1011 1000 1100 0111 1001。

2.3.1.2、经度的二进制编码

经度也用同样的算法，对(-180, 180)依次细分，得到116.3906的编码为 1101 0010 1100 0100 0100。

2.3.2、组码 （经度占偶数位，纬度占奇数位）

经度占偶数位，纬度占奇数位，注意，0也是偶数位。

纬度产生的编码为1011 1000 1100 0111 1001，

经度产生的编码为1101 0010 1100 0100 0100。

把2串编码组合生成新串：11100 11101 00100 01111 00000 01101 01011 00001

2.3.3、按照Base32进行编码

编码：对这个整数做一次 base32 编码（ 0-9、b-z（去掉a, i,l, o）这32个子母/数字。

具体操作是将获取到的经纬度二进制数以每5个数为一组，将每一组都进行转换成十进制数字。然后采用Base32对应编码进行转换可得到编码wx4g0ec1。

⬤ 比如我们的经纬度都分了10次，那么最后生成的字符串的长度就是 10 * 2 / 5 = 4，范围是20km，

⬤ 如果我们经纬度都分20次，那么最后生成的字符串的长度就是20 * 2 / 5 = 8，范围可以精确到19m。

首先将11100 11101 00100 01111 00000 01101 01011 00001转成十进制，十进制对应的编码就是wx4g

2.4、GeoHash原理

经度范围是东经180到西经180，纬度范围是南纬90到北纬90，我们设定西经为负，南纬为负，所以地球上的经度范围就是[-180， 180]，纬度范围就是[-90，90]。如果以本初子午线、赤道为界，地球可以分成4个部分。

我们将二进制编码的结果填写到空间中，当将空间划分为四块时候

1、经度左半区间为 0，右半区间为 1，纬度下半区间 为0，上半区间为1，于是经纬度二进制编码交叉组合，得到编码的顺序分别是左下角00，左上角01，右下脚10，右上角11，也就是类似于Z的曲线

2、当我们递归的将各个块分解成更小的子块时，编码的顺序是自相似的（分形），每一个子块也形成Z曲线，这种类型的曲线被称为Peano空间填充曲线。

这种类型的空间填充曲线的优点是将二维空间转换成一维曲线（事实上是分形维），对大部分而言，编码相似的距离也相近

注意：但Peano空间填充曲线最大的缺点就是突变性，有些编码相邻但距离却相差很远，比如0111与1000，编码是相邻的(最大的Z字形连线)，但距离相差很大。

2.4.1、边界问题

上面也说了，这个算法看起来完美，但是稍微也有点问题，那么该怎么找出这些位置相近而编码不相邻的位置呢？

1、就是有些编码相邻但距离却相差很远，

2、有些地理位置相对较近，却编码并不相邻。

问题1：两个离的越近，geohash的结果相同的位数越多，对么？

答案：如下

1、这一点是有些用户对geohash的误解，虽然geo确实尽可能的将位置相近的点hash到了一起，可是这并不是严格意义上的(实际上也并不可能，因为毕竟多一维坐标)

2、例如上图中红点和黑点离的很近，可是它们的geohash值一定是相差的相当远，很多时候我们对geohash的值进行简单的排序比较，结果貌似真的能够找出相近的点，并且似乎还是按照距离的远近排列的，可是实际上会有一些点被漏掉了。

问题2：如果每个方格的精度为 2km，那么我们直接按照前缀查询红点附近 2km 的点是查找不到离它很近的黑点的，那怎么办呢。

答案：要解决这个问题，我们就需要所其周边八个方格也考虑上，将自身方格和周边八个方格内的点都遍历一次，再返回符合要求的

问题3：那如何计算出周边8个方格的点呢？

答案：如下

1、假设我们计算的goohash值是6位，那么二进制位数就是 6 * 5 = 30位，所以经纬度分别是15位。我们以纬度为例，纬度会均分15次。这样我们很容易能够算出15次后，划分的最小单位是多少

2、得到了最小单位，那么周边区域的经纬度也可以计算得到了。比如说左边区域的经度肯定是自身经度减去最小经度单位。纬度也可以通过加减，得到上下的纬度值，最终周围8个单位也可以计算得到。

3、可以到 http://geohash.co/ 进行geohash编码，以确定自己代码是否写错

问题4：既然不能做到将相近的点hash值也相近，那么geohash的意义何在呢?

答案：能确保将每一个小块的geohash值确保在一定的范围之内，这样就为灵活的周边查找和范围查找提供了可能。

3、Redis 的 Geo 指令基本使用

Redis 提供的 Geo 指令只有 6 个，读者们瞬间就可以掌握。使用时，读者务必再次想起，它只是一个普通的 zset 结构。

3.1、geoadd：增加地理位置信息

`geoadd key 经度 纬度 城市`

127.0.0.1:6379> geoadd company 116.48105 39.996794 juejin 
(integer) 1
127.0.0.1:6379> geoadd company 116.514203 39.905409 ireader 
(integer) 1
127.0.0.1:6379> geoadd company 116.489033 40.007669 meituan
(integer) 1


# 同时添加多个地理位置信息 
127.0.0.1:6379> geoadd company 116.562108 39.787602 jd 116.334255 40.027400 xiaomi 
(integer) 2

3.2、zrem：删除地理信息

Redis 没有提供 geo 删除指令，反正它就是没有提供。但是这里需要知道的是这里存放的数据类型为zset，按照zset的方式删除即可

127.0.0.1:6379> type cities:location
zset
127.0.0.1:6379> zrem  cities:location beijing

3.3、geopos：获取地理位置信息

geopos 指令可以获取集合中任意元素的经纬度坐标，可以一次获取多个。

注意：我们观察到获取的经纬度坐标和 geoadd 进去的坐标有轻微的误差，原因是 geohash 对 二维坐标进行的一维映射是有损的，通过映射再还原回来的值会出现较小的差别。对于「附 近的人」这种功能来说，这点误差根本不是事。

127.0.0.1:6379> geopos company juejin 
1) 1) "116.48104995489120483"
   2) "39.99679348858259686"
127.0.0.1:6379> geopos company ireader 
1) 1) "116.5142020583152771"
   2) "39.90540918662494363" 
   
   
127.0.0.1:6379> geopos company juejin ireader 
1) 1) "116.48104995489120483"
   2) "39.99679348858259686" 
2) 1) "116.5142020583152771"
   2) "39.90540918662494363"

3.4、geodist ：获取两个地理位置之间的距离

geodist key city1 city2 [unit] m米 km千米 mi英里 ft 尺

127.0.0.1:6379> geodist company juejin ireader km 
"10.5501"
127.0.0.1:6379> geodist company juejin meituan km 
"1.3878"
127.0.0.1:6379> geodist company juejin jd km 
"24.2739"
127.0.0.1:6379> geodist company juejin xiaomi km 
"12.9606"
127.0.0.1:6379> geodist company juejin juejin km 
"0.0000"

3.5、georadiusbymember：获取指定位置范围内的地理信息位置集合

georadiusbymember 指令是最为关键的指令，它可以用来查询指定元素附近的其它元 素，它的参数非常复杂。

WITHDIST: 同时返回地理位置与给定位置的距离

WITHCOORD: 同时返回地理位置的经纬度坐标

WITHHASH: 同时返回Redis内部的GeoHash值（非标准算法值），一般用于debug

ASC|DESC：结果按距离升降序排序

1、范围 20 公里以内最多 3 个元素按距离正排，它不会排除自身

127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 asc 
1) "ireader"
2) "juejin"
3) "meituan"

2、范围 20 公里以内最多 3 个元素按距离倒排

127.0.0.1:6379> georadiusbymember company ireader 20 km count 3 desc 
1) "jd"
2) "meituan"
3) "juejin"

3、三个可选参数 withcoord withdist withhash 用来携带附加参数

# 三个可选参数 withcoord withdist withhash 用来携带附加参数
# withdist 很有用，它可以用来显示距离
127.0.0.1:6379>  georadiusbymember company ireader 20 km withcoord withdist withhash count 3 asc 
1) 1) "ireader"
   2) "0.0000"
   3) (integer) 4069886008361398
   4) 1) "116.5142020583152771"
      2) "39.90540918662494363"
2) 1) "ireaderexit"
   2) "0.0000"
   3) (integer) 4069886008361398
   4) 1) "116.5142020583152771"
      2) "39.90540918662494363"
3) 1) "meituan"
   2) "11.5748"
   3) (integer) 4069887179083478
   4) 1) "116.48903220891952515"
      2) "40.00766997707732031"

4、除了 georadiusbymember 指令根据元素查询附近的元素，Redis 还提供了根据坐标值来 查询附近的元素，这个指令更加有用，它可以根据用户的定位来计算「附近的车」，「附近 的餐馆」等。它的参数和 georadiusbymember 基本一致，除了将目标元素改成经纬度坐标 值。

127.0.0.1:6379> georadius company 116.514202 39.905409 20 km withdist count 3 asc 
1) 1) "ireader"
   2) "0.0000"
2) 1) "ireaderexit"
   2) "0.0000"
3) 1) "meituan"
   2) "11.5748"

3.5.1、实现方式

1、GeoHash值的前缀相同的位数越多，代表的位置越接近，可以方便索引。但反之不成立，位置接近的GeoHash值不一定相似。靠近每个方块边界两侧的点虽然十分接近，但所属的编码会完全不同。

2、实际应用中，需要通过去搜索环绕当前方块周围的8个方块来解决该问题。搜索的时候会检查挡墙方块+8个覆盖整个搜索半径的区域，不断的去除geohash的低位，直到这9个方块能覆盖搜索半径位置。再一次搜索计算每个位置的距离。

3.6、geohash：获取元素的 hash 值

geohash 可以获取元素的经纬度编码字符串，上面已经提到，它是 base32 编码。你可以使用这个编码值去 http://geohash.org/${hash}中进行直接定位 它是 geohash 的标准编码 值。

127.0.0.1:6379> geohash company ireader 
1) "wx4g52e1ce0"
127.0.0.1:6379> geohash company juejin 
1) "wx4gd94yjn0"

4、zset存储的数据量太大怎么办

在一个地图应用中，车的数据、餐馆的数据、人的数据可能会有百万千万条，如果使用 Redis 的 Geo数据结构，它们将全部放在一个 zset 集合中。

在 Redis 的集群环境中，集合 可能会从一个节点迁移到另一个节点，如果单个 key 的数据过大，会对集群的迁移工作造成 较大的影响，在集群环境中单个 key 对应的数据量不宜超过 1M，否则会导致集群迁移出现 卡顿现象，影响线上服务的正常运行。

所以，这里建议如下 ：

1、 Geo 的数据使用单独的 Redis 实例部署，不使用集群环境。

2、如果数据量过亿甚至更大，就需要对 Geo 数据进行拆分，按国家拆分、按省拆分，按 市拆分，在人口特大城市甚至可以按区拆分。这样就可以显著降低单个 zset 集合的大小。