空间索引

1、使用索引，适合建立索引的数据结构是【Hash】和【树】
2、可能索引方案包括：B树，网格索引，四叉树索引、R树索引、GeoHash
3、B树是针对一维数据【单个字段】使用，空间对象（点、线、面）是多维数据

通用二维数据解决方案（点、线、面）
1、网格索引
（1）索引实现：使用Hash数据结构实现，单位网格对应于HashMap中的一个桶，该网格关联的对象对应存储在相应桶的链表中
（2）局限性：网格索引在对象空间分布均匀时效率比较高
如果空间对象分配不均匀，那么最终会得到大量空白网格，浪费存储空间
网格尺寸不好确定，太大则索引效率低，太小则形成很多空白空格

2、普通四叉树索引
（1）索引实现：递归地对空间进行四等分，从而建立一个四叉树。通过叶节点挂接数据，并且只有叶点存储数据，根节点和中间节点不存储数据
（2）局限性：
如果空间对象分配不均匀，那么最终构造出来的是层次比较深的不均衡树，最终导致查询的效率下降
同一个对象在不同叶节点中重复存储
（3）四叉树索引改进
将地理实体信息存储在完全包含它的最小矩形节点中，每个地理实体只在树中存储一次，避免了存储空间的浪费
（4）四叉树在对象空间分布均匀时效率比较高

3、R树索引
是B树在高纬空间的扩展，是一棵平衡树。R树采用了空间分割的理念，具体是使用“最小外包矩形”，从叶子节点开始用矩形将空间框起来，节点越往上，框住的空间越大，以此对空间进行分割。

将二维数据转换为一维数据的解决方案GeoHash（适合于点对象）
（1）索引实现：分别根据点对象的经度和纬度分别进行【区间划分】到【符合一定精度的程度】，分别编码，然后合并，最后进行base32编码得到可以比较的字符串编码
例如wx4g0ec1，它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索。首先根据用户当前坐标计算geohash（例如wx4g0ec1）然后取其前缀进行查询 （SELECT * FROM place WHERE geohash LIKE ‘wx4g0e%’），即可查询附近的所有地点
（2）GeoHash编码表示的是矩形区域，而不是具体点；该矩形区域内的所有兴趣点拥有相同的编码
地理围栏
地理围栏（Geo-fencing）是LBS的一种应用，就是用一个虚拟的栅栏围出一个虚拟地理边界，当手机进入、离开某个特定地理区域，或在该区域内活动时，手机可以接收自动通知和警告
实现思路：首先对地理围栏（多边形）建立R树索引，以便能快速找到覆盖目标位置的外包矩形（进而定位到多边形围栏），然后再依据射线法判断点是否在多边形内部

四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间，如此递归下去，直至树的层次达到一定深度或者满足某种要求后停止分割。四叉树的结构比较简单，并且当空间数据对象分布比较均匀时，具有比较高的空间数据插入和查询效率，因此四叉树是GIS中常用的空间索引之一。常规四叉树的结构，地理空间对象都存储在叶子节点上，中间节点以及根节点不存储地理空间对象。

四叉树对于区域查询，效率比较高。但如果空间对象分布不均匀，随着地理空间对象的不断插入，四叉树的层次会不断地加深，将形成一棵严重不平衡的四叉树，那么每次查询的深度将大大的增多，从而导致查询效率的急剧下降。

一、空间索引有哪几种？

　　传统索引使用哈希和树这两类最基本的数据结构。空间索引虽然更为复杂，但仍然发展于这两种数据结构。因此可以将空间索引划分为两大类：1）基于哈希思想，如网格索引等；2）基于树思想，有四叉树、R树等。
　　

二、网格索引

　　哈希是通过一个哈希函数将关键字映射到内存或外存的数据结构，如何扩展到空间数据呢？

2.1. 网格索引原理

　　扩展方法：对地理空间进行网格划分，划分成大小相同的网格，每个网格对应着一块存储空间，索引项登记上落入该网格的空间对象。

