2021年10月

背景

如何表示一个地点所处客观的位置,传统的方法有经纬度、邮政编码等。
比如给一个北纬31.2397度,东经121.4994度,就是大概东方明珠所处于的地球上的位置,这样表示方法,精度高,但二维的表示方法不太利于查询。另外邮政编码也是生活中经常使用的,大家应该比较了解,比如200000是上海市邮编,201800就是上海嘉定区的邮编,这样的一维编码比较利于查询,地理位置相邻的区域有共享前缀,但是精度比较差(国家政府会统一编码),只能表示一个区域,而且一般邮编都是和行政区挂钩的,覆盖区域范围不规则。
6097d5c6454e8fc273dac412e8dcbf90.jpeg
OK,那有没有既保证精度,又方便查询的表示位置的数据结构呢?有,GeoHash就是,那么下面我们就介绍下GeoHash是什么以及GeoHash如何应用在位置搜索场景中。

GeoHash的原理

GeoHash是一种地理编码系统。
GeoHash介绍.png
GeoHash是一种变长的编码,上图就是世界地图被分为了32个区域,每个网格可以使用base32的字母数字编码表示。优点有,可以达到任意精度(编码足够长即可),规则的固定区域(每个地球上的点可以算出来GeoHash,不是通过国家行政手段分配的),相邻区域享受越长的共享前缀。
仔细观察下上图的字母数字排列,并非常规顺序,这是因为GeoHash采用了Z曲线(也叫N曲线)去做字母排列,目的是在二维数据映射到一维数据时,尽可能保持locality。
ZorN曲线.png
那么再以东方明珠的位置为例,GeoHash的编码为wtw3sz。
东方明珠的GeoHash表示.png
可以看到先是按48的格子分,w的格子按照84再细分,以此类推,随着编码长度变长,越来越精确,如果两个位置共享前缀越长,表示他们之间的物理距离也越近。
GeoHash精度表示范围.png
上图所示,当编码长度为12时,已经到了3.7cm*1.9cm,所以一般情况6~7的长度,在表示日常生活中位置时,基本够用了。最后来看下GeoHash和邮政编码以及经纬度的对比。
编码对比.png
所以,GeoHash的编码就是将世界地图切分为32个格子,每个格子又可以递归切分,编码的具体顺序如下图所示,以Z曲线(或者叫N曲线)顺序安排32个字母和数字。
一笔画GeoHash编码.png

GeoHash的应用

GeoHash显然大量使用在LBS类型的APP上,比如大众点评,美团外卖等,通常就是给定一个位置(经纬度坐标)和一个查询半径,找到附近的商家。这其实就是一个圆和方块们的故事,为啥这么说呢?
先来看一个简单查询的情况,黑色小圆表示顾客所在位置,搜索附近250m的商家,这时发现顾客所在位置的geohash6(长度为6的geohash)为wtw3sz,正好这个顾客处于这个GeoHash的中间位置,半径250m,都是被这个GeoHash所覆盖,那么查询语句,只需要查询此GeoHash内的商家,然后以250m的距离过滤掉即可。
简单查询.png
上面显然是最简单的情况,那么如果geohash长度选择不合适,就会造成需要查询的方格数量过大(查询次数多)或者过小(需要过滤的地点多),一般的情况查询的方格数量为2~9个,以下图为例说明。
一般查询.png
查询方法有两种:

  1. 分别查询9个格子geohash="4" OR geohash="5" ……,缺点是查询次数和涉及到的方格数量一样,上面的例子就要查询9次,优点是只查询了需要查询的方格。
  2. 范围搜索,也就是利用GeoHash编码的局部性,选出最小和最大的geohash,作为查询范围,geohash >= "4" AND geohash <= "s",优点是只需要查询1次,缺点是查询了非必要的格子,所以需要过滤的商家数量变多了。

结论

实际使用GeoHash作为位置编码和位置查询时,业务侧肯定会有更多复杂的逻辑设计,这篇文章就是想抛砖引玉,介绍下GeoHash这个有趣的数据机构,如果后续有时间,会深入到源码实现的角度学习下GeoHash。