既然涉及的是旅游搜索，那就不能少了空间搜索的内容。现在移动设备之广泛想必不必多说。根据eMarketer的新[数据](http://www.chinabgao.com/stat/stats/39758.html)，2015年全球智能手机用户将达到19.1亿，2016年该指数将增长12.6%达到21.6亿。智能手机都会带有GPS模块，现在一个APP不获取下用户位置都觉得是吃亏，不过这也用户隐私的侵犯也很严重，尤其是在Android生态圈中，不过现在各大手机厂商的系统都对这一块做了一些限制。

空间搜索，又名Spatial Search，基于空间搜索技术，可以做到：

<!--more-->

1. 对Point（经纬度）和其他的几何图形建索引
2. 距离计算：根据给定点计算它到其他点的距离。
3. 限定框过滤器：查找某些特定区域内所有匹配项（文档）。
4. 排序：根据到固定点的距离对搜索结果进行排序。
5. 相关度改进：使用距离作为记录中的增强因素，同时允许其他因素发挥作用。
6. 查询解析：在给出位置的地址或其他一些用户规定时，创建可用于根据索引数据进行搜索的编码表示。

# 空间搜索原理
在Solr中，空间搜索主要基于GeoHash和Cartesian Tiers 2个概念来实现。下面先来讲解一下这两个算法，虽然这两种算法可以很容易在网上找到资料，但是我在这里对其进行总结，并根据之前自己的知识和相似的技术、算法思想进行对比。后面将会是和Solr相关的如何进行配置和查询，虽然这些算法的实现比较复杂，好在Solr已经帮我们做好了，通过配置就可以使用。当然这里最需要感谢的美团的技术团队，这么无私的把这些技术分享出来，我基本上是靠美团的这篇文章来完成了这个模块的工作。

## GeoHash算法
GeoHash即Geology和Hash的组合，使用hash算法的方法对地理信息进行编码，要想充分了解GeoHash，我们先来了解Hash。
### 各种Hash及其核心思想
>Hash(散列)算法，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。

计算机中有关Hash的应用有很多的，例如java的HashMap、Hash Table、数据加密、数据完整性、错误校正等方面都有应用。它的基本思想上面的Wikipedia已经定义的比较好了，我来分享下我的见解，hash就是把数据按照某种规则进行重组再表示，这个再表示比原始的数据量要小，其实是有损的转换，因此不能从再表示中还原数据。另外由于再表示的取值空间比较小，会有不同的原始数据经过Hash之后得到相同的再表示，这也就意味着冲突，好的转换规则能最低限度的降低冲突概率。

和GeoHash比较相近的应用是Hash Table，它通过关键码值（Key value）来访问数据，把key通过一个hash函数生成Hashcode，这个Hashcode对应一个位置，而其value就放在这个位置，相当于是key和value所在位置的一个映射。我们知道线性的数据结构能够通过index(下标)来快速获取数据（非线性需要遍历才能找到），我们可以直接把下标当做key，这样的`<key,value>`也可以快速找到，但希望的是key可以是任何字符，那么经过hash函数的转换，Hash Table应运而生。

Hash Table是为了解决查询速度的问题，GeoHash当然也是为了解决这个问题，它主要解决的是地理位置的查找，不过其复杂程度比Hash Table高一些，不过也算比较容易理解。

### GeoHash初识
其实GeoHash就是将二维的经纬度转换成字符串，并且这些字符串有个特征是同一个地区的前缀N位是相同的，如果两点的GeoHash字符串前缀相同的位数越多表示这两点越接近，因此将距离的计算转换成字符串相同位数的比较，虽然是其基本原理如此常见，但运算量的减小确是非常巨大的。

为了能让大家对我上面说的概念有个更直观的了解，于是我很恬不知耻地借用别人的图片来给大家看，也是蛮拼(lan)的。
![](https://fliaping-blog.oss-rg-china-mainland.aliyuncs.com/storage/blog/14641705440976.jpg)
上图可以看到每一个字符串代表了一个矩形区域（为啥是矩形不是方形？下面再说），只要是这个区域内的所有点经过GeoHash算法之后前5位一定是相同的。这就有个好处，那就是缓存啊，把数据按照区域缓存起来加快访问速度和减小负载，真是机智。

![](https://fliaping-blog.oss-rg-china-mainland.aliyuncs.com/storage/blog/14641710035781.jpg)
上面的图是啥意思呢？字符串越长，表示的范围越精确。5位的编码能表示10平方千米范围的矩形区域，而6位编码能表示更精细的区域（约0.34平方千米），也就是说在大格子里面画小个子，也从正面说明了前缀相同的位数越多表示这两点越接近。
### GeoHash算法步骤
我们都知道地球的纬度为-90~90，经度为-180~180，我就用美团这篇文章的数据来讲吧。例如纬度为39.92324，经度为116.3906（这货真懒）
#### 二分编码
1) 对区间[-90,90]进行二分为[-90,0),[0,90]，称为左右区间，可以确定39.92324属于右区间[0,90]，给标记为1；
2) 接着将区间[0,90]进行二分为 [0,45),[45,90]，可以确定39.92324属于左区间 [0,45)，给标记为0；
3) 递归上述过程，39.92324总是属于某个区间[a,b]，随着每次迭代区间[a,b]总在缩小，并越来越逼近39.928167；
4) 如果给定的纬度（39.92324）属于左区间，则记录0，如果属于右区间则记录1，这样随着算法的进行会产生一个序列1011 1000 1100 0111 1001，序列的长度跟给定的区间划分次数有关。
![](https://fliaping-blog.oss-rg-china-mainland.aliyuncs.com/storage/blog/14641716776526.png)
5) 同理，地球经度区间是[-180,180]，对经度116.3906进行编码的过程也类似的二分编码，过程如下：
![](https://fliaping-blog.oss-rg-china-mainland.aliyuncs.com/storage/blog/14641717242233.png)
#### 组码&Base32编码
通过上述计算（图中只显示16次二分，共20次），纬度产生的编码为`1011 1000 1100 0111 1001`，经度产生的编码为`1101 0010 1100 0100 0100`。偶数位放经度，奇数位放纬度。因为经纬度都分别二分了20次，现在要组合成一个二十位数，这个数从左往右（纬度表示为lat，经度表示为lng）


|40|39|38|37|36|...|
|