精华内容
下载资源
问答
  • postgis——空间索引
    千次阅读
    2020-01-20 15:05:02

    空间索引是postgis中十分重要的功能,一个数据库中如果不支持索引那几乎是没法使用的。postgis中空间索引通过将数据组织到搜索树中来加快搜索速度,搜索树可以快速遍历以查找特定记录。

    对于空间的几何图形,不是通过btree索引来加速查询,而是通过gist索引。gist索引是通过r_tree的结构来实现对空间类型数据的索引查询,其结构类似于btree索引。
    r树介绍:https://zh.wikipedia.org/wiki/R%E6%A0%91
    gist索引是怎么工作的呢?
    在这里插入图片描述
    比如上面这个图片,查询和黄星相交的对象,即是图中的红线,gist索引不能索引几何要素本身,而是索引几何要素的边界框(bouding box)。
    在这里插入图片描述
    所以在索引计算时,其实是先判断那些边界框和黄星所在的框相交,显然是红线和蓝线的框,然后再进行哪些直线与黄星相交的精确计算。

    使用语法:

    postgis=# create index idx_t_pos_1 on t_pos using gist(pos);
    CREATE INDEX
    

    对一张数据量1000的表进行全表扫描:

    postgis=# select count(*) from t_pos;
     count 
    -------
      1000
    (1 row)
    postgis=# explain (analyze,buffers,timing) select * from t_pos where pos && st_astext(' POINT(73.689759 3.880185)');
                                               QUERY PLAN                                            
    -------------------------------------------------------------------------------------------------
     Seq Scan on t_pos  (cost=0.00..21.50 rows=1 width=36) (actual time=0.012..0.600 rows=1 loops=1)
       Filter: (pos && '0101000000C9C7EE02256C52402670EB6E9E0A0F40'::geometry)
       Rows Removed by Filter: 999
       Buffers: shared hit=9
     Planning Time: 0.231 ms
     Execution Time: 0.612 ms
    (6 rows)
    

    加上索引,使用索引查询:

    postgis=# explain (analyze,buffers,timing) select * from t_pos where pos && st_astext(' POINT(73.689759 3.880185)');
                                                         QUERY PLAN                                                     
    --------------------------------------------------------------------------------------------------------------------
     Index Scan using idx_t_pos_1 on t_pos  (cost=0.14..8.16 rows=1 width=36) (actual time=0.057..0.058 rows=1 loops=1)
       Index Cond: (pos && '0101000000C9C7EE02256C52402670EB6E9E0A0F40'::geometry)
       Buffers: shared hit=3
     Planning Time: 0.228 ms
     Execution Time: 0.074 ms
    (5 rows)
    

    可以看到性能有了明显的提升!

    更多相关内容
  • GIS空间索引

    万次阅读 2020-03-11 12:02:02
    在GIS系统中,空间索引技术就是通过更加有效的组织方式,抽取与空间定位相关的信息组成对原空间数据的索引,以较小的数据量管理大量数据的查询,从而提高空间查询的效率和空间定位的准确性。 常见的GIS空间索引 KD...

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

    在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树就必须发生相应的改变。

    展开全文
  • 认识ArcGIS的空间索引

    千次阅读 2018-01-09 16:57:06
    在 ArcGIS 的地理数据库中创建空要素类或导入数据以创建新要素类时,将为要素类创建空间索引空间索引用于编辑和加载数据。 *在 DB2 的地理数据库中创建空要素类时,不会创建空间索引。 数据源不同,空间索引...

    1.概述

    ArcGIS 使用空间索引来提高要素类的空间查询性能。识别要素、通过点选或框选来选择要素以及平移和缩放都需要 ArcMap 使用空间索引来查找要素。

    在 ArcGIS 的地理数据库中创建空要素类或导入数据以创建新要素类时,将为要素类创建空间索引。空间索引用于编辑和加载数据。

    *在 DB2 的地理数据库中创建空要素类时,不会创建空间索引。

    数据源不同,空间索引的工作方式也不同。以下地理数据库类型中的要素类使用基于格网的空间索引:

    • 个人地理数据库
    • 文件地理数据库
    • DB2 中的地理数据库
    • 使用 Esri ST_Geometry 或二进制几何存储的 Oracle 地理数据库
    • 使用二进制几何存储的 SQL Server 地理数据库

    使用 Oracle Spatial (SDO_Geometry) 存储、Informix 和 PostgreSQL 的 Oracle 要素类不使用基于格网的空间索引 — 它们使用 R 树索引。同样,使用 SQL Server 空间类型的要素类不使用 Esri 基于格网的空间索引。


    2.原理

    Oracle 和 DB2 中的 ArcSDE 地理数据库使用格网索引。空间索引通过将格网应用到空间列中的数据构建而成。空间格网索引是二维的,并且涵盖一个要素类范围,类似于一般道路地图上的参考格网。您可以将空间格网索引划分为成一个、两个或三个格网等级,每个等级的像元大小各不相同。必不可少的第一层格网等级的像元大小最小。第二层和第三层格网像元等级为可选等级,将其设置为 0 时不可用。如果启用第二层和第三层格网像元等级,则第二层格网像元的大小至少必须是第一层格网像元大小的三倍,而第三层网格像元的大小至少必须是第二层网格像元大小的三倍。

    在下例中,要素类具有两个格网等级。区域形状 101 位于等级 1 的格网像元 4 中。空间索引表上会添加一条记录,这是因为要素所占格网像元数小于四个(本例中仅占一个像元)。区域要素 102 的包络矩形位于等级 1 的像元 1 到 8 中。由于要素的包络矩形所占格网像元数大于四个,因此要素被将提升到等级 2,在等级 2 中,其包络矩形拟合于两个格网像元中。要素 102 在等级 2 中建立索引,而且空间索引表中会添加两条记录。

    形状 101 在格网等级 1 上建立索引;形状 102 在格网等级 2 上建立索引,该形状仅占两个格网像元。
    形状 101 在格网等级 1 上建立索引;形状 102 在格网等级 2 上建立索引,该形状仅占两个格网像元。

    插入、更新或删除要素会更新空间索引。每个要素的范围都会叠加到最低格网等级上,从而获得格网像元的数量。如果要素超过为 SERVER_CONFIG 表中的 MAXGRIDSPERFEAT 值设置的值,则在已定义更高等级的情况下,几何会被提升至下一较高等级。

    对于 Oracle 数据库,您可以通过设置用于创建要素类的配置关键字的 S_STORAGE 参数来指定创建空间索引的位置。有关设置配置参数的信息,请参阅 Oracle DBTUNE 配置参数和《ArcSDE 管理命令参考》中的 sdedbtune 命令。


    3.设置空间索引快速浏览

    空间索引用于在显示、编辑或查询数据时快速定位要素。因此,空间索引非常重要,尤其是在处理大量数据时。

    数据源不同,空间索引的工作方式也不同。DB2 中的个人地理数据库、文件地理数据库和企业级地理数据库,使用二进制几何存储机制的 Oracle 和 SQL Server 企业级地理数据库及使用 ST_Geometry 存储机制的 Oracle 企业级地理数据库均使用基于格网的空间索引。Oracle Spatial、Informix 和 PostgreSQL 不使用格网大小 - 它们使用 R 树索引。同样,使用 SQL Server 空间类型的要素类不使用 Esri 空间格网索引。

    ArcGIS 如何维护空间索引

    在文件、企业级、工作组和桌面地理数据库中完成某些操作后,ArcGIS 会自动重建空间索引以确保索引处于最优状态。下面介绍 ArcGIS 如何管理空间索引:

    • 使用“新建要素类”向导创建空要素类时,将会为(不包括 DB2 数据库中的)文件、工作组、桌面和所有企业级地理数据库创建空间索引。在编辑或使用“加载数据”命令时,将使用空间索引。在 DB2 的企业级地理数据库中,在将数据加载到空要素类后会创建空间索引。
    • 如果从个人地理数据库、shapefile 或 coverage 导入数据,或者将计算机辅助绘图 (CAD) 或智能数据压缩 (SDC) 数据导入文件、企业级、工作组或桌面地理数据库,则会为新的要素类自动计算空间索引。
    • 在使用 ArcCatalog 的“复制”和“粘贴”命令将要素类从个人地理数据库复制到文件、企业级、工作组或桌面地理数据库时,将会自动重新构建空间索引。如果从 Oracle Spatial、PostgreSQL 或 Informix 复制要素类,也会重新构建空间索引。如果将要素类从使用基于格网索引的文件或企业级地理数据库(Oracle 二进制和 ST_Geometry、SQL Server 二进制或 DB2)复制到其他使用基于格网的索引的地理数据库,则会将索引与源数据一同复制,而不会重新计算。
    • 在使用创建要素类的地理处理工具时,会检查新要素类中的要素,并自动计算出新的空间索引。
    • 对于没有空间索引的要素类,在保存编辑或“加载数据”命令时,将会在保存编辑或加载数据操作结束时计算空间索引。
    • 压缩文件地理数据库要素类使用的空间索引类型与未压缩要素类中使用的空间索引类型不同。在压缩文件地理数据库要素类时,系统会自动重新构建索引。此索引无法修改。解压缩要素类时,将自动重新建立与压缩前要素类所具有的相同的空间索引。

    何时更新空间索引

    因为 ArcGIS 会维护文件、企业级、工作组和桌面地理数据库中的空间索引,所以用户极少需要手动重新创建空间索引。仅在以下极少数情况下需要重新创建空间索引:

    • 在添加了大量与要素类中原有要素大小不同的要素后,需要手动重新计算空间索引。这只适用于在编辑会话中添加要素的情况。例如,您可能启动了一个编辑会话,并手动添加了大量线要素或使用“对象加载器”加载了这些要素。添加的许多要素与要素类中原有的要素相比可能很长或很短。为确保空间索引与新要素的配合达到最优,应当进行更新。

    个人地理数据库中的空间索引

    在个人地理数据库中创建要素类时,无论是使用“新建要素类”向导、地理处理工具还是任何其他方法,ArcGIS 都将计算空间索引,并且无法修改。空间索引将基于要素类坐标系的范围,并且始终是最优的。


    4.修改空间索引

    可以在企业级地理数据库或数据库中重新构建要素类的空间索引,这些数据库使用 ST_Geometry 存储类型(Oracle 中)或几何存储(SQL Server 中)。对于企业级地理数据库和数据库中的其他所有存储类型,以及对于文件地理数据库中的要素类,您可以删除和重新创建空间索引,但无法对其进行修改。对于个人地理数据库中的要素类,则不能修改或重新创建空间索引。

    可以通过查看要素类属性 对话框常规选项卡中的“几何属性”部分,确定企业级地理数据库内要素类所使用的几何存储类型。

    许可 许可:

    修改企业级地理数据库中的要素类的空间索引仅对 ArcGIS for Desktop Advanced 和 Standard 可用。

    请注意,为企业级地理数据库或数据库中的要素类构建新的空间索引是一项非常占用服务器资源的操作,因此在许多用户登录到服务器时,不应对大型要素类执行该操作。

    要修改或重新创建要素类的空间索引,请执行以下操作:

    步骤:
    1. 启动 ArcMap 并打开 Catalog 窗口,或启动 ArcCatalog。
    2. 在“目录”树中,连接到包含要修改空间索引的要素类的地理数据库。

      对于企业级地理数据库或数据库,必须以数据所有者身份进行连接才可修改索引。

    3. 右键单击要素类,然后单击属性
    4. 单击索引选项卡。
    5. 修改要素类空间索引的方式取决于要素类包含的空间数据类型。
      • 对于使用 SQL Server 中的 Geometry 存储的要素类,请单击重新计算,以便 ArcGIS 设置格网大小。
      • 对于使用 Oracle 中的 ST_Geometry 的要素类,请单击重新构建
      • 对于文件地理数据库中的要素类,PostgreSQL、DB2 或 Informix 中的要素类,或者使用二进制/SDO_Geometry 存储(Oracle 中)或 Geometry 存储(SQL Server 中)的要素类,可以单击删除来移除空间索引,然后单击创建来创建新的空间索引。重新创建的索引会反映当前数据。
      警告 警告:

      对于包含数百万条记录或更多记录的 Windows Azure SQL Database 中的要素类,请勿删除和重新创建其空间索引。如果 Windows Azure SQL Database 确定对包含数百万条记录的要素类创建空间索引会占用过多服务器资源,则会终止此操作。这会使您的要素类不具有空间索引。

    5.性能提示

    以下信息可帮助您提高和维护文件地理数据库的性能:

    • 创建新要素类时的默认分辨率是 0.1 毫米或按数据集的坐标系单位计算的等效值。x,y 分辨率的默认值几乎对所有情况都适用。如果数据没有这么精确,则创建要素类时可选择设置一个较大的 x,y 分辨率。以较大的 x,y 分辨率来存储坐标可降低存储要求并提高性能。这不仅适用于文件地理数据库,也适用于 ArcSDE 地理数据库。有关 x,y 分辨率的详细信息,请参阅要素类基础知识
    • 与其他任何数据源一样,只创建真正需要的属性索引,因为添加的每个索引都会稍微降低要素类或表的编辑速度。每次编辑某个创建了索引的属性时,ArcGIS 都必须更新此索引。如果需要经常编辑某个字段,尽可能避免为其创建索引。
    • 如果要在一个较大的数据集中添加、编辑或删除大量要素或记录,无论是通过编辑会话、地理处理工具还是 Catalog 目录树,在开始之前先删除空间索引以及任何受影响的属性索引,然后在完成更改后再重新添加这些索引,将会节省时间。

      每次添加、编辑或删除要素类或记录时,ArcGIS 都需要更新索引。如果只对较小的数据集进行更改或只对几条记录进行更改(如 100 万条记录中的 10 条),则 ArcGIS 在每次增量更改之后更新索引所耗费的时间可以忽略不计。但是,如果对大量记录进行更改(如 100 万条中的 300,000 条),为大量的增量更改更新索引所耗费的时间就要远远超过按开始前先删除索引,完成更改后再添加这些索引所消耗的时间。对于其他情况,决定是否要删除索引会涉及到取舍问题,并且可能不十分明显。同样,用 ArcObjects 编写加载程序或转换程序的开发人员每次要加载大量记录时,都应考虑使用只加载模式。只加载模式会暂停所有属性和空间索引的更新,直到要素被导入。导入所有要素之后,所有记录的索引(现有的以及新的)都会自动更新。可通过 IFeatureClassLoad 接口设置此模式。

    • 与个人地理数据库一样,如果频繁添加或删除数据,则应定期紧缩文件地数据库。而且,在执行了任何大规模更改后,也应对文件地理数据库执行一次紧缩操作。紧缩可重新整理磁盘上的数据存储,从而改善性能。有关详细信息,请参阅紧缩文件地理数据库和个人地理数据库
    • 与使用任何其他存储在文件系统中的文件类型时一样,请将计算机维持在经过良好维护和调整的状态下。如果使用的是 Windows,请偶尔运行一次磁盘碎片整理程序来维护整个文件系统的性能。磁盘碎片整理程序是 Windows 操作系统随附的工具;有关详细信息,请参阅操作系统的联机帮助。
    • 空间索引格网大小过小或过大会导致加载时间变长并降低空间搜索性能。ArcGIS 会在大多数操作结束时自动重新构建空间索引,以确保格网大小处于最优状态。需要您手动重新计算索引的情况极少。但是,在编辑会话中添加大量要素时,可能存在需要手动重新计算的情况。有关详细信息,请参阅设置空间索引


    展开全文
  • 常见的空间索引方法

    万次阅读 多人点赞 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树系列。

     

    展开全文
  • PostGIS教程十一:空间索引

    万次阅读 多人点赞 2019-01-11 14:39:28
    一、空间索引是怎样工作的? 二、纯索引查询 三、分析 四、清理(VACUUM) 五、相关函数 回想一下,空间索引是空间数据库的三个关键特性之一。空间索引使得使用空间数据库存储大型数据集成为可能。在没有空间...
  • 空间数据库之空间索引

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

    千次阅读 2017-11-30 09:06:49
    1、空间索引的创建 1)创建索引之前总是要为空间层插入元数据 2)如果之前创建的索引失败了,必须先删除才能创建 Drop index customers_sidx; 创建索引: Create index customers_sidx oncustomers(location) ...
  • postgis建立空间索引

    千次阅读 2019-11-27 11:23:56
    postgis建立空间索引 查询索引删除索引建立GIST空间索引 查询索引 select * from pg_indexes where tablename='tablename'; 删除索引 DROP INDEX index_name; 建立GIST空间索引 CREATE INDEX index_name ...
  • ArcSDE空间索引

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

    千次阅读 2017-09-08 10:45:38
    MySQL索引之空间索引(SPATIAL) mysql对GIS空间数据的支持,包括创建空...
  • oracle 创建空间索引

    千次阅读 2017-09-06 10:39:52
    如果数据是从别人的库中导入进来,先前如果建有空间索引,则需要删除之后,建立自己的空间索引(否则容易报错),如果完全是自己的数据,或者之前并没有建立空间索引那就可以直接建立了。 首先进行查询,判断数据...
  • hilbert曲线用于空间索引

    千次阅读 2017-07-07 18:56:43
    hilbert 空间索引
  • 空间索引--网格索引

    千次阅读 2018-04-22 20:38:39
    原文地址:http://www.cnblogs.com/LBSer/p/3403933.html深入浅出空间索引2 第一...本篇将对空间索引进行简单分类,然后介绍网格索引。(深入浅出空间索引1:http://www.cnblogs.com/LBSer/p/3392491.html)一、空...
  • geohash之2d 地理空间索引

    千次阅读 2018-06-07 18:37:27
    2d 地理空间索引 概述 2D地理空间索引可以将文档与二维空间中的位置(例如地图上的点)相关联。MongoDB将位置字段中的二维坐标解释为点,并且可以将这些点编入特殊索引类型以支持基于位置的查询。地理空间索引提供...
  • 在谈论空间索引之前,我们必须了解数据索引的概念:索引是为了提高数据集的检索效率。打个比喻,一本书的目录就是这本书的内容的“索引”,我们查看感兴趣的内容前,通过查看书的目录去快速查找对应的内容,而不是...
  • Oracle中索引及空间索引的总结整理

    千次阅读 2018-03-14 19:50:49
    索引是一种允许直接访问数据表中某一数据行的树型结构,为了提高查询效率而引入,是一个独立于表的对象,可以存放在与表不同的表空间中。索引记录中存有索引关键字和指向表中数据的指针(地址)。对索引进行的I/O...
  • 地理空间索引:GeoHash原理

    千次阅读 2019-01-01 23:16:17
    1. 基于空间位置的服务 基于位置的服务型电商席卷而来,搭乘网约车去到目的地、搜索附近的餐馆酒旅,无不让人们感觉到便捷。比如打开滴滴APP,我们看到附近的车辆如下 那么问题来了,滴滴是怎么快速的匹配出乘客...
  • 问题发现: ArcMap10.2编辑ArcSDE中数据,SaveEdits时速度比较慢 ... Tools-indexes-add spatial index工具可以为要素类添加空间索引,可在执行过程中发现无论空间索引输入多少,工具运行之后添加的
  • B-树类型的索引树是一种高度平衡的多路径检索树结构,在传统的数据库中应用非常广泛。...因此,需要对传统 B-树进行扩展,开拓创新,提出更多的基于 B-树的专用空间索引技术,如 R-树、R+-树、R*-树等。
  • C++常见空间索引效率对比

    千次阅读 2014-09-09 20:30:59
    由于打算写一个空间数据引擎,在空间索引和属性索引方面搜集了一些开源实现,本文用以对比C++ GIS开发中常见的空间索引实现的效率 测试环境 操作系统 Windows 7 Professional SP1 ...
  • 公司这边用了Oracle Spatial来存储GIS数据信息,今天在某表上创建空间索引时报了下面的错: 此处举例说明: 假如有表TEST,其中有一列SHAPE存储维度信息。 CREATE INDEX IDX_TEST_SHAPE ON TEST(SHAPE) INDEXTYPE...
  • 有关空间格网索引原理详见前面章节讲述的内容。这里我们根据SpatialHadoop中具体的实现,来详细讲解下。格网索引是一级索引,格网的个数取决于两个参数,一个是数据集的大小,另外一个就是格网的大小。那么在...
  • 原名引至:http://www.cnblogs.com/linhugh/archive/2012/07/24/2606439.html 之前在做shp数据导入Geodatabase中时,程序运行出现错误提示:“The spatial index grid size is invalid”。...
  • Oracle_spatial的空间索引

    千次阅读 2014-07-15 02:42:06
    空间索引 1、空间索引的创建 1)创建索引之前总是要为空间层插入元数据 2)如果之前创建的索引失败了,必须先删除才能创建 Drop index customers_sidx; 创建索引: Create index customers_sidx on ...
  • spatialite之空间索引

    千次阅读 2014-11-25 13:07:33
    它有一个比较重要的概念就是空间索引了。 假设我们建好的表是testTable,主键为testTableId,可以增加图形列 这个机遇RTree 的索引的核心其实是把每个图形的范围记录在了索引表中。 范围就是后面的4个数字。 如何...
  • GIS空间索引(1)--概述

    千次阅读 2013-09-12 15:32:08
    空间索引 (spatial index) 为便于空间目标的定位及各种空间数据操作,按要素或目标的位置和形状或空间对象之间的某种空间关系来组织和存储数据的结构。 索引 对一个数据集做“索引”,是为了提高对这个数据集检索...
  • GeoMesa源码学习:空间索引

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

    万次阅读 2015-11-26 19:02:27
    MongoDB专为平面坐标查询做了专门的索引,称为地理空间索引。 同样需要用ensureIndex创建,不过,参数是两个 "2d" db.map.ensureIndex({"gps":"2d"}) gps键的值必须是某种形式的一对值:一个包含两个元素的...
  • 空间索引格网大小无效

    千次阅读 2014-12-26 13:54:00
    不知道同事什么原因在数据编辑过程中造成空间索引格网大小无效。 ESRI官网帮助中解译了这一问题:http://resources.arcgis.com/zh-cn/help/main/10.1/index.html#//01m600000046000000 ,空间索引用于在处理文件地理...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 739,505
精华内容 295,802
关键字:

空间索引

友情链接: Sci-Hub.rar