精华内容
下载资源
问答
  • 常见空间索引方法

    万次阅读 多人点赞 2018-05-21 15:51:17
    在谈论空间索引之前,我们必须了解索引的概念。索引是为了提高数据集的检索效率。打个比喻,一本书的目录就是这本书的内容的“索引”,我们查看感兴趣的内容前,通过查看书的目录去快速查找对应的内容,而不是...

            在谈论空间索引之前,我们必须了解索引的概念。索引是为了提高数据集的检索效率。打个比喻,一本书的目录就是这本书的内容的“索引”,我们查看感兴趣的内容前,通过查看书的目录去快速查找对应的内容,而不是一字一句地找我们感兴趣的内容。所以,索引是一种“前人栽树,后人乘凉”的东西。

            空间索引不同于书本“目录”,“目录”对应的书本内容是不变的,而我们讨论的空间索引是根据空间数据的改变而变化的,包括数据的创建、修改、删除等基本操作都会重新建立新的索引。空间数据是含有位置、大小、形状以及自身分布特征等多方面信息的数据,因其数据复杂性,我们需要一种索引去提高检索空间数据集合中空间数据的效率,减少空间数据操作时间。我们把检索空间数据集合的“目录”称作空间索引。

            基础的内容这里不多说,直接介绍常见的空间索引

    综合各种文献资料,把常用空间索引的方法大致分为以下几类:

     

     

    在介绍空间索引方法前,我们先介绍一种经典的索引法——B树索引,并介绍基于B树的索引方法。

     

    基于B树的索引方法

    B树索引

    B树,即二叉搜索树,结构特点:
        1. 所有非叶子节点至多拥有两个子节点(Left和Right);
        2. 所有的节点存储一个关键字;

        3. 非页子节点的左指针指向小于其关键字的子树,右节点指向大于其关键字的子树;

     

    实际的使用B树都是在B树的基础上加上平衡算法,是一种平衡多路查找树,其原理是把数据划分为树状层次索引,每个节点占一个存储块。该树所有的特点是:
        1. 定义任意非叶子子节点最多只有M个子节点,且M>2;
        2. 根节点的子节点数为[2,M];
        3. 除根节点意外的非叶子节点的子节点数为[M/2,M];
        4. 每个节点存放至少M/2-1(取上整)和至多M-1个关键字;(至少两个关键字)
        5. 非叶子节点的关键字个数=指向子节点的指针个数-1;
        6. 非叶子节点的关键字:k[1],k[2]…k[M-1],且k[i]<k[i+1];
        7. 非叶子节点的指针:p[1],p[2]....p[M];其中p[1]指向关键字k[1]的子树,p[M]指向关键字大于K[M-1]的子树,其他p[i]指向关键字属于(K[i-1],K[i])的子树;

        8. 所有叶子节点位于同一层;

     

    R树、R+树、R*树索引
    R树是空间数据索引结构中重要的一种层次结构,目前已成为许多空间索引方法的基础,不少前沿的空间索引都使用到R树或者对R树改良。其构建思想是以最小边界矩形(MBR)递归地对空间数据集的空间按照“面积”规划进行划分。它的特点如下:
        1. R树中非叶子节点代表一个划分的空间区域,即一个矩形空间区域;
        2. R树中的叶子节点包含的矩形区域对应空间对象的MBR;
        R+树主要针对R树中兄弟节点的MBR重叠后,导致空间搜索性能较差的特点提出的。R+树中,兄弟节点之间的MBR不允许重叠,这使得空间搜索的性能较好,但由于在插入和删除时需保证兄弟节点之间的MBR不能重叠,因此R+树的插入和删除操作的效率较低。
        R+树中间节点的所有矩形都是不相交的。如果一个对象的MBR被两个或多个R+树高层节点中的矩形分割,与这些非叶节点中矩形相联系的每个项都有指向这个对象的一个后继叶节点。这样树的高度增加,但搜索操作的性能会大大提高。

        R*树相对R树优化的地方是强制重新插入算法,R树中,插入操作导致节点溢出时,采用分裂的方法进行处理,R*树思路是:当新的空间对象索引项的插入导致节点溢出时,选择部分节点在同层节点间进行调整,以推迟节点分裂,从而达到优化R树整体结构的目的。基于R*树的空间索引算法提高了空间利用率,减少了节点分裂次数,但同时增加了CPU的计算代价。

    基于网格的空间索引

            网格索引的基本思想是将研究区域按一定规则用横竖线分为小的网格,记录每个网格所包含的地理对象。当用户进行空间查询时,首先计算查询对象所在的网格,然后通过该网格快速查询所选的地理对象。网格索引算法大致分为三类:基于固定网格划分的空间索引算法、基于多层次网格的空间索引算法和自适应层次网格空间索引算法。
    基于固定网格的空间索引

        将一幅地图分割成a*b的固定网格,再根据一定的方法将网格编码,为落入每个格网内的地图目标建立索引,这样只需检索原来区域的1/a*b,以达到快速检索的目的。该算法的优点是操作简单,在涉及的数据量不大、不需要进行复杂操作时具有一定的适应性。例如对点对象的检索特点适合使用。

            常用的网格编码方法有行排序、Z排序和Hilbert值排序,其中Hilbert值排序最能反应空间邻近性。因此,基于Hibert曲线分形的算法被广泛应用到空间索引中。

    基于多层次网格的空间索引

        将一幅地图分割成若干大小相同的小块,将落入该小块内的地图目标存入该小块、块对应的存储区域中,根据需要可以将小块划分成更小的块,建立多级索引。该算法的优点是检索的效率比较高,相比于纯粹的网格索引减少了特定的比较次数。但是网格划分的精细程度无法保证最优。对处于网格边缘的对象没有一个很好的解决办法,没有考虑到地图目标的水平与垂直分布对网格划分的影响。

    自适应层次网格空间索引算法

        其网格大小由各具体的地图目标的外接矩形决定,避免了网格索引中网格划分的人为因素。算法的优点是网格划分稳定自动,以各地图目标的外接矩形的大小作为划分依据,避免了重复存储,在存储效率上有一定改善。不足就是算法实现复杂,建立索引前,必须知道各地图目标外界矩形的长、宽,按其面积大小排序;建立索引后,进行插入或删除操作时,涉及的地图目标的外接矩形面积若不是原有面积大小,则需要重新进行排序,效率反而会下降。

     

     

    基于二叉树的空间索引

    四叉树空间索引

            四叉树索引可能是最早的专门为存取空间数据而设计的数据结构,不仅可用于二维变量,也可以用于任意维数。它是二叉树用于二维数据的一种推广。
    四叉树索引,类似于网格索引,也是对地理空间进行网格划分,对地理空间递归进行四分来构建四叉树,直到自行设定的终止条件(比如每个节点关联图元的个数不超过3 个,超过 3 个,就再四分),最终形成一颗有层次的四叉树。它的特点如下
        1. 每个叶子节点存储了本区域所关联的图元标识列表和本区域地理范围;
        2. 非叶子节点仅存储本区域地理范围。

    由于四叉树的生成和维护比较简单,且当空间数据对象分布比较均匀时,基于四叉树的空间索引可以获得比较高的空间数据插入和查询效率。如下两图:

     

    KD树——K近邻算法的实现

            K邻近算法在这里就不提及了,KD树(K维搜索树)是把二叉树推广到多维数据的一种主存数据结构,它是一个K维空间中的平衡二叉树,主要用于存储点数据。在每一个内部节点中,它用一个k-1维的超平面(如二维空间的线)将节点所表示的k维空间分成两个部分,这些超平面在k个可能的方向上交替出现,而且在每一个超平面中至少包括一个点数据。在KD树中查找一个所有维都给定值得对象的处理如同在二叉树中一样,只需在每个内部节点上决定沿哪个走向,直至搜索到叶节点为止。

            假设有6个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},数据点位于二维空间内,如下图八所示。为了能有效的找到最近邻,kd树采用分而治之的思想,即将整个空间划分为几个小部分。首先,粗黑线将空间一分为二,然后在两个子空间中,细黑直线又将整个空间划分为四部分,最后虚黑直线将这四部分进一步划分。

    6个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}构建kd树的具体步骤为:
        1. 确定:split域=x。具体是:6个数据点在x,y维度上的数据方差分别为39,28.63,所以在x轴上方差更大,故split域值为x;
        2. 确定:Node-data = (7,2)。具体是:根据x维上的值将数据排序,6个数据的中值(所谓中值,即中间大小的值)为7,所以Node-data域位数据点(7,2)。这样,该节点的分割超平面就是通过(7,2)并垂直于:split=x轴的直线x=7;
        3. 确定:左子空间和右子空间。具体是:分割超平面x=7将整个空间分为两部分:x<=7的部分为左子空间,包含3个节点={(2,3),(5,4),(4,7)};另一部分为右子空间,包含2个节点={(9,6),(8,1)};

            如上算法所述,kd树的构建是一个递归过程,我们对左子空间和右子空间内的数据重复根节点的过程就可以得到一级子节点(5,4)和(9,6),同时将空间和数据集进一步细分,如此往复直到空间中只包含一个数据点。如此便成了下面这样一棵k-d树:

        关于KD的内容很多,我就简单阐述到这里。

     

    KDB树

        KDB树兼有KD树和B树的特性,以B树的方式进行插入和删除,是完全平衡的,且可以进行局部重组,她的主要缺陷是不能保证最小空间利用率。KDB树是B树享多味空间发展的一种形式。它对于多维空间中的点进行索引,具有较好的动态特性,删除和增加地理要素可以很方便地实现。其缺点是不直接支持占据一定空间范围的地理要素,如2维空间中的线和面。

    BSP树

        BSP表示二叉空间分割,BSP树能很好地与空间对象的分布情况相适应,但对一般情况而言,BSP树深度较大,对各种操作均有不利影响。
        它的基本思想是基于这样一个事实,任何平面都可以将空间分割成两个半空间。所有位于这个平面的一侧的点定义了一个半空间,位于另一侧的点定义了另一个半空间。此外,如果我们在任何半空间中有一个平面,它会进一步将此半空间分割为更小的两个子空间。我们可以使用多边形列表将这一过程一直进行下去,将子空间分割得越来越小,直到构造成一个二叉树。在这个树中,一个进行分割的多边形被存储在树的节点,所有位于子空间中的多边形都在相应的子树上。当然,这一规则使用于树中每一个节点。

        假设某多边形的平面投影如图十,在它上面,所有多边形都能映射为直线段

        多边形B所在的平面将空间分割为两个部分,使得多边形D和E位于同一个半空间中,多边形C在另一个半空间中。在这个例子中, 多边形A穿越了两个半空间。接下步骤一和二:

            现在已经将问题分成了两个子问题。我们可以在子树中再次使用上述算法,在左边子树中选择E作为分割多边形,在右边子树中选择A2作为分割多边形。这样,我们将建立图十的BSP树,如图十一步骤2。

            必须注意,任何给定的BSP树都不是唯一的。我们可以对同样的多边形找到多个有效的二叉分割方法。根据我们的选择来进行分割的多边形的顺序,可以得到不同的树。

     

    空间索引方法的比较

     

    新型空间索引

     

        目前,成熟的空间索引包括R树索引、网格索引、四叉树索引等等,在实际运用中具有新算法的空间索引很少,基本都是结合上述的空间索引中的一种或两种以上,融合它们的特点变成新的空间索引。

    PostGis的通用搜索树

     

        数据库对多维数据的存取有两种索引方案,R-Tree和GiST(Generalized Search Tree)简称“通用搜索树”,在PostgreSQL中的GiST比R-Tree的健壮性更好,因此PostGIS对空间数据的索引一般采用GiST实现。

    通用搜索树是一棵平衡树,其特点如下:

     

        1.  除根节点的扇出数在2和M之间外,每个节点的扇出数在kM和M之间,这里2/M<=k<=1/2。常量k称作该树的最小填充因子,M为一个节点可以容纳索引项的最大数目。

        2.  索引项形式为(p,ptr),其中p是用作搜索码的谓词(谓词中可以包含自由变量,只要相应子树中叶节点标识的所有元组能实例化这些变量即可)。在叶节点中,ptr为指向数据库中某一元组的指针;而在非叶结点中,ptr为指向其子树根结点的指针。

        它是一种可扩展的树型索引结构框架。这里的“可扩展”包含 层意思:一是支持数据类型的可扩展性;二是支持查询谓词的可扩展性。

     

    QR树——基于R树与四叉树的空间索引

        从R-树的特征出发,为了提高查找性能,减少索引空间重叠,避免或减少查找分支,而引入索引空间的“四叉树”层次划分方法,将整个索引空间划分为多级子索引空间,然后对每级的子索引空间均采用R-树进行索引。其实质是将一棵“大”的R-树分解成多课“小”的R-树(即一群R-树的集合)将查询尽可能限定在局部空间区域,从而提高查找性能。

    实验证明,与R树相比,QR树以略大的空间开销为代价,换取了更高的性能,且索引目标数越多,QR树的整体性能越好。

     

    HR树——基于Hilbert分形曲线的空间索引

        上文阐述网格索引时,提及到网格编码方式中有一种叫Hilbert值编码方式。空间数据沿着Hilbert曲线的特性编码成为Hilbert码。

        基于Hilbert码的R树建立思想是:先将待索引的空间对象按照最小外包矩形MBR的中心的Hilebert码值进行排序分组,然后按照自底而上的模式生成R树。这种算法可以获得几乎100%的空间利用率,而且查询性能优于会产生节点分裂的R树系列。

     

    展开全文
  • C++常见空间索引效率对比

    千次阅读 2014-09-09 20:30:59
    由于打算写一个空间数据引擎,在空间索引和属性索引方面搜集了一些开源实现,本文用以对比C++ GIS开发中常见空间索引实现的效率 测试环境 操作系统 Windows 7 Professional SP1 ...

    第一篇博客,感谢下带我这个门外汉入了GIS行业的导师李治江老师~


    由于打算写一个空间数据引擎,在空间索引和属性索引方面搜集了一些开源实现,本文用以对比C++ GIS开发中常见的空间索引实现的效率


    测试环境

    操作系统 Windows 7 Professional SP1
    CPU Inter Core i7-3520M @ 2.9GHz
    内存 8GB
    系统盘硬盘 SanDisk SDSSDXP120G
    数据盘硬盘 HGST HTS725050A7E630
    开发环境 Visual Studio 2008 SP1

    实验对象

    空间筛选的大致流程基本都是:
    1. 矩形框初筛,通过待查询矩形框与数据外包矩形相交快速判断
    2.对初筛后缩小了的数据集进行相交、包含、相切、相离等精确判断
    空间索引就是提高第一步矩形运算效率的算法
    其实不管什么实现,矩形相交的快速判断方法是固定的,四个边界数值的比较,除非写汇编、写机器码,否则不太有提升空间。而空间索引的算法优劣,主要在于如何减少无关数据的访问次数
    空间数据至少是二维数据,常用的一维索引(如BTree/Bitmap索引等)无法满足需求,常用的空间索引算法有BSP树、K-D-B树、R树、R+树和CELL树(摘自百度百科,补充四叉树)。
    本文要对比的是一些常见的C++空间索引开源实现
    loop 最原始的循环,每个节点都访问
    shapelib-qix shapelib提供的默认空间索引算法,基于四叉树的实现。支持硬盘、内存两种模式
    shapelib-sbn 从gdal-1.10起添加的对ArcGIS生成的sbn格式的空间索引支持,笔者将其编译入了最新的shapelib中。仅支持硬盘模式
    geos geos提供了若干种空间索引算法,本文对其中的STRTree和QuadTree分别进行了测试。仅支持内存模式
    spatialindex 提供了多种基于RTree的空间索引算法,还包括时空GIS所需要的多版本索引算法等。本文仅对二维数据索引,因此仅探讨RTree。支持硬盘、内存两种模式

    对比方法

    测试数据

    郑州市矢量数据
    数据类型:Line
    数据量:1554304条
    x_min:454250.000000
    x_max:479750.045600
    y_min:3839499.634654
    y_max:3862000.032000
    空间参考:Xian_1980_3_Degree_GK_CM_114E

    对比逻辑

    对上述数据的打开数据、创建索引、索引查询范围R内数据n次、相关清理作为一次完整流程,记录索引创建时间、索引内存占用情况、查询时间、查询到数据结果数量作为横向对比参考。重复如上操作t次,取平均值。
    其中
    R:x_min:465701.923
    R:x_max:469994.306
    R:y_min:3852567.173
    R:y_max:3855717.229
    n:100
    t:5

    对比结果

    Method Mode Insert(ms) Memory(MB) Query(ms) QueryCount 说明
    Loop-vector Memory 2801.2 77.274219 1523.8 60854 使用std::vector作为数据的存取容器
    Loop-list Memory 2856.4 106.534375 1367.2 60854
    使用std::list作为数据的存取容器
    Loop Disk 0.0 0.000000 264532.0 60854
    打开数据逐条IO判断
    Qix Memory 3499.8 75.525781 745.8 62240 在内存中创建qix索引查询
    Qix Disk 3730.6 0.000000 2010.2 62240 使用硬盘中的qix索引查询
    Sbn Disk 0.0 10.158594 898.2 63047 使用硬盘中的sbn索引查询
    Geos-STRTree Memory 3100.4 136.578125 2878.8 60854
    在内存中创建geos::strtree索引查询
    Geos-QuadTree Memory 4194.4 302.792969 383.4 64288 在内存中创建geos::quadtree索引查询
    SpatialIndex-RTree Memory 83795.2 72.734375 3087.8 60854
    在内存中创建rtree索引查询(原始insert接口)
    SpatialIndex-RTree Memory-BulkLoad 13041.0 90.471875 2874.6 60854
    在内存中创建rtree索引查询(使用bulkload提升创建速度)
    SpatialIndex-RTree Disk-BulkLoad 13348.8 18.336719 4249.6 60854
    使用硬盘中的rtree索引查询(使用bulkload提升创建速度)


    优缺点对比


    优点 缺点
    qix 1.索引速度极快
    2.支持硬盘、内存两种模式
    1.仅支持shp数据(仔细研究下代码应该也能把索引部分跟SHPHandle的耦合解开)
    sbn 1.硬盘索引速度极快 1.暂无生成sbn的代码,仅能用作只读索引
    2.仅支持shp数据
    3.仅支持硬盘模式(不过速度其实已经很快了,是否内存化可能不太重要)
    geos 1.内存四叉树索引速度为最快 1.仅支持内存模式(对数据量过大的情况应对性不好)
    2.geos源码中存在一处内存释放未决,需要使用者对插入索引树的内存做管理,使用较为不便(建议修改源码)
    3.内存占用较大
    spatialindex 1.支持硬盘、内存两种模式 1.索引生成较慢(做大数据量的实时编辑数据时可能会有效率问题)

    综上考虑,可能会在后续的索引中使用spatialindex

    对比缺陷

    哎,说到缺陷,还请各位看客多多留下宝贵意见

    1.最最百思不得其解的是,除了四叉树的两个索引算法和sbn索引,其他索引居然都比内存生生循环要慢,真是打脸打的厉害啊。。。

      2014-09-10 自圆其说的一种解释

    2.对比没有考虑不同数据特点下索引算法的优劣,如数据外包矩形均匀分布或有明显集中是否有影响

    3.对不同算法中的可控参数尚未做纵向对比

    4.未对比更大数据量的索引稳定性(之前使用过sqlite的rtree,发现超过1000万条记录就会导致索引建立极慢无比,且因为sqlite的rtree实现是通过虚表+关联外键方式实现,实用性较差,因此没有放在此次对比中)


    附上源码,敬请指正:

    http://pan.baidu.com/s/1kTJttrh


    展开全文
  • GIS空间索引

    万次阅读 2020-03-11 12:02:02
    常见的GIS空间索引 KD树空间索引(二叉树索引)、KDB树索引 R树、R+树空间索引 G树索引 四叉树索引及其分类(点四叉树索引、MX四叉树索引、PR四叉树索引、CIF四叉树索引、基于固定网格划分的四叉树索...

    微信搜索:“二十同学” 公众号,欢迎关注一条不一样的成长之路

    在GIS系统中,空间索引技术就是通过更加有效的组织方式,抽取与空间定位相关的信息组成对原空间数据的索引,以较小的数据量管理大量数据的查询,从而提高空间查询的效率和空间定位的准确性。

    常见的GIS空间索引

    1. KD树空间索引(二叉树索引)、KDB树索引
    2. R树、R+树空间索引
    3. G树索引
    4. 四叉树索引及其分类(点四叉树索引、MX四叉树索引、PR四叉树索引、CIF四叉树索引、基于固定网格划分的四叉树索引)
    5. CELL树索引
    6. BSP树空间索引

    1.关于KD树

    在计算机科学里,k-d树(k-维树的缩写)是在k维欧几里德空间组织点的数据结构。k-d树是每个节点都为k维点的二叉树。所有非叶子节点可以视作用一个超平面把空间分区成两部分。在超平面左边的点代表节点的左子树,在超平面右边的点代表节点的右子树。超平面的方向可以用下述方法来选择:每个节点都与k维中垂直于超平面的那一维有关。因此,如果选择按照x轴划分,所有x值小于指定值的节点都会出现在左子树,所有x值大于指定值的节点都会出现在右子树。这样,超平面可以用该x值来确定,其法矢为x轴的单位矢量。(来自维基百科

    GIS中的KD树

    KD树的基本形式存储了K维空间点。KD树的每个内部节点都包含一个点,并且和一个矩形区域相对应。树的根节点和整个研究区域相对应。树中奇数层次上的点的X坐标和偶数层次上的点的Y坐标把矩形区域分成两部分。在KD树结构中,通过沿着树下降到达一个树叶节点的方式来添加一个新点。KD树的查找是从根节点开始,查看所存储的节点(分裂的点)是否被包括在查找范围内以及和左子树或者右子树是否有交叠。对于每个和查询范围交叠的子树,查询过程将重复执行直到到达树叶那一级为止

    示意图如下:

     

    KD树的每个内部结点都包含一个点,每个结点表示k维空间中的一个点,并且和一个矩形区域相对应,树的根结点和整个研究区域相对应。KD树要求用平行于坐标轴的纵横分界线将平面分为若干区域,使每个区域中的点数不超过给定值。树中奇数层次上的点的x坐标和偶数层次上的点的y坐标把矩形区域分成两部分。分界线仅起分界的作用,它的选取没有硬性的限制。一般选用通过某点的横向线或者纵向线。分界线上的点,对左右分界线来说属于右部,对上下分界线来说属于上部。 如图:

    KD树查找

    伪代码

    Algorithm KD_Search(R,P)
    /*在根结点为R的KD树(子树)中查找点P。找到则返回结点,否则返回NULL*/
    Begin
      If R=NULL Then Return NULL;//Not Found
      If R. Point=P Then Return R;//Found;
    Else
      Begin
        d:=Discriminator of R;
        If P[d] <R Point[d] Then /*比较P点与R结点的第D维的值*/
          KD_Search(R.Lchild,P)//在左子树继续查找
        Else
          KD_Search(R.Rchild,P)//在右子树继续查找
      End
    End.

    KD树插入

    伪代码

    Algorithm KD_Insert(R,P,F)
    /*在根结点为R的KD树(子树)中插入点P,F为R的父结点*/
    Begin
      If R=NULL Then
        Begin
          Create a Node P;
          If F=NULL Then //KD树为空
            Root:=P//P成为根结点
          Else
            If R Is the Left child of F Then
              F.Lchild:=P//P作为F的左孩子
            Else F.Rchild:=P//P作为F的右孩子
        End
        Else
          Begin
            d:=Discriminator of R;
            If P[d]R.Point[d] Then/*比较P点与R点的第D维的值*/
              KD_Insert(R.Lchild,P,R)//插入到左子树中
            Else
             KD_Insert(R.Rchild,P,R)// 插入到右子树中
         End;
    End;

    KD树删除

    Algorithm KD_Delete(R,P)
    /*在根结点为R的KD树(子树)中点P,删除成功返回True,否则返回False */
    Begin
          Q:= KD_Search(R,P);//Q为要删除的对象
          LABEL;
          If Q=NULL Then Return False;//Not found
          If (Q.Lchild=NULL) And (Q.Rchild=NULL) Then
            Begin//第一种情况
              F:=Q is Father Node;
              If Q is the left Child of F then
                F.Lchild:=NULL
              Else F.Rchild:NULL;
                Delete Node Q;
              Return True;
           End
        Else
          Begin
             If (Q.Rchild=NULL) Then第三种情况转化为第二种情况处理
                Q.Rchild:=Q.Lchild;
             M:=FindMin(Q.Rchild);
          (Q)←(M);//将M结点的值赋给Q结点
            Q:=M;//让Q指向M结点
            GOTO LABEL;//继续删M结点
        End
    end

    KDB树是KD树与B树的结合,它由两种基本的结构——区域页(region pages,非叶结点)和点页(point pages,叶结点)组成。如图所示

     

    点页存储点目标,区域页存储索引子空间的描述及指向下层页的指针。在KDB树中,区域页则显式地存储了这些子空间信息。区域页的子空间(如s11,S12和s13)两两不相交,且一起构成该区域页的矩形索引空间(如S1)即父区域页的子空间。

    KDB-tree包括两种类型的页:

    • 区域页面: (region, child)对的集合包含边界区域的描述,加上该区域指向子页面的指针。
    • 点页面:(point, location)对的集合。数据库方面,location可能指向数据库记录的索引,对于K维空间中的点,可以被看成该空间中的点坐标。

    当向KDB树插入元素时,导致节点的规模超过它的最优规模,页面溢出。因为KDB-tree的目的是优化外部内存访问,例如硬盘访问,当节点的规模超过外部内存页大小,一个叶被认为是溢出。通过插入和删除操作,KDB树保持一些属性:

    • 该图是一个多叉树,区域页面指向子页面,并且不能为空。点页面是叶子节点。
    • 对于所有查询,到达叶节点的路径长度是相同的。
    • 如果根节点是区域页面,区域的联合是整个搜索空间。
    • 当一个区域页面的(region, child)对的儿子也是一个区域页面,所有儿子区域的联合是该页面。
    • 如果儿子是一个点页面,儿子中所有点必须被该区域包含。

     

    2.关于R树,R+树

    R树是一种多级平衡树,它是B树在多维空间上的扩展。在R树中存放的数据并不是原始数据,而是这些数据的最小边界矩形(MBR),空间对象的MBR被包含于R树的叶结点中。在R树空间索引中,设计一些虚拟的矩形目标,将一些空间位置相近的目标,包含在这个矩形内,这些虚拟的矩形作为空间索引,它含有所包含的空间对象的指针。虚拟矩形还可以进一步细分,即可以再套虚拟矩形形成多级空间索引。

    R树索引是一种高效的空间索引,它是B树在多维空间的扩展,也是平衡树。R树的结构类似于B+树的平衡树。

     

    R树及其特点

    对于一棵M阶的R树,R树中每个非叶子结点都由若干个(p,MBR)数据对组成。MBR(Minimal Boundary Rect)为包含其对应孩子的最小边界矩形。这个最小外接矩形是个广义上的概念,二维上是矩形,三维空间上就是长方体MBV(Minimum Bounding Volume),以此类推到高维空间。p是指向其对应该子结点的指针。

    叶子结点则是由若干个(OI,MBR)组成,其中MBR为包含对应的空间对象的最小外接矩形。OI是空间对象的标号,通过该标号可以得到对应空间对象的详细的信息。

    R树查找

    伪代码如下:

    Algorithm R_Search(N,W) {
        /*在根结点为N的R树中查找所有与W相交的数据矩形*/
    
        if (N.LEVEL==0) //N是叶子结点
            //  Return all data rectangles that intersect with W;
        else //N不是叶子结点
            for (i=1;i<N.COUNT;i++)
                if (N.MBRi;Intersect with W)
                  R_Search (N.pi,W);
    }
    

     

    R树插入

    伪代码如下:

    Algorithm R_Insert(N,P){
    /*向根结点为N的R树中插入数据矩形P*/
      if (N.LEVEL==0) {
            Insert P into N;
            if (N overfill) Split N;
        }
      else {//N是中间结点
          // Choose the entry in N whose rectangle needs 
          // least area enlargement to include the new data rectangle.
          // Resolve ties by choosing the entry with the rectangle of
          // smallest area (Let's suppose it's entry is the answer)
          R_Insert(N.pi,P);
          // Adjust N.MBRi to enclose all rectangle in its child node;
        }
    }
    

    R树删除

    伪代码如下:

    Algorithm R_Delete(N,P){
    /*从根结点为N的R树中删除数据矩形P*/
      if (N:LEVEL==0) 
      {//N是叶结点
          if (N包含P)
          {
              // 从N中删除P
              N.COUNT=N.COUNT-1;
              return true;
          }
          else
              return false;
      }
      else
      {
          for (i =1;i<N.COUNT;i++)
              if (N.MBRi intersects with P)
                if (R_Delete(N.pi,P))
                    if (N.pi,COUNT=m)
                        // Adjust N.MBRi to enclose all child's rectangles;
                    else
                    {
                        // Reinsert all remain entries of N.pi and delete N.pi;
                        // if N underfilled, Reinsert alI         
                        // remain entries of it and
                        // delete it too...;〗
                    }
      }
    }
    

     

    地图对应的R树结构

     

    关于R+树

    在R树的构造中,要求虚拟矩形一般尽可能少地重叠,并且一个空间对通常仅被一个虚拟矩形所包含。但空间对象千姿百态,它们的最小矩形范围经常重叠。 R+ 改进R树的空间索引,为了平衡,它允许虚拟矩形相互重叠,并允许一个空间目标被多个虚拟矩形所包含。

    R+树索引的主要特征是在R+树中兄弟节点对应的空间区域没有重叠,这样划分空间可以使空间搜索的效率提高。R+树也是R树的一个变种,在R+树中,兄弟节点对应的空间区域没有重叠,这样划分空间可以使空间搜索的效率提高。R+树对空间的划分及其索引对象的MBR组织如下:

     

    R+树查找

    算法Search(R,W)/R:R+树的根结点,W:查找矩形窗口/

    S1.[查找中间结点]
    If R是非叶结点 then
      For R的每一索引项(p,MBR) DO
          If MBRW then Search(p,WMBR)
    S2.[查找叶子结点]
    If R是叶子结点 then
      检查R的每一数据项(OI,MBR)
      RETURN所有与W相交的数据矩形
    

    由查找算法可知,与R树相比,对于区域查找,查找路径应该可以减少,但依旧可能有多条;对于点查找,则可以通过一条路径得到查找结果。

    R+树插入

    Algorithm Insert(R,IR){ 
    /*R为R+树的根结点,IR为要插入的数据矩形*/
        I1.[查找中间结点]
        if (R是非叶结点) then
            for (p,MBR) do
              if (MBRIR0) Insert(CHILD,IR);
        I2.[查找叶子结点]
        if (R是叶结点) then
          if (R已有M个数据项)then SplitNode(R);
          else 插入IR于R;
    }
    

     

    R+树删除

    Algorithm Delete (R,IR){ 
    /*R为R+树的根结点,IR为要删除的数据矩形*/
    Dl.[查找中间结点]
    if (R是非叶结点)then
      for R的每一索引项(p,MBR)do
        if (MBRIR0) then Delete(CHILD,IR);
    D2.[查找叶子结点]
    if (R是叶结点) then
      从R中删除IR且调整R的父结点中对应的目录矩形;
    }
    

    结点分裂

    Algorithm SplitNode(R){
    SN1[寻找一个划分]
    调用Partition;
    // 设(p,MBR)为与R相关联的索引项,S1与S2表示划分得到的两个子区域,
    // 创建两个新结点n1=(p1,MBR1)与n2=(p2,MBR2),MBRi=MBRSi,i=1,2;〗
    SN2[填充新结点]
    For (R的每一项(pk,MBRk) do
      if (MBRkMBR==MBRk) then // MBR k完全包含于MBRi
          put(pk,MBRk) in ni;
      else // MBR k与MBR1及MBR2都重叠。
          if (R是叶结点) then
            put (pk,MBRk) in n1 与n2;
          else
            〖用划分线继续分裂(pk,MBRk)所指结点,设得到的新结点为:nk1= 
          (pk1,MBRk1),nk2=(pk2,MBRk2),MBRki完全包含于MBRi,将  
              nki加入到ni,i=I,2;〗
    SN3[向上传播结点分裂操作]
    if (R是根结点)
        创建一新根结点,n1与n2为其两孩子结点;
    else
      // 在R的父结点PR中,用n1与n2替换R。
      // 如果PR的索引项个数超过M,那么调用SplitNode(PR)。
    }
    

    3.G树

    G树是一种多层次的动态生长的格网结构。与KD树类似,G树也按照循环交替的方式分割空间,但是它是采取平均分割空间的方法。假设各维的值,即有关的属性值,都能规范到0到1之间的值,并且每个区域中不能超过2点。如果超过2点,继续循环交替分割空间,直至每个区域不超过2点为止

     

    这种空间分割策略有3个特点:

    1. 区域的二进制编码是全序的;
    2. 分割所得的区域集合构成平面的一个划分;
    3. 区域的二进制编码的位数越多,则该区域越小,它是其编码前缀所代表的区域的子空间

    4.四叉树索引及其分类

    在GIS中,四叉树索引又分为很多种类,包括点四叉树、PR四叉树、MX四叉树、CIF四叉树等

    <1>点四叉树(Point Quadtree)

    点四叉树与KD树相似,两者的差别是在点四叉树中,空间被分割成四个矩形。四个不同的多边形分别是:SW、NW、SE、NE。其搜索过程和KD树相似,当一个点包含在搜索范围内时被记录下来,当一个子树和搜索范围有交叠时它将被穿过。下图:点四叉树示意图

    点四叉树是QuadTree的一个变种,主要是针对空间点的存储表过与索引(Finkel and Bentley,1974),与KD树相似,两者的差别是在点四叉树中,空间被分割成四个矩形,四个不同的多边形对应于SW、NW、SE、NE四个象限。

    对于k维数据空间而言,以新插入的点为中心将其对应索引空间分为两两不相交的2k个子空间,依次与它的2k个孩子结点相对应,对于位于某一子空间的点,则分配给对应的子树。

    点四叉树的每个结点存储了一个空间点的信息及2k个孩子结点的指针,且隐式地与一个索引空间相对应。其搜索过程和KD树相似,当一个点包含在搜索范围内时被记录下来,当一个子树和搜索范围有交叠时它将被穿过。如果想从Point QuadTree中删除一个点的话,则会引起相应的子树的重建,一个简单的方法是将所有子树上的数据重新插入。如图是二维空间的一棵点四叉树的例子。

    优势&劣势

    点四叉树的优点是结构简单,对于精确匹配的点查找性能较高。

    其缺点有:

    1. 树的动态性差,删除结点处理复杂;
    2. 树的结构由点的插入顺序决定,难以保证树深度的平衡;
    3. 区域查找性能较差;
    4. 对于非点状空间目标,必须采用目标近似与空间映射技术,效率较差;
    5. 不利于树的外存存储与页面调度;
    6. 每个结点须存储2k个指针域且其中叶子结点中包含许多空指针,尤其是当k较大时,空间存储开销大,空间利用率低。

    <2>PR四叉树(Point Region Quadtree)

    PR四叉树是点四叉树的一个变种,它不使用数据集中的点来分割空间。在PR四叉树中,每次分割空间时,都是将一个正方形分成四个相等的子正方形,依次进行,直到每个正方形的内容不超过所给定的桶量(比如一个对象)为止。下图:PR四叉树

    PR四叉树是点四叉树的一个变种,它不使用数据集中的点来分割空间。在PR四叉树中,每次分割空间时,都是将一个正方形分成四个相等的子正方形,依次进行,直到每个正方形的内容不超过所给定的桶量(比如一个对象)为止。

    PR四叉树与MX四叉树的主要区别是:

    1. 叶子结点可能不在树的同一层次;
    2. PR四叉树的叶结点数及树的深度都小于MX四叉树,因此PR四叉树的检索效率要高于MX四叉树。

     

    <3>MX四叉树

    空间被分割成四个矩形。四个不同的多边形分别是:SW、NW、SE、NE。每次分割空间时,都是将一个正方形分成四个相等的子正方形,依次进行,直到每个正方形的内容不超过所给定的桶量(比如一个对象)为止。

    所有的数据都处在四叉树的同一个深度,多个点可以由一个指针联接。

    MX四叉树索引即Matrix四叉树索引。在k维空间中,整个数据空间被分割成四个矩形。四个不同的多边形对应于SW、NW、SE、NE四个象限。每次分割空间时,都是将一个正方形分成四个相等的子正方形,依次重复地进行2k次等分,直到每个正方形的内容不超过所给定的桶量(比如一个对象)为止,空间中的每一点都属于某一象限且位于该象限内,每一象限均只与一个空间相关联。

    在MX四叉树中,叶子结点的黑结点或空结点分别表示数据空间某一位置空间点的存在与否。如图所示为二维空间的一棵MX四叉树的例子。

    <4>CIF四叉树

    CIF(Caltech Intermediate From)四叉树是针对表示VLSI(Very Large Scale Integration)应用中的小矩形而提出的,它可以用于索引矩形及其他形体。

    它的组织方式与区域四叉树相似,数据空间被递归地细分直至产生的子象限不再包含任何矩形。在分解的过程中,与任一划分线相交的矩形与该划分线对应的象限相关联,属于一个象限的矩形不能属于祖先象限,换句话说,矩形只属于完全包围它的最小象限。

    下图是二维空间一颗CIF树的例子(这里假设数据桶的容量为3个矩形)。

     

    <5>基于固定网格划分的四叉树索引

    先看下图:

    非叶结点数:MAX_NONLEAFNODE_NUM=∑N−1i=04i∑i=0N−14i

    叶结点数:MAX_LEAFNODE_NUM=2^N×2^N=4N

    非叶结点从四叉树的根结点开始编号:

    从0到MAX_NONLEAFNODE_NUM-1

    叶子结点则从MAX_NONLEAFNODE_NUM开始编号,

    直到MAX_NONLEAFNODE_NUM+MAX_LEAFNODE_NUM-1

    在四叉树中,空间要素标识记录在其外包络矩形所覆盖的每一个叶结点中,但是,当同一父亲的四个兄弟结点都要记录该空间要素标识时,则只将该空间要素标识记录在该父亲结点上,并按这一规则向上层推进。

    在基于固定网格空间划分的四叉树空间索引机制中,二维空间范围被划分为一系列大小相等的棋盘状矩形,即将地理空间的长和宽在X和Y方向上进行2^N等分,形成2^N×2^N的网格,并以此建立N级四叉树。

    在四叉树中,空间要素标识记录在其外包络矩形所覆盖的每一个叶结点中。但当同一父亲的四个兄弟结点都要记录该空间要素标识时,则只将该空间要素标识记录在该父亲结点上,并按这一规则向上层推进。

    把一幅2^n×2^n的图像压缩成线性四叉树的过程

    1. 按Morton码把图象读入一维数组。
    2. 相邻的四个象元比较,一致的合并,只记录第一个象元的Morton码。循环比较所形成的大块,相同的再合并,直到不能合并为止。 
    3. 进一步用游程长度编码压缩。压缩时只记录第一个象元的Morton码。

    解码时,根据Morton码就可知道象元在图像中的位置(左上角),本Morton码和下一个Morton码之差即为象元个数。知道了象元的个数和象元的位置就可恢复出图像了。

    1. 按Morton码读入一维数组。
      Morton码:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
      象 元 值: A A A B A B B B A A A A B B B B
    2. 四相邻象元合并,只记录第一个象元的Morton码。
      0 1 2 3 4 5 6 7 8 12
      A A A B A A B B A B
    3. 由于不能进一步合并,则用游程长度编码压缩。
      0 3 4 6 8 12
      A B A B A B

    <6>线性可排序四叉树索引

    •首先将四叉树分解为二叉树,即在父结点层与子结点层之间插入一层虚结点,虚结点不用来记录空间要素,然后按照中序遍历树的顺序对结点进行编码,包括加入的虚结点。

    假设某个结点位于四叉树的第N层,可排序四叉树编码为Index。它的四个子结点位于树的第N-1层,编码从左到右分别为:

    Index_C1=Index-3×4×(N-1) 

    Index_C2=Index-4×(N-1)

    Index_C3=Index+4×(N-1)

    Index_C4=Index+3×4×(N-1)

    通过编码值很容易确定结点在树中的层数。在进行查询时,给定一个查询范围,假定为矩形,这个矩形范围唯一的对应一个四叉树结点。通过结点的编码,可以快速计算出在这棵子树下的所有子结点。

    找子结点的范围的程序伪代码如下:

    GetIndexRange(long Index,long Min,long Max)
    {
      long  n = GetLayerNum(Index);
      Min = Max = Index;    
      While(n>0)
      {
        Min = Min- 3×4×(n-1);
        Max = Max-3×4×(n-1);
        n = n –1; 
      }
    }

    5.CELL树索引

    针对R树和R+树在插入、删除与空间搜索效率两个方面难于兼顾的问题,产生了CELL树索引。它在空间划分时不再采用矩形作为划分的基本单位,而是采用凸多边形来作为划分的基本单位,具体划分方法与BSP树有类似之处,子空间不再相互覆盖,如图:

     

    CELL树的磁盘访问次数比R树和R+树少,由于磁盘访问次数是影响空间索引性能的关键指标,因此大大提高了搜索性能,故CELL树是比较优秀的空间索引方法。

    6.BSP树空间索引

    BSP树(Binary Space Partitioning Tree,二值空间划分树)是一种二叉树,它将空间逐级进行一分为二的划分,如下图。BSP树能很好地与空间数据库中空间对象的分布情况相适应,但对一般情况而言,BSP树深度较大,对各种操作均有不利影响,所以在GIS系统中采用BSP空间索引的并不多见。如图:

    BSP的想法最早在Fuchs(1980)中被提出,起初的目的是为了解决实时地消除隐藏面。BSP可以说是八叉树的一般化。前人在这方面已经做了很多有效的工作,Fuchs首次将BSP技术中剖分平面的定侧性质应用于多边形场景的剖分,建立起空间二叉树结构.该二叉树的每一结点表示一个子空间及空间内所包含的多边形。在每一结点空间中,选取其中一平面作为剖分平面,将该空间继续剖分成正负两子空间,分别作为该结点的两个子结点,其中与剖分平面有交的多边形被分割成两个多边形,分别归入相应的子空间中。上述过程是一个递归过程,直至每一子空间仅包含一个多边形为止。与八叉树剖分相比,BSP树具有内存耗费小,剖分方式灵活,产生的无效区域较小的优点;且对大部分场景来说,BSP树较八叉树更为平衡。

     

    生成过程:

    最初,整个区域被定义为 BSP树的根。之后,你继续划分区域。一旦把凹形区域划分为两个凸形区域(在最好情况下)或凹多边形,命名这些区域,它们成为其父结点的孩子,父结点实际上代表了整个区域。

    优缺点

    BSP树能很好地与空间对象的分布情况相适应,但一般而言,BSP树深度较大,对各种操作均有不利影响。 使用BSP树来进行从后向前排序的最大优点就是算法运行的复杂性较低 。这种方法也解决了多边形的多重交叠和多边形穿越问题。但是,通过使用一个预计算结构,我们已经失去了一定的灵活性。如果多边形的排列在运行时发生了改变, BSP树就必须发生相应的改变。

    展开全文
  • 几种常见空间索引分类及特点

    千次阅读 2012-07-25 10:18:28
    这里是空间索引的概括介绍,点击下载 2.1 网格索引  网格索引的基本思想是将研究区域按一定规则用横竖线分为小的网格,记录每个网格所... 三类:基于固定网格划分的空间索引算法、基于多层次网格的空间索引

    这里是空间索引的概括介绍,点击下载


    2.1   网格索引

              网格索引的基本思想是将研究区域按一定规则用横竖线分为小的网格,记录每个网格所包含的地理对象。当用户
             进行空间查询时,首先计算查询对象所在的网格,然后通过该网格快速查询所选的地理对象。网格索引算法大致分为
              三类:基于固定网格划分的空间索引算法、基于多层次网格的空间索引算法和自适应层次嘲格空间索引算法。
             2.1.1基于基于固定网格划分的空间索引算法将一幅地图分割成a*b的固定网格,为落入每个格网内的地图目标建立索引,
             这样只需检索原来区域的I,矿b,
             以达到快速检索的目的。该算法的优点是操作简单,在涉及的数据量不大、不需要进行复杂操作时具有一定的适应性。
             2.1.2基于多层次网格的空闻索引算法将一幅地图分割成若干大小相同的小块,将落入该小
             块内的地图目标存入该小块、块对应的存储区域中,根据需要可以将小块划分成更小的块,建立多级索引。该算法的优
             点是检索的效率比较高,相比于纯粹的网格索引减少了特定的比较次数。但是网格划分的精细程度无法保证最优。对
             处于网格边缘的对象没有一个很好的解决办法,没有考虑到地图目标的水平与垂直分布对网格划分的影响。
             2.1.3自适应层次网格空间索引算法
             其网格大小由各具体的地图目标的外接矩形决定,避免了网格索引中网格划分的人为因素。算法的优点是网格
             划分稳定自动,以各地图目标的外接矩形的大小作为划分依据,避免了重复存储,在存储效率上有一定改善。不足就
             是算法实现复杂,建立索引前,必须知道各地图目标外界矩形的长、宽,按其面积大小排序:建立索引后,进行插入或删
             除操作时,涉及的地图目标的外接矩形面积若不是原有面积大小,则需要重新进行排序,效率反而会下降.
    2.2  四又树索引
             四义树索引,类似于网格索引,也是对地理空间进行网格划分,对地理空问递归进行四分来构建四义树,
             直到自行设定的终止条件(比如每个节点关联图元的个数不超过
             3个,超过3个,就再四分),最终形成一颗有层次的四叉树。每个叶子节点存储了本区域所关联的图元标识列表和本区
             域地理范围,非叶子节点仅存储本区域地理范围。由于四叉树的生成和维护比较简单,且当空问数据对
             象分布比较均匀时,基于四叉树的空问索引可以获得比较高的空间数据插入和查询效率。
    2.3   R树家族索引
             这是+。种面向对象分割技术的索引算法,将空问对象按范围划分,每个节点都对应一个区域和磁盘页,非页节点
             的磁盘页中存储着其予节点的区域范围;叶节点的磁盘页中存储着其区域范围内的所有空问对象的外接矩形。
            2.3.I基于R树的空间索引算法
             R树算法是一种层次数据结构动态索引算法,它是B树在K维空间上的自然扩展,是一种高度平衡树。R树由根节点、中问节点和叶节点三类节点组成,
             中问节点代表数据集空问中的一个矩形,该矩形包含了所有其他孩子节点的最小外接矩形,叶节点存储的是实际对象的外接矩形。
             R树允许节点相互覆盖,这种覆盖可以使R树保持较高的空问利用率和保持树的平衡。相比网格索弓l,无需预知
             整个研究区域的索引范围就能建立空问索引,减少了大地理对象的存储冗余。由于它是按数据来组织索引结构,是一
             种完全动态的索引结构,不需要周期性的索引重组。但是节点之间的过多覆盖不能保证检索路径的唯一性,有的甚至
             会检索整个树,造成查询效率的降低。 .
             2.3.2基干R+树的空间索引算法
             Sellis在1987年提出了R十树。R十树与R树类似,区别在于R+树中兄弟节点对应的空问区域无重叠,这样就消
             除了R树划分空间时因允许节点重叠而产生的死区域,减少无效查询次数,提高空间索引的效率,但插入删除操作则
             效率降低。R+树中间节点的所有矩形都是不相交的。如果一个对象的MBR被两个或多个IH树高层节点中的矩形分割,与
             这些非叶节点中矩形相联系的每个项都有指向这个对象的一个后继叶节点。这样树的高度增加,但搜索操作的性能会有很大提高。
             2.3.3基于R+树的空间索引算法
             Beckmann于1990提出了R+树。R.树相对于R树优化的地方是强制重新插入算法,其思路是:当新的空问对
             象索引项的插入导致节点溢出时,选择部分节点在同层节点问进行调整,以推迟节点分裂,从而达到优化R树整体结
             构的目的。基于R·树的空间索引算法提高了空间利用率,减少了节点分裂次数,但同时增加了CPU的计算代价.
    2.4  金字塔索引
             Berchtold于1998年提出了金字塔方法,该方法基于一种特殊的优化高维数据的不均衡分割策略,其原理是先将
             d维空问分成2d个金字塔,共享数据空间的中心点为顶点,然后再将每个金字塔分割成平行于金字塔基的数据页。金
             字塔索引结构是将高维数据转化为一维数据,利用B+树进行操作。金字塔索引结构的优点是当处理范围查询时,这种索引结构的性能优子其他的索引结构,
             而且查询处理效率不会随着维数的增加而降低,原因在于在处理范周查询时充分利用了金字塔空问中相近的点在B+树中更有可能在B+
             树的同一个数据页上这个事实。但金字塔索引结构的优点是基于均匀数据分布和超立方体查询的,对于那些覆盖数
             据空问边界的查询不是很理想,而现实世界中的数据很少是服从均匀分布的.
    3结论
             在这些索引中,不同的索引有各自的优点和缺点以及适用范围。需要选取哪种空问索引方法,要根据实际情况和
             需求来确定。实际应用中也是采用多种索引结构的方法,取长补短。高效的空问索引方法一‘直是很多学者专家研究的
             课题,有很多问题需要进。‘步的解决的例如高效索引树算法的改进、复杂空问查询方法的优化以及查询插入操作中
             算法的优化。
    展开全文
  • ArcSDE空间索引

    千次阅读 2014-06-23 11:08:14
    为了提高空间查询的性能,ArcSDE采用空间索引的机制。是一个覆盖整个要素类的两维索引,类似于一般的道路图上的索引网格。ArcSDE可以赋予三层空间索引网格,每个网格层都具有自己的格网大小。第一层网格为必需,它的...
  • 空间数据库之空间索引

    千次阅读 2017-12-15 18:11:37
    空间数据库 空间索引 网格索引 四叉树索引 R树索引 金字塔索引 空间查询效率
  • GIS空间索引技术

    千次阅读 2011-01-18 13:11:00
    常用的空间索引技术介绍和比较:  网格空间索引、四叉树空间索引和R树系列空间索引最为常见。    目前国内外主要的空间数据库也大都采用网格空间索引、四叉树 与 R树 这三类的空间索引结构...
  • 索引的类型和常见索引

    千次阅读 2018-03-02 14:48:16
    索引的类型(索引有很多种类型,在mysql中,并没有统一的索引标准,不同的存储引擎的索引的工作方式并不一样,也不是所有的存储引擎都支持所有类型的索引) 1、B-Tree索引 大多数MySQL引擎都支持这种索引,对索引列是...
  • 数据库常见索引

    千次阅读 2019-05-31 22:16:05
    1.什么是索引 数据库索引好比是一本书前面的目录,能加快数据库的查询速度。 2.索引的优缺点 优点: 1.大大加快数据的检索...1.索引需要占用数据表以外的物理存储空间 2.创建索引和维护索引要花费一定的时间...
  • 常见高维索引技术

    千次阅读 2014-12-13 23:21:45
    四叉树类似于前面介绍的网格索引,也是对地理空间进行网格划分,对地理空间递归进行四分来构建四叉树,本文将在普通四叉树的基础上,介绍一种改进的四叉树索引结构。首先,先介绍一个GIS(Geographic Information ...
  • 前言:在很多系统中,比如本人目前管理的数据库,索引经常被滥用,甚至使用DTA(数据库引擎优化顾问)来成批创建索引(DTA目前个人认为它的真正用处...一个表甚至20多个索引索引的数量并没有标准,但是要尽量
  • 在我们遇到很多关于性能的问题,我们一般建议用户重新常见空间索引,那么如果用户一个库里面几十个甚至上百个空间索引,那么该怎么处理呢? ArcGIS10.1版本 RebuildIndexes:(这个功能只有ArcGIS10.1才的)...
  • 空间索引(Spatial Index)是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构 ,其中包含空间对象的概要信息,如对象的标识、外接矩形及指向空间对象实体的指针。(不知所云,...
  • GeoMesa源码学习:空间索引

    千次阅读 2019-01-05 20:12:39
    分布式空间索引可以说是GeoMesa的灵魂了,它直接决定了空间数据的:(1)行主键(2)数据分区与负载均衡(3)索引高效查询。所以说要想真正了解GeoMesa的核心代码,必须要把索引这一部分弄懂吃透。空间索引方法是...
  • GIS空间索引(1)--概述

    千次阅读 2013-09-12 15:32:08
    空间索引 (spatial index) 为便于空间目标的定位及各种空间数据操作,按要素或目标的位置和形状或空间对象之间的某种空间关系来组织和存储数据的结构。 索引 对一个数据集做“索引”,是为了提高对这个数据集检索...
  • 说说Mysql索引,看到一个很少比如:索引就好比一本书的目录,它会让你更快的找到内容,显然目录(索引)并不是越多越好,假如这本书1000页,500也是目录,它当然效率低,目录是要占纸张的,而索引是要占磁盘空间的...
  • 数据库常见索引结构

    千次阅读 2019-07-12 15:18:42
    常见的平衡二叉树:AVL,RBT,Treap,Splay Tree。   B-树 是一种多路搜索树(并不是二叉的):  1.定义任意非叶子结点最多只有M个儿子;且M>2;  2.根结点的儿子数为[2, M];  3.除根结点...
  • 先思考个常见的问题:如何根据自己所在位置查询来查询附近50米的POI(point of interest,比如商家、景点等)呢(图1a)? 每个POI都经纬度信息,我用图1b的SQL语句在mySQL中建立了POI_spatial的表,其中lat和lng...
  • 前言: 在很多系统中,比如本人目前管理的数据库,索引经常被滥用,甚至使用DTA(数据库引擎优化顾问)来成批创建索引(DTA目前个人认为它的真正用处应该...一个表甚至20多个索引索引的数量并没有标准,但是要尽量
  • Mysql索引面试常见问题

    千次阅读 2020-03-18 23:30:02
    常见的问题: 1)Mysql常用到的存储引擎:MySIAM和Innodb 2)索引的实现级别是表级别 索引为什么不用二叉树? 二叉树的高度不可控,避免出现深度过大的情况 索引为什么不用btree Degree 节点的数据存储个数 :叶...
  • Mysql索引结构及常见索引的区别

    万次阅读 2017-08-09 11:39:43
    一、Mysql索引主要两种结构:B+Tree索引和Hash索引 Hash索引 mysql中,只有Memory(Memory表只存在内存中,断电会消失,适用于临时表)存储引擎显示支持Hash索引,是Memory表的默认索引类型,尽管Memory表也可以...
  • Mysql常见四种索引的使用

    万次阅读 2015-06-25 15:12:38
    提到mysql优化,索引优化是必不可少的。其中一种优化方式 ——索引优化,添加合适的索引...接下来总结一下mysql常见的四种索引 一. 四种索引(主键索引/普通索引/全文索引/唯一索引) 1.索引的添加  1.1主键索引的添加
  • 在我们遇到很多关于性能的问题,我们一般建议用户重新常见空间索引,那么如果用户一个库里面几十个甚至上百个空间索引,那么该怎么处理呢?ArcGIS10.1版本RebuildIndexes:(这个功能只有ArcGIS10.1才的) 这...
  • 数据库常见的四种索引 1.普通索引:主要以B+树和哈希索引为主,任务是加快对数据的访问速度,常用于查询和排序的条件,值可以为空并没有唯一性的限制 2.唯一性索引:与普通索引类似,不同的是唯一性索引索引列的值...
  • SDE空间索引的内部运行机制2

    千次阅读 2010-12-17 13:56:00
    2.2.1各种矢量数据存储类型的空间索引的实现方式 ArcSDE从开始到现在主要支持以下几种存储类型: 存储类型 数据库 SDELOB Oracle,SQLServer,DB2 ST_GEOMETRY Oracle,DB2,PostgresQL,Informix ...
  • 常见索引: 主键索引(primary key) 唯一索引(unique) 普通索引(index) 全文索引(fulltext) 1. 主键索引(primary key) 一个表中,最多一个主键索引,当然可以使符合主键 主键索引的效率高(主键不可重复) ...
  • 数据库常见面试题——索引

    千次阅读 2019-07-31 16:38:02
    索引模块 为什么要使用索引 快速查询数据 什么样的信息能够成为索引 主键、唯一键以及普通键等 索引的数据结构 生成索引,建立二叉查找树进行二分查找树(平衡二叉树、红黑树) 生成索引,建立B-Tree结构进行...
  • 性能测试常见指标有哪些

    千次阅读 多人点赞 2020-03-10 17:50:44
    行业参考标准: 为了最大利用内存,在内存中存放了缓存,因此内存利用率100%并不代表内存瓶颈,衡量系统内存是否瓶颈主要靠SWAP(与虚拟内存交换)交换空间利用率,一般低于70%,太多的交换将引起系统性能低下...
  • 面试官:索引优化策略有哪些

    千次阅读 2019-12-23 15:17:37
    从逻辑上可以分为:普通索引,唯一索引,主键索引,联合索引,全文索引 索引优化策略 不要在索引列上进行运算或使用函数 在列上进行运算或使用函数会使索引失效,从而进行全表扫描。如下面例子在publish_time,id列...
  • 说说Mysql索引,看到一个很少比如:索引就好比一本书的目录,它会让你更快的找到内容,显然目录(索引)并不是越多越好,假如这本书1000页,500也是目录,它当然效率低,目录是要占纸张的,而索引是要占磁盘空间的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 170,429
精华内容 68,171
关键字:

常见的空间索引有哪些