mysql geohash_算法：geohash
现今互联网确实从方方面面影响我们的生活。现在我们可以足不出户就能买到我们心仪的衣服，找到附近的美食。当我们点开一个外卖的app就能看到自己附近的餐厅，那我们有没有想过这是怎么实现的呢？
首先我们能想到的就是把所有餐厅的经纬度存下来，然后当用户选择附近餐厅是，我们先获取用户的经纬度，然后到数据库中查出所有的经纬度，依次计算它们和用户间的距离。最后根据用户输入的距离范围过滤出合适的餐厅，并根据距离做一个升序排列。这样貌似能查出附近的餐厅，但是餐厅的数量这么多，直接全查出来内存也要爆掉，即使分批处理计算量也十分大。这样用户等待的时间就会特别长。那有什么办法能减少我们的计算量呢？很简单，我们应该只计算用户关心的那一片数据，而不是计算所有的。例如用户在北京，那完全没必要计算海南，黑龙江，新疆，浙江等其它地区的数据。如果我们能快速定位到北京直至某个区，那么我们的计算量将大大减少。我们发现这其实就是索引的功能，但是MySQL对这种二维的地理位置的索引支持并不友好(mongodb有直接的地理位置索引)，它对一维的像字符串这样的支持很好。那如果我们的数据在MySQL中，有没有什么方法能将我们的二维坐标转换为一种可比较的字符串呢？这就是我们今天要介绍的geohash算法。
geohash简单来说就是将一个地理坐标转换为一个可比较的字符串的算法。不过生成的字符串表示的是一个矩形的范围，并不是一个点。比如西二旗地铁附近这一片矩形区域就可以用wx4eyu82这个字符串表示，并且越靠前的编码表示额范围越大，比如中国绝大部分地区可以用w这个字母表示的矩形区域内。像wx4eyu82表示的区域一定在wx4e表示的区域范围内。利用这些特性我们就可以实现附近餐厅的功能了，比如我们希望查看西二旗地铁附近的餐厅就可以这样查询：select * from table where geohash like 'wx4eyu82%'; 这样就可以利用索引，快速查询出相关餐厅的信息了。并且我们还可以用wx4eyu82为key，餐厅信息为value做缓存。
下面我们具体看一下geohash算法是怎样一步步将一个坐标转换为一个字符串的。首先我们将经度和纬度都单独转换为一个二进制编码，我们先以西二旗地铁站(116.312621,40.058918)的纬度为例。纬度的范围是[-90,90],将其一分为二[-90,0]和[0,90]，如果我们的纬度落在第一个区间，则编码为0，如果落在第二个区间，则编码为1。接着我们再将纬度落在的那个区间也一分为二[0,45]和[45,90]。这时发现我们的纬度落在第一个区间，这时得到第二个编码0，以此类推:
所以我们得到纬度的二进制编码为：1011100011
具体需要分多少次，我们可以参考维基百科中的数据：
比如我们的经纬度都分了10次，那么最后生成的字符串的长度就是4，范围是20km，如果我们经纬度都分20次，那么最后生成的字符串的长度就是8，范围可以精确到19m。同理我们可以得到经度的二进制编码为: 1101001010。
得到经度和纬度的二进制编码后，我们按照奇数位放纬度，偶数为放经度的规则(我们这里奇数偶数下标是从0开始)将它们合成一个二进制编码：
最后我们需要将这个二进制编码转换为base32编码(就是使用 0~9，和 26个英文字母(去掉了a,i,l,o这4个字母)共32个字符来编码)。第一步我们将这个二进制编码按5个一组，转换为十进制，得到的十进制数为: 28， 29， 4， 13 。
第二步，对照上面这个base32编码表将获取对应的base32编码为: wx4e 。至此我们就完成了将一个经纬度坐标转换为一个字符串的过程。
现在我们总结一下，geohash将区域画成一块块矩形块，每个矩形块使用一个字符串表示，当我们需要查询附近的点时，通过自己的坐标计算出一个字符串，根据这个字符串定位到我们所在的矩形块，然后返回这个矩形块中的点。这样做会不会有什么缺陷呢？我们看下面这张图：
比如现在是y1，根据geohash算法定位到y1所在的矩形块，返回附近的点就会得到y2。但是我们发现实际情况是，x, z虽然不在我们所在的那个矩形区域，但是x, z显然离我们更近。这就是geohash的边界问题，就是如果我们刚好处在矩形的边界处，那么离我们最近的点不一定是和我们在同一个矩形框中的点，很可能是旁边的矩形框中的某些点离我们更近。那么怎么解决这个问题呢？目前比较通行的做法就是我们不仅获取当前我们所在的矩形区域，还获取周围8个矩形块中的点。那么怎样定位周围8个点呢？关键就是需要获取周围8个点的经纬度，那我们已经知道自己的经纬度，只需要用自己的经纬度减去最小划分单位的经纬度就行。因为我们知道经纬度的范围,有知道需要划分的次数，所以很容易就能计算出最小划分单位的经纬度。不理解的可以参考后面的代码实现部分。
通过上面这张图，我们就能很容易的计算出周围8个点的经纬度了。有了经纬度就能定位到周围8个矩形块了。这样我们就能获取包括自己所在矩形块的9个矩形块中的所有的点。最后分别计算这些点和自己的距离(由于范围很小，点的数量就也很少，计算量就很少)过滤掉不满足条件的点就行了。当然这些外面app附近商家的功能不一定是这么实现的，这只是我个人的“意淫”，? 。
代码放在github上，仅供参考： Cailiang/lbs