地理位置附近查询的GEOHASH解决方案

case描述

滴滴出现是一款非常好用的APP，解决了日常用户的出行需求，产品的背后需要非常精湛的技术支持，其中一项技术叫附近查找，附近查找的业务可能会基于多种业务规则，最常用的就是基于出行人的地理位置，查找附件的司机，从而将该出行需求信息推送给给附近的司机（以上是滴滴的业务，跟我们的业务并没有任何关系，只是为了描述业务场景）。我们的货车业务一样需要用到附近查找的技术，通过定位当前用户的位置，查询附近的货车，并在地图上展示。

解题思路

地图后台如何根据自己所在位置查询来查询附近货车的呢？计算用户所在位置P与朝阳区所有货车距离，然后返回距离<=1000米的货车。问题来了，那么如果我们朝阳区有10万辆货车，这样计算不得了，是否可以考虑用索引？

一提到索引，大家脑子里马上浮现出B树索引，因为大量的数据库（如MySQL、oracle、PostgreSQL等）都在使用B树。B树索引本质上是对索引字段进行排序，然后通过类似二分查找的方法进行快速查找，即它要求索引的字段是可排序的，一般而言，可排序的是一维字段，比如时间、年龄、薪水等等。但是对于空间上的一个点（二维，包括经度和纬度），如何排序呢？又如何索引呢？解决的方法很多，下文介绍几种方法来解决这一问题。

• 支持二维索引的存储数据库：mongo

mongoDB支持二维空间索引,使用空间索引,mongoDB支持一种特殊查询,如某地图网站上可以查找离你最近的咖啡厅,银行等信息。这个使用mongoDB的空间索引结合特殊的查询方法很容易实现。

db.places.find( { location : { $near : [39.9994520000,116.4021310000], $maxDistance: 0.7 } } ).limit(20);

获取附近半径0.7附近的20条记录，经常简单实用。

优点:API直接支持，很方便
缺点：mongo2D查询不能建立联合索引，再基于其它条件排序的话，性能比较低，类似mysql的filesort，并发量大、数据量大的话性能是mongo会成为瓶颈。

• 升级Mysql至5.7，支持Geohash

MySQL 5.7.5 增加了对GeoHash的支持，提供了一系列geohash的函数，但是其实Mysql并没有提供类似mogodb类型near这样的函数，仅仅提供了一些经纬度转hash、hash取经纬度的一些函数。
参考：spatial-geohash-functions : http://dev.mysql.com/doc/refman/5.7/en/spatial-geohash-functions.html

优点:函数直接调用，生成目标hash、根据hash获取经纬度。
缺点：不支持范围查询函数，需要自行处理周边8点的问题，需要补充geo的算法

• Redis Commands: Geography Edition

GEO 特性在 Redis 3.2 版发布， 这个功能可以将用户给定的地理位置信息储存起来， 并对这些信息进行操作，GEO通过如下命令来完成GEO需求：详细参考：

redis-geo:https://matt.sh/redis-geo

Redis GEO 特性简介:http://blog.jobbole.com/89225/

优点:效率高，API丰富
缺点：3.2版本是否稳定？

• 基于Lucene-Spatial的地理位置查找

Lucene通过Spatial包提供了对基于地理位置的全文检索的支持，将坐标信息转化为笛卡尔层，建立索引

优点:天然支持，性能很优。
缺点：需要投入时间研究一下特性。

为什么GeoHash

GeoHash应用原理介绍

以上方案大部分都基于GEOHASH，思想通过某种方法将二维的点数据转换成一维的数据,我们已mysql为例，那样不就可以继续使用B树索引了嘛。
 GeoHash将二维的经纬度转换成字符串，比如下图展示了北京9个区域的GeoHash字符串，分别是WX4ER，WX4G2、WX4G3等等，每一个字符串代表了某一矩形区域。也就是说，这个矩形区域内所有的点（经纬度坐标）都共享相同的GeoHash字符串，这样既可以保护隐私（只表示大概区域位置而不是具体的点），又比较容易做缓存，比如左上角这个区域内的用户不断发送位置信息请求餐馆数据，由于这些用户的GeoHash字符串都是WX4ER，所以可以把WX4ER当作key，把该区域的餐馆信息当作value来进行缓存，而如果不使用GeoHash的话，由于区域内的用户传来的经纬度是各不相同的，很难做缓存。

