|
先看几个需要空间索引技术的场景： 如何根据给定位置来查询附近1000米的poi？ 如何查找给定位置的最近poi? 如何查找给定矩形框内所有link和面数据？ 1.用B-tree、B tree或者hash算法对空间数据建索引可以吗？ B-tree是平衡多路查找树，在节点上及其子节点上存放有序的关键字，非叶子节点关键字数等于指向子树指针数减1；查找从根节点开始，叶子节点和非叶子节点都有可能命中。 B-tree树形结构图 B tree的非叶子节点子树指针数和关键字数相等，所有关键字都存储在叶子节点中，非叶子节点不存储数据，只存储关键字，为叶子节点增加链表指针；查找也从根节点开始搜索，到叶子节点才能命中。性能等价于对关键字全集做一次二分查找。更适合做文件索引系统。 B tree树形结构图 hash索引用hash值指针指向关键字位置； 这三种索引都是基于关键字，不能满足二维及多维空间信息索引。 2.根据空间点数据特性，我设计了一种基于二分查找的一种简单快速查找最近poi的算法 对每个poi计算一个到原点的距离，按地区编码adcode和这个原点距离两个字段排序，并计算出每个adcode的开始索引和结束索引，当根据给定位置查找最近poi时，先按adcode查找到这个adcode的开始索引和结束索引，再根据原点距离，查找到其buffer内的记录，然后向两头分别查找，当超出buffer范围时跳出，通过比较找到最近poi。也可以通过这种方法计算出附近范围内的所有poi。 这个算法预先处理出基于数组的数据，有效划分了数据集合，时间复杂度接近略高于二分查找，有较高的查找性能。 优点：编程实现简单，比较适合点数据 缺点：当没有adcode字段时查找性能会大幅下降，线、面、圆、多边形等数据类型基本不可用。传统的这几种数据结构不能满足多类型多场景查询空间数据的索引！ 3.几种高级空间索引算法：网格空间索引、四叉树、R树、kd-tree 1)网格空间索引 将平面等分成网格，是一种平均划分，用哈希数据结构，索引项上记录落入该网格的空间对象，用下图方式将相应空间对象记录到每个索引网格中，建立索引。 网格空间索引图1 查找某个矩形框内空间对象时，确定所画矩形左上角和右下角所在的网格数组元素；即可得到这个矩形所关联覆盖的所有网格集合，然后即可通过索引获取到其中的空间对象。 网格索引图2 网格越多查找性能越好，但是空间冗余度越高，网格太少，划分就越少，就降低了查找性能。 优点：在点数据建网格索引，没有数据冗余，有广泛应用 缺点：在线、面等空间数据有很大数据冗余，查询效率也明显下降。 2)四叉树 Quadtree 将已知范围的空间等分成四个相等的子空间，当空间对象分布比较均匀时，具有较高的插入和查询效率，但同样存在一个空间元素被多个区域所索引，相应存储在多个叶子节点上，也存在索引的冗余。R树是对四叉树的优化。 四叉树图1 优点：通过将数据空间逐层细分来组织数据，结构和操作比较简单，实现比较方便。 缺点：有索引冗余，一旦索引建立树层次被固定，无法根据数据空间对象的变化调整树高，可调节性差。 3)R树 主要采用空间分割的理念，采用MBR最小边界矩形的方法，从叶子节点开始用矩形将空间框起来，节点越往上，框住的空间就越大。 R树图1 以此对空间进行分割：所有原始空间元素都是叶子节点，这样就不会出现网格索引和四叉树空间要素被多个索引指引的情况，从而避免了大量索引冗余的问题。所有叶子节点都是空间对象。查找时候从根节点开始，找到哪些矩形区域与检索矩形相交，一层一层查找到检索矩形内的空间对象。 优点：有很强灵活性和可调节性，建树无须预知整个空间对象所在空间范围，也有较高的执行效率。 缺点：索引空间经常重叠，造成树深度和存储空间的增加，导致遍历时间增加，查询效率下降。 4)Kdtree K-dimensional (k-维树的简称)，是一种分割k维数据空间的数据结构，主要用于多维数据的搜索和数据挖掘中高维数据范围查询和k近邻查询。kd树是个二叉树，每个子节点是一个空间范围，这种划分空间没有重叠。 kd树中每个节点的数据类型如下： kdtree图1 根据方差确定split值，根据中值计算data-node值，左子空间和右子空间重复根节点过程，就可以得到下一级子节点。 假设有6个二维数据点{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，数据点位于二维空间内。 由于此例简单，数据维度只有2维，所以可以简单地给x，y两个方向轴编号为0,1，也即split={0,1}。 （1）确定split域的首先该取的值。分别计算x，y方向上数据的方差得知x方向上的方差最大，所以split域值首先取0，也就是x轴方向； （2）确定Node-data的域值。根据x轴方向的值2,5,9,4,8,7排序选出中值为7，所以Node-data = （7,2）。这样，该节点的分割超平面就是通过（7,2）并垂直于split = 0（x轴）的直线x = 7； （3）确定左子空间和右子空间。分割超平面x = 7将整个空间分为两部分，如图2所示。x < = 7的部分为左子空间，包含3个节点{（2,3），（5,4），（4,7）}；另一部分为右子空间，包含2个节点{（9,6），（8,1）}。 查找最近邻：比如要搜索图4中星号点(2.1,3.1)，从根节点开始，通过二叉搜索顺着搜索路径很快就能找到最近邻的近似点,也就是叶子节点(2,3)，该叶子节点不一定是最近邻节点，需要沿搜索路径再回溯计算最近邻点，看其父节点的其他子节点是否是更近邻节点。 优点：空间二维或多维点数据构建索引和查询效率较高，在矩形范围查询场景也有较高效率（通过二叉树节点数据的比较即可查到数据）。 缺点：线、面等复杂空间数据类型不太适用。 4.应用场景 link按行驶方向的连接、 道路分层静态数据处理、 线上实时矩形框内poi查询、 最近邻poi点查找 5.JAVA第三方组件JTS中的空间索引类 上边说到的空间索引算法自己编程实现有一定难度，JTS较好支持了这几种空间索引算法，使用起来较为方便。 四叉树Quadtree类:org.vividsolutions.jts.index.quadtree; Kdtree类:com.vividsolutions.jts.index.kdtree.KdTree; Rtree类:com.vividsolutions.jts.index.strtree.STRtree; |
|
|