　　举个例子，我们将地理空间进行网格划分，并进行编号。该空间范围内有三个空间对象，分别是id=5的街道，23的河流和11的商圈。这时候我们可以按照哈希的数据结构存储，每个网格对应着一个存储桶，而桶里放着空间对象，比如对2号网格，里面存储着id=5的空间对象，对35号网格，桶里放着id=5和id=23的空间对象
　　
2.2. 网格索引缺点

1）索引数据冗余

　　网格与对象之间多对多关系在空间对象数量多、大小不均时造成索引数据冗余。比如11号商圈这个空间对象在68，69，100，101这4个网格都有存储，浪费了大量空间。

2）网格的大小难以确定

　　网格的划分大小难以确定。网格划分得越密，需要的存储空间越多，网格划分的越粗，查找效率可能会降低
　　
3）很多网格没有数据

　　空间数据具有明显的聚集性，比如POI只在几个热点商贸区聚集，在郊区等地方很稀疏，这将导致很多网格内没有任何空间数据。
1 如何判断点在多边形内部
地理围栏一般是多边形，如何判断点在多边形内部呢？可以通过射线法来判断点是否在多边形内部。如下图所示，从该点出发沿着X轴画一条射线，依次判断该射线与每条边的交点，并统计交点个数，如果交点数为奇数，则在多边形内部（如图3个交点），如果焦点数是偶数，则在外部，射线法对凸和非凸多边形都适用，复杂度为O(N)，其它N是边数。源码可参考（http://alienryderflex.com/polygon/）

当地理围栏多边形数目较少时，我们可以依次遍历每一个多边形（暴力遍历法），然后用射线法进行判断，这样效率也很高。而当多边形数目较多时，比如有10万个多边形，这个时候需要执行10万次射线法，响应时间达到3.9秒，这在互联网应用几乎不可忍受。

2 R树索引加速判断
暴力遍历法效率低下的原因是与每一个多边形都进行了射线法判断，如果能减少射线法的调用次数性能就能提升。因此我们的优化思路很直接，首先通过粗筛的方法快速找到符合条件的少量多边形，然后对粗筛后的多边形使用射线法判断，这样射线法的执行次数大大降低，效率也能大大提高。怎么粗筛呢？对于一维数据我们常常使用索引的方法，比如通过B树索引找到某一个范围区间段，然后对此范围区间段进行遍历查找，对于二维空间数据常常使用空间索引的方法，比如通过R树找到范围区间内的多边形，然后对此范围内的多边形进行精确判断，下面介绍最常使用的空间索引R树的解决思路。

   1）外包矩形表示多边形

   由于多边形形状各异，我们需要以一种统一的方式来对多边形进行近似，最简单的方式就是用最小外包矩形来表示多边形。

   

    2）对最小外包矩形建立R树索引

    

     3）查询

      a）首先通过R树迅速判断用户所在位置（粗红点）是否被外包矩形覆盖（图5，红色点代表用户所在位置；R树平均查询复杂度为O(Log(N))，N为多边形个数）；



      b）如果不被任何外包矩形覆盖则返回不在地理围栏多边形内；



      c）如果被外包矩形覆盖则还需要进一步判断是否在此外包矩形的多边形内部，采用上文提到的射线法判断（图2）。

3 多边形边数较多怎么办
大多数应用的地理围栏多边形都比较简单，但有时也会遇到一些特别复杂的多边形，比如单个多边形的边数就超过十几万条，这时候对此复杂多边形执行一次射线法也非常耗时（因为射线法时间复杂度为O(N)，N为多边形边数）。

   如何提高对复杂多边形执行射线法的计算效率呢？同样使用R树索引！笔者在实际应用中对边数较多（如超过1万）的多边形的边再单独进行R树索引，具体如图6所示，首先对多边形的每条边构建最小外包矩形，然后在这些最小外包矩形基础上构建R树索引（R树索引上的外包矩形未画出），这样射线法求交点的时候首先通过R树判断射线是否与外包矩形相交，最后对R树粗筛后的边进行精确求交判断，时间复杂度从O(N)降到O(Log(N))，大大提高了计算效率。