字符串越长，表示的范围越精确。如图所示，5位的编码能表示10平方千米范围的矩形区域，而6位编码能表示更精细的区域（约0.34平方千米）

通过上面的介绍我们知道了GeoHash就是一种将经纬度转换成字符串的方法，并且使得在大部分情况下，字符串前缀匹配越多的距离越近，回到我们的案例，根据所在位置查询来查询附近餐馆时，只需要将所在位置经纬度转换成GeoHash字符串，并与各个餐馆的GeoHash字符串进行前缀匹配，匹配越多的距离越近。

GeoHash算法的步骤

理论略过，网上一大堆，参考：
Geohash ：https://en.wikipedia.org/wiki/Geohash

简单讲一下Peano空间填充曲线

如图所示，我们将二进制编码的结果填写到空间中，当将空间划分为四块时候，编码的顺序分别是左下角00，左上角01，右下脚10，右上角11，也就是类似于Z的曲线，当我们递归的将各个块分解成更小的子块时，编码的顺序是自相似的（分形），每一个子快也形成Z曲线，这种类型的曲线被称为Peano空间填充曲线。

这种类型的空间填充曲线的优点是将二维空间转换成一维曲线（事实上是分形维），对大部分而言，编码相似的距离也相近， 但Peano空间填充曲线最大的缺点就是突变性，有些编码相邻但距离却相差很远，比如0111与1000，编码是相邻的，但距离相差很大。

除Peano空间填充曲线外，还有很多空间填充曲线，如图所示，其中效果公认较好是Hilbert空间填充曲线，相较于Peano曲线而言，Hilbert曲线没有较大的突变。为什么GeoHash不选择Hilbert空间填充曲线呢？可能是Peano曲线思路以及计算上比较简单吧，事实上，Peano曲线就是一种四叉树线性编码方式。

GeoHash的缺陷及解决方法

• 边界问题

由于GeoHash是将区域划分为一个个规则矩形，并对每个矩形进行编码，就导致了geohash算法会有突变性，这样在查询附近信息时会导致距离很近的2个位置，GeoHash编码缺不一样，（因为不在同一个GeoHash区域块上），而近的GeoHash编码与我们不一致。

在当前点位于矩形的边界位置或者靠近边界位置时，与其最近的点可能处于边界另一侧的矩形内，这种情形下就无法匹配到最近的点。针对这种情况最直观的想法是把当前点所在矩形的周围八个矩形也包括进来，这样能保证输入的点集一定包括潜在的最近点。我们查询时，除了使用定位点的GeoHash编码进行匹配外，还使用周围8个区域的GeoHash编码，，再使用这8个点去取数据，最后再做merge、sort，这样可以避免这个问题。

8个点的算法：这个问题之前很困惑，怎么找效率最高，按照顺时针，8个方向：北、东北、东、东南、南、西南、西、西北，分别将当前位置的精度、维度的二进制提取出来，针对北的计算，则将维度+1，东北的则经度+1，维度+1,以此类推，最后再做组合计算，得到点的geohash。

经纬度距离换算

如果geohash的位数是9位数的时候，大概为附近2米
a）在纬度相等的情况下：

经度每隔0.00001度，距离相差约1米；
每隔0.0001度，距离相差约10米；

每隔0.001度，距离相差约100米；

每隔0.01度，距离相差约1000米；

每隔0.1度，距离相差约10000米。

b）在经度相等的情况下：

纬度每隔0.00001度，距离相差约1.1米；

每隔0.0001度，距离相差约11米；

每隔0.001度，距离相差约111米；

每隔0.01度，距离相差约1113米；

每隔0.1度，距离相差约11132米。

参考资料

Geohash :https://en.wikipedia.org/wiki/Geohash

Movable Type Scripts : http://www.movable-type.co.uk/scripts/geohash.html

使用 Apache Lucene 和 Solr 进行位置感知搜索  :http://www.ibm.com/developerworks/cn/java/j-spatial/

欢迎关注casestudy微信公共账号，及时了解最新的case