一文讲懂GeoHash技术(一)
一文讲懂GeoHash技术(一)
本文主要讲解GeoHash技术的原理及其应用。在第二篇文章中，我们将带领大家从零开始实现GeoHash。
1. GeoHash背景
1.1 背景问题
现在到了饭点，小明决定不点外卖，而是出去觅食。出门觅食肯定需要地图APP来指路，于是他打开了地图导航。
这时候小明突然产生了一个疑问：在地图APP中，是如何对这些饭店进行精准定位并推送的？而且为什么更换定位后，搜索附近的餐馆仍然能快速返回结果？
1.2 暴力解法
作为一个优秀的计算机科学学生，小明的第一反应是使用暴力遍历的方法。考虑到上海是一个二维化的城市，可以用经纬度坐标来表示，与重庆这种三维城市有所不同。
暴力解法的步骤如下：
- 先将所有餐馆的经纬度坐标存储在一个列表中
- 获取用户的经纬度坐标以及用户要求的最远距离
- 遍历列表中的所有坐标并计算与用户的距离
- 找出距离小于用户要求最远距离的饭店集合
虽然这种方法实现起来很简单，但问题也很明显：全球有数以亿计的餐馆，每次范围搜索都需要遍历这些数据，不仅用户体验差，服务器集群也难以承受这样的负载。
1.3 哈希解法
为了提高效率，小明想到了使用哈希。哈希的关键在于设计合理的哈希策略，以避免哈希冲突。然而，哈希如何进行范围查询呢？目前很多数据库引擎选择使用B+树而不是哈希，一个重要原因就是哈希无法进行范围查询。
这两个问题——可能退化成暴力算法和如何进行范围查询——正是GeoHash要解决的主要问题。GeoHash的基本思路是将坐标一维化，将二维坐标转换为一串索引，然后通过索引的前缀来确定是否在一个区域内。
让我们先看几个GeoHash的例子：
结果 | 点 | 经度 | 纬度 |
|---|---|---|---|
YJXY433V | A | 101 | 77 |
K6BE10DN | B | 12 | -29 |
经纬度的具体概念可以参考初中地理知识，因为这个概念在生活中经常用到。
2. GeoHash实现原理
在探讨完第一章后，读者可能会产生一个疑问：为什么GeoHash能把二维坐标转换为一维索引呢？而且为什么不会发生哈希冲突？这确实很神奇。
下面我们一起来学习这个算法的原理。
2.1 地球其实是矩形（dog）
地球当然不是矩形的，是椭圆形的，但是在计算机眼中，地球可以被投影为一个矩形平面。地球在纵向上由-90°90°的纬度范围组成，在横向上由-180°180°的经度范围组成。因此，矩形的宽、高刻度分别对应着经度和纬度，宽度方向上自左向右以-180°为起点，180°为终点，每个刻度的单位为1°经度；高度自底向上以-90°为起点，90°为终点，每个刻度单位为1°纬度。
2.2 把经纬度进行二分
如何把经纬度转换成一维坐标呢？GeoHash的思路是通过不断二分，再利用二进制来进行处理，最终得到一个二进制索引串。
2.2.1 经度拆分
具体步骤如下：
- 第一轮：经度范围为-180°
180°，拆分为-180°0°和0°~180°两部分。如果经度属于前者，则令首个比特位取0，否则令首个比特位取1。 - 第二轮：-180°
0°可以拆分为-180°-90°和-90°0°，如果经度属于前者，则令第二个比特位取0，否则令第二个比特位取1。0°180°可以拆分为0°90°和90°180°，前者令第二个比特位取0，后者令第二个比特位取1。 - 第3轮及以后：重复上述步骤的思路，最终递归二分，将经度表示成一个由二进制数字组成的字符串。
func binary(begin int , end int){
if(begin==end){
return
}
arg[begin][0.5*(end+begin)]=0
arg[0.5*(end+begin)][end]=1
binary(begin,0.5*(end+begin))
binary(0.5*(end+begin),end)
}
上述代码是伪代码，没有说明终止位数，完整的代码将在下一篇文章中给出。
2.2.2 纬度拆分
纬度的拆分过程与经度类似。
然后地球就被划分成了多个小块。要想把这两组二进制数合并成一组，可以将经度字符串和纬度字符串依次交错排列，最终形成一个一维字符串。例如，A块的索引是0000，B块是0100，E块是0010，以此类推。
2.2.3 最终结果
从上文可知，索引越长，划分的块就越少；反之，索引越短，划分的块就越多。如果两个块有相同的前缀，就可以认为它们在同一个大块中，例如A和B。他们有公共前缀00，所以他们都属于00表示的这个大块中。
综上所述，这个一维字符串具有前缀索引的性质，它能够保证两个字符串前缀匹配位数越长，两个矩形块的相对位置就越靠近。
这肯定会存在一些问题，后面会具体说明。
2.3 如何进行编码映射
具体来说，GeoHash一般采用Base32编码格式。因为如果直接用经纬度映射结果，映射结果会太长，要注意我们平常精确到小数点后三位，也就是几十位甚至上百位的映射结果。
所以采取Base32的编码格式来进行映射，在生成的二进制串中，从左向右开始，一次取五位，不足五位则在前补0（注意不是在后补0，不影响映射数值），然后5个二进制数的十进制从0到31依次对应10个数字字符‘0’-‘9’加上26个英文字母‘A’-‘Z’。
比如在第一章提到的YJXY433V，A点对应十进制串就是30 17 29 30 4 3 3 27，二进制串大家可以自己计算。
2.4 长度决定精度
在GeoHash字符串中，字符串的长度决定了矩形块的大小，进一步决定了距离的精度。在对经纬度进行递归二分时，每多一轮二分，矩形一个方向上的边长就会减半，因此矩形区域就越小，对应的精度就越高。
从小徐先生的编程世界中截的图，大家可以看一下。
3. GeoHash步骤
来具体梳理一下GeoHash的步骤：
- 获取目标经纬度
- 将经度按所需精度二分获得二进制串
- 将纬度按所需纬度二分获得二进制串
- 将前两步获得的两个二进制串进行Base32编码
- 进行查询等其他操作
看起来还是很简单的，具体实现会放在本系列的下一章来讲。
4. 常见问题
矩形块大小的问题
比如说还是这张图：
我们在矩形块F的右上边缘，那么显然块I以及J都会有和我们距离比较近的点，但显然F和IJ的公共前缀是不够的，但是距离是要比F点内左下角要小很多的。
针对这个问题，显然矩形块的大小不能随便的继续减小，不然可能会出现距离的问题，所以我们一般是通过GeoHash锁定一个小的矩形块后，以其作为中心，将周围8个矩形块范围内的点也同时检索出来，再根据实际的相对距离进行过滤。
范围检索
前面提到过GeoHash很重要的一点就是能进行范围检索。
应用GeoHash技术的一类场景是：给定一个指定位置作为中心点，想要检索出指定半径范围内的所有点集合。
这是我们的思路一般是，获得中心块的GeoHash的哈希串，然后以九宫格的方向向外扩展，直到满足覆盖中心点按要求半径所形成的圆，这样做肯定会有多余结果，我们再通过与中心点的距离进行过滤，当然不是过滤全部，只过滤边缘块。
对于第四章这个话题肯定还有其他问题，欢迎评论区或者私信交流。
本文主要讲的是GeoHash的技术原理，相信看完本文肯定会有比较深入的了解，下一篇文章我会带大家从0到1实现GeoHash。
本文主要学习：小徐先生的编程世界