背景

如何表示一个地点所处客观的位置，传统的方法有经纬度、邮政编码等。
比如给一个北纬31.2397度，东经121.4994度，就是大概东方明珠所处于的地球上的位置，这样表示方法，精度高，但二维的表示方法不太利于查询。另外邮政编码也是生活中经常使用的，大家应该比较了解，比如200000是上海市邮编，201800就是上海嘉定区的邮编，这样的一维编码比较利于查询，地理位置相邻的区域有共享前缀，但是精度比较差（国家政府会统一编码），只能表示一个区域，而且一般邮编都是和行政区挂钩的，覆盖区域范围不规则。

OK，那有没有既保证精度，又方便查询的表示位置的数据结构呢？有，GeoHash就是，那么下面我们就介绍下GeoHash是什么以及GeoHash如何应用在位置搜索场景中。

GeoHash的原理

GeoHash是一种地理编码系统。

GeoHash是一种变长的编码，上图就是世界地图被分为了32个区域，每个网格可以使用base32的字母数字编码表示。优点有，可以达到任意精度（编码足够长即可），规则的固定区域（每个地球上的点可以算出来GeoHash，不是通过国家行政手段分配的），相邻区域享受越长的共享前缀。
仔细观察下上图的字母数字排列，并非常规顺序，这是因为GeoHash采用了Z曲线（也叫N曲线）去做字母排列，目的是在二维数据映射到一维数据时，尽可能保持locality。

那么再以东方明珠的位置为例，GeoHash的编码为wtw3sz。

可以看到先是按48的格子分，w的格子按照84再细分，以此类推，随着编码长度变长，越来越精确，如果两个位置共享前缀越长，表示他们之间的物理距离也越近。

上图所示，当编码长度为12时，已经到了3.7cm*1.9cm，所以一般情况6~7的长度，在表示日常生活中位置时，基本够用了。最后来看下GeoHash和邮政编码以及经纬度的对比。

所以，GeoHash的编码就是将世界地图切分为32个格子，每个格子又可以递归切分，编码的具体顺序如下图所示，以Z曲线（或者叫N曲线）顺序安排32个字母和数字。

GeoHash的应用

GeoHash显然大量使用在LBS类型的APP上，比如大众点评，美团外卖等，通常就是给定一个位置（经纬度坐标）和一个查询半径，找到附近的商家。这其实就是一个圆和方块们的故事，为啥这么说呢？
先来看一个简单查询的情况，黑色小圆表示顾客所在位置，搜索附近250m的商家，这时发现顾客所在位置的geohash6（长度为6的geohash）为wtw3sz，正好这个顾客处于这个GeoHash的中间位置，半径250m，都是被这个GeoHash所覆盖，那么查询语句，只需要查询此GeoHash内的商家，然后以250m的距离过滤掉即可。

上面显然是最简单的情况，那么如果geohash长度选择不合适，就会造成需要查询的方格数量过大（查询次数多）或者过小（需要过滤的地点多），一般的情况查询的方格数量为2~9个，以下图为例说明。

查询方法有两种：

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

结论

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