基于Solr的空间搜索(1)

http://ju.outofmemory.cn/entry/709

在Solr中基于空间地址查询主要围绕2个概念实现：

Cartesian Tiers 笛卡尔层

Cartesian Tiers是通过将一个平面地图的根据设定的层次数，将每层的分解成若干个网格，如下图所示:

 每层以2的评方递增，所以第一层为4个网格，第二层为16 个，所以整个地图的经纬度将在每层的网格中体现：

笛卡尔层在Lucene中对空间地理位置查询最大的用处在查找周边地址的时候有效的减少查询量，即将查询量可以控制在分层后最小的网格中的若干 docId。那么如何构建这样的索引结构呢，其实很简单，只需要对应笛卡尔层的层数来构建域即可。也即是 tiers0->field_0，tiers1->field_1,tiers2- field_2,……，tiers19->field_19。（一般20层即可）。每个对应笛卡尔层次的域将根据当前这条记录的经纬度通过笛卡尔算 法计算出归属于当前层的网格，然后将gridId（网格唯一标示）以term的方式存入索引。这样每条记录关于笛卡尔0-19的域将都会有一个 gridId对应起来。但是查询的时候一般是需要查周边的地址，那么可能周边的范围超过一个网格的范围，那么实际操作过程是根据经纬度和一个距离确定出需 要涉及查询的从19-0（从高往低查，留给读者思考）若干层对应的若干网格的数据（关于代码实现在后面的文章内容阐述）。那么一个经纬度周边地址的查询只 需要如下图圆圈内的数据：

所以通过这样的数据过滤，将极大的减少计算量。

GeoHash算法

在Lucene索引中将经纬度的二维坐标通过geohash，变成一个一维的字符串base32的坐标，例如，经纬度对应一个base32的坐标为 DRT2Y，那这个base32的字符串什么意思呢？其实编码中每个字符都是代表一个区域，并且前面的字符是后面字符的父区域，即R是D区域内的子区 域，T又为D区域的子区域，大家可以从如下图片获得base32的层级关系（以下图片均来自互联网）：

进入D区域，则看到又分为若干区域，而R为其子区域：

继续进入R区域，可以继续看到有子区域T区域：

而2Y也是基于以上的关系类推，所以一个base32的编码是标示一个区域，而编码过程中会根据经纬度的精度来确定这个区域大小。从上面的解释大家 肯定会想到编码的前缀是表示更大的区域。例如wx4g0ec1，它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大区域。所以根据这个特点，利 用模糊查询是可以达到一种附近地点的查询。

Geohash算法实现其实非常简单，网上有很多例子，在这里借用下这些例子再加上比较详细的说明。基本算法流程是基于多轮的收敛，以达到满足精度 要求为止。具体流程以(39.92324 纬度, 116.3906 经度)为例，首先将纬度的范围(-90, 90)平分成两个区间(-90, 0)、(0, 90)，如果目标纬度位在（-90,0），则编码为0，在（0,90）则编码为1。由于上面的例子中维度39.92324是属于(0, 90)，所以第一轮获得的编码位取1。接下来再将(0, 90)分成 (0, 45), (45, 90)两个区间，而39.92324位于(0, 45)，所以编码为0。以此类推，直到精度符合要求为止，如下图所示：

所以通过16轮的计算后得到经度39.92324的编码为：1011 1000 1100 0111 1001

经度也用同样的算法，对(-180, 180)多轮的依次细分计算：

得到经度116.3906的编码为1101 0010 1100 0100 0100

经纬度的编码都计算完毕后，接下来就需要合并经纬度的编码，规则是以经度开始，依次每次取一位合并成5位的新编码，如上图红色字标示顺序所示：

完成合并编码后就需要将该编码和base32编码表对应起来，做法是每5位为一个十进制数，以11100为例，它的十进制数是28，所以对应的base32编码表示W，如下图所示：

其他的五位编码依次从表中找到对应位置后，(39.92324 纬度, 116.3906 经度)的base32编码为：wx4g0ec1

解码算法与编码算法相反，先进行base32解码，然后分离出经纬度，最后根据二进制编码对经纬度范围进行细分即可，这里不再赘述。不过由于geohash表示的是区间，编码越长越精确，但不可能解码出完全一致的地址

而关于Solr+Lucene使用Cartesian Tiers 笛卡尔层和GeoHash的构建索引和查询的细节介绍将在新的Blog中阐述。