geoHash

一. 什么是geoHash

GeoHash本质上是空间索引的一种方式，其基本原理是将地球理解为一个二维平面，将平面递归分解成更小的子块，每个子块在一定经纬度范围内拥有相同的编码。以GeoHash方式建立空间索引，可以提高对空间poi数据进行经纬度检索的效率。

二. 使用geoHash有什么优点

①GeoHash用一个字符串表示经度和纬度两个坐标。某些情况下无法在两列上同时应用索引（例如MySQL 4之前的版本，Google App Engine的数据层等），利用GeoHash。只需要在一列上应用索引即可。

②GeoHash表示的并不是一个点，而是一个矩形区域。比如编码wx4g0ec19，它表示的是一个矩形区域。使用者可以发布地址编码，既能表明自己位于北海公园附近，又不至于暴露自己的精确坐标，有助于隐私保护。

③编码的前缀可以表示更大的区域。例如，wx4g0ec1，它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。这个特性可以用于附近地点搜索。首先根据用户当前坐标计算GeoHash（例如wx4g0ec1），然后取其前缀进行查询（SELECT * FROM place WHERE geohash LIKE 'wx4g0e%'），即可查询附近的所有地点。

④GeoHash比直接用经纬度的高效很多。

三. geoHash原理

这里通过一个具体的坐标进行举例。

常营地铁站（lat:39.9257460000,lng:116.5998310000）,我们获取一个区域的位置，是使用一个二维数组对其进行标记的，它表示的不是一个具体的点，而是泛指一片区域，区域的范围与经纬度的取值精度直接相关。

当我拿到常营地铁站的经纬度后，通过GeoHash这种算法进行计算后，获取到一个可比较的字符串，具体计算过程如下:

同样，对纬度也进行相对应的算法进行计算得到一个二进制值(对经纬度取值范围越小，精度越高，所表示区域范围越小)，在此省去计算过程。

https://www.cnblogs.com/tgzhu/p/6204173.html

将经纬度的二进制数进行组合，以奇数为经度，偶数为纬度组合，过程如上图。

然户将获取到的经纬度二进制数以每5个数为一组，将每一组都进行转换成十进制数字。

然后采用Base32（2^5）对应编码进行转换可得到编码 wx4g0e这样的可比较的字符串，比如我们的经纬度都分了10次，那么最后生成的字符串的长度就是4·（10+10）/5，范围是20km，如果我们经纬度都分20次，那么最后生成的字符串的长度就是8，范围可以精确到19m。为什么是可比较字符串，后面会详细讲解到。

在此对Base32编码进行一番简单介绍: Base32，是将数字 0~9 ，加上26个字母(去除a,i,l,o 四个)进行组合而成的32个字符编码形式。如代码：

Base32对应编码参考图：(上面二进制转换对应的十进制数值)

维基百科上Base32位值信息表

下面是从网上在线解析的常营地铁站GeoHash值(wx4gjk32kfrx)

这个geoHash实际表示的是一个范围区域，对应的坐标点就在其中。

Geohash其实就是将整个地图或者某个分割所得的区域进行一次划分，由于采用的是base32编码方式，即Geohash中的每一个字母或者数字（如wx4g0e中的w）都是由5bits组成（2^5 = 32，base32），这5bits可以有32中不同的组合（0~31），这样我们可以将整个地图区域分为32个区域，通过00000 ~ 11111来标识这32个区域。第一次对地图划分后的情况如下图所示（每个区域中的编号对应于该区域所对应的编码）。

​ Geohash的0、1串序列是经度0、1序列和纬度0、1序列中的数字交替进行排列的，偶数位对应的序列为经度序列，奇数位对应的序列为纬度序列，在进行第一次划分时，Geohash0、1序列中的前5个bits（11100），那么这5bits中有3bits是表示经度，2bits表示纬度，所以第一次划分时，是将经度划分成8个区段（2^3 = 8），将纬度划分为4个区段（2^2 = 4），这样就形成了32个区域。如下图

​ 同理，可以按照第一次划分所采用的方式对第一次划分所得的32个区域各自再次划分。

