一. LBS 的实际问题
LBS 有一个经典的使用场景，就是查找当前位置附近的商家，车辆，或者交通站点。对于如何利用现有的技术来实现这个简单的需求，网上已经有成堆的资料可以查到，这里就不再赘述了，简单的说一下其中的一个关键的技术点 GeoHash 算法，仅此备忘。
传统的空间上的区域的数据都是二维以上的，比如经纬度，笛卡尔坐标等。存储的数据的形式通用的一般是关系型数据，和非关系型数据。
关系型数据在查询的支持的使用最多的就是依靠索引，B+树方式高效查询这点不用怀疑，但是如何针对二维数据有效的查询是心有余而力不足，那么如何解决二维数据的存储查询问题，就会有以下两种思路
1.使用一种特殊的索引结构实现对于空间数据的支持，这个就是所谓的空间索引
2.使用其他的非关系型数据，支持这些空间数据的存储，查询处理，所谓的 Redis，MongoDB 流派就是搞这个的。
不管1> 还是 2> ，他们其中用到的核心算法就是我们今天要讲的主角：GeoHash
二. GeoHash 算法
GeoHash 是一种地理编码，实现对于二维经纬度数据转化为一维的字符串，也就是降维打法，有了一维的数据，就可以进行方便的查询处理了。
GeoHash 算法，具体如下：
1.对于经纬度的数据，进行二分比较后，进行编码
其中纬度的总区间是 (-90, 90)
经度的总区间是 (-180, 180)
划分后，就可以根据要求的精度大小，最终收敛到某个区间范围，从开始到这个区间就对应唯一的二进制编码（二分处理过程中，属于0 还是 1）
2.按照 Z 阶曲线（局部保序性），对经纬度的编码进行合并，奇数位是纬度，偶数位是经度，得到新的编码
3.然后对于得到的编码按照 Base32 进行编码
可以看到上述的这种区间的划分方式，最终就会分布成一个个矩形块，每个矩形块的编码是字符串，矩形块内部编码一致（如果精度不再进一步细分的前提下），不同矩形块的编码是不同的。我们很自然的会以为，附件的点一定是在某个矩形块（某个精度）中，其实不然，对于矩形块的边界区域，很可能存在两个点地理上很近，但是被划分在不同的矩形块中，所以，我们在查找附近的点的时候，势必要求我们还需要对当前矩形块周围的 8个矩形块同时搜索，减少附件点的遗漏。
关于 Z 阶曲线的数学特性和不同数据库空间索引的比较，可以查看后面的文献，加深理解。
参考：
阅读(1840) | 评论(0) | 转发(0) |