GeoHash将每一个区域画成一块块矩形块，每个矩形块使用一个字符串表示，当我们需要查询附近的点时，通过自己的坐标计算出一个字符串，根据这个字符串定位到我们所在的矩形块，然后返回这个矩形块中的点。例如 wx4e就包含wx4e0e,也就是说wx4e0e在wx4e范围内。

按照这种思路进行，思路逐渐清晰，但是，这种方式会不会有什么问题呢？ 或者说，它有什么弊端。

四. geoHash缺点

按照单个区域情况考虑，就会出现如上所示的情况。所以就得想办法解决这种情况，就需要将范围进一步扩大。

目前比较通行的做法就是**我们不仅获取当前我们所在的矩形区域，还获取周围8个矩形块中的点。**那么怎样定位周围8个点呢？关键就是需要获取周围8个点的经纬度，那我们已经知道自己的经纬度，只需要用自己的经纬度减去最小划分单位的经纬度就行。因为我们知道经纬度的范围,有知道需要划分的次数，所以很容易就能计算出最小划分单位的经纬度。

通过上面这张图，我们就能很容易的计算出周围8个点的经纬度了。有了经纬度就能定位到周围8个矩形块了。这样我们就能获取包括自己所在矩形块的9个矩形块中的所有的点。最后分别计算这些点和自己的距离（由于范围很小，点的数量就也很少，计算量就很少）过滤掉不满足条件的点就行了。

五. 什么是Z阶曲线

x 轴就是纬度，y轴就是经度。经度放偶数位，纬度放奇数位就是这样而来的。

六. Z阶曲线产生的优缺点

Geohash 的优点很明显，它利用 Z 阶曲线进行编码。而 Z 阶曲线可以将二维或者多维空间里的所有点都转换成一维曲线。在数学上成为分形维。并且 Z 阶曲线还具有局部保序性。

Z 阶曲线通过交织点的坐标值的二进制表示来简单地计算多维度中的点的z值。一旦将数据被加到该排序中，任何一维数据结构，例如二叉搜索树，B树，跳跃表或（具有低有效位被截断）哈希表都可以用来处理数据。通过 Z 阶曲线所得到的顺序可以等同地被描述为从四叉树的深度优先遍历得到的顺序。

这也是 Geohash 的另外一个优点，搜索查找邻近点比较快。 Geohash 的缺点之一也来自 Z 阶曲线。 Z 阶曲线有一个比较严重的问题，虽然有局部保序性，但是它也有突变性。在每个 Z 字母的拐角，都有可能出现顺序的突变。

看上图中标注出来的蓝色的点点。每两个点虽然是相邻的，但是距离相隔很远。看右下角的图，两个数值邻近红色的点两者距离几乎达到了整个正方形的边长。两个数值邻近绿色的点也达到了正方形的一半的长度。

Geohash 的另外一个缺点是，如果选择不好合适的网格大小，判断邻近点可能会比较麻烦。 看上图，如果选择 Geohash 字符串为6的话，就是蓝色的大格子。红星是美罗城，紫色的圆点是搜索出来的目标点。如果用 Geohash 算法查询的话，距离比较近的可能是wtw37p，wtw37r，wtw37w，wtw37m。但是其实距离最近的点就在 wtw37q。如果选择这么大的网格，就需要再查找周围的8个格子。

如果选择 Geohash 字符串为7的话，那变成黄色的小格子。这样距离红星星最近的点就只有一个了。就是 wtw37qw。

如果网格大小，精度选择的不好，那么查询最近点还需要再次查询周围8个点。

七. 实际应用

例如对于地图图上，需要实时去更新自己的地图的路网的数据，特别是一些link的拓扑修改等，这个时候，多条数据来进行修改，是需要进行加锁的，避免并发冲突，那么我们怎么对地图上的一个区域或者是点加锁呢？首先我们知道一般前端来得数据应该是一个坐标，这时我们就可以利用geohash将这个坐标转化为geohash字符串，这个字符串表示这个坐标点所在的区域，我们直接使用redis 对这个字符串进行加锁，就表示当前这个位置被站锁正在被修改，非常方面。

参考：

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

https://www.jianshu.com/p/1ecf03293b9a

https://www.shenyanchao.cn/blog/2020/01/16/geo_geohash/