精华内容
下载资源
问答
  • 这是关于常用空间索引技术分析电子书,希望对各位有用
  • 1.MySQL在创建数据表时候创建索引 在MySQL中创建表时候,可以直接创建索引。基本语法格式如下: CREATE TABLE 表名(字段名 数据类型 [完整性约束条件], [UNIQUE | FULLTEXT | SPATIAL] INDEX | KEY ...

    转自:https://blog.csdn.net/tomorrow_fine/article/details/78337735

    1.MySQL在创建数据表的时候创建索引

    在MySQL中创建表的时候,可以直接创建索引。基本的语法格式如下:

    CREATE TABLE 表名(字段名 数据类型 [完整性约束条件],
                      [UNIQUE | FULLTEXT | SPATIAL] INDEX | KEY
                      [索引名](字段名1 [(长度)] [ASC | DESC])
    );
    

    UNIQUE: 可选。表示索引为唯一性索引。
    FULLTEXT; 可选。表示索引为全文索引。
    SPATIAL: 可选。表示索引为空间索引。
    INDEX和KEY: 用于指定字段为索引,两者选择其中之一就可以了,作用是一样的。
    索引名: 可选。给创建的索引取一个新名称。
    字段名1: 指定索引对应的字段的名称,该字段必须是前面定义好的字段。
    长度: 可选。指索引的长度,必须是字符串类型才可以使用。
    ASC: 可选。表示升序排列。
    DESC: 可选。表示降序排列。

    1.1 MySQL创建普通索引

    创建一个普通索引时,不需要加任何UNIQUE、FULLTEXT或者SPATIAL参数。

    实例:创建一个名为index1的数据表,在表内的id字段上建立一个普通索引。

    1. 创建普通索引的SQL代码如下:

    CREATE TABLE index1(id INT,
        name VARCHAR(20),
        sex BOOLEAN,
        INDEX(id)
    ); 
    

    查看MySQL创建普通索引的操作效果。如下图所示:
    在这里插入图片描述
    从上图中可以看出,运行结果显示普通索引创建成功。

    2. 使用SHOW CREATE TABLE语句查看表的结构。如下图所示:
    或者通过1步骤,可以看出,在id字段上已经建立了一个名为id的普通索引。语句:

    KEY `id` (`id`)
    

    圆括号内的id是字段名称,圆括号左侧外面的id是索引名称。

    3. 使用EXPLAIN语句查看索引是否被使用。SQL代码如下:

      EXPLAIN SELECT * FROM index1 WHERE id = 1;
    

    使用EXPLAIN语句查看索引是否被使用的操作效果。如下图所示:
    在这里插入图片描述

    上图中的结果显示,possible_keys和key的值都为id。说明id索引已经存在,并且查询时已经使用了索引。

    1.2 MySQL创建唯一性索引

    如果使用UNIQUE参数进行约束,则可以创建唯一性索引。

    实例:创建一个名为index2的数据表,在表内的id字段上建立一个唯一性索引,并且设置id字段以升序的形式排列。
    1. 创建一个唯一性索引的SQL代码如下:

    CREATE TABLE index2(
    id INT UNIQUE,
    NAME VARCHAR(20),
    UNIQUE INDEX index2_id(id ASC)
    );
    

    index2_id是为唯一性索引起的一个新名字。

    查看MySQL创建唯一性索引的操作效果。如下图所示:
    在这里插入图片描述
    从上图中可以看出,运行结果显示创建成功。

    2. 使用SHOW CREATE TABLE语句查看表的结构。SQL代码如下:

    SHOW CREATE TABLE index2 \G
    在DOS提示符窗口中查看使用SHOW CREATE TABLE语句查看表的结构的效果。也可以通过上面的1步骤看到,在id字段上建立了名为id和index2_id的两个唯一性索引。这样做,可以提高数据的查询速度。

    如果在创建index2表时,id字段没有进行唯一性结束。如下所示:

    CREATE TABLE index2(
    id INT,
    name VARCHAR(20),
    UNIQUE INDEX index2_id(id ASC)
    );
    

    则也可以在id字段上成功创建名为index2_id的唯一性索引。但是,这样可能达不到提高查询速度的目的。

    1.3 MySQL创建全文索引

    全文索引使用FULLTEXT参数,并且只能在CHAR、VARCHAR或TEXT类型的字段上创建。
    全文索引可以用于全文搜索。
    现在,MyISAM存储引擎和InnoDB存储引擎都支持全文索引。
    实例:创建一个名为index3的数据表,在表中的info字段上建立名为index3_info的全文索引。

    1. 创建全文索引的SQL代码如下:

    CREATE TABLE index3(id INT,
    info VARCHAR(20),
    FULLTEXT INDEX index3_info(info)
    )ENGINE=MyISAM;
    

    如果设置ENGINE=InnoDB,则可以在InnoDB存储引擎上创建全文索引。

    查看MySQL创建全文索引的操作效果。如下图所示:
    在这里插入图片描述

    从上图中可以看出,代码的执行结果显示创建成功。

    2. 使用SHOW CREATE TABLE语句查看index3数据表的结构。如下图所示:
    从上图中可以看出,在info字段上已经建立了一个名为index3_info的全文索引。
    注意
    我使用的是MySQL 5.6.19版本,已经可以在InnoDB存储引擎中创建全文索引了。

    全文索引非常适合于大型数据集,对于小的数据集,它的用处可能比较小。

    1.4 MySQL创建单列索引

    单列索引是在数据表的单个字段上创建的索引。一个表中可以创建多个单列索引。唯一性索引和普通索引等都为单列索引。

    实例:创建一个名为index4的数据表,在表中的subject字段上建立名为index4_st的单列索引。

    1. 创建单列索引的SQL代码如下:

    CREATE TABLE index4(
    id INT,
    subject VARCHAR(30),
    INDEX index4_st(subject(10))
    );
    

    查看MySQL创建单列索引的操作效果。如下图所示:
    在这里插入图片描述

    从上图中可以看出,代码执行的结果显示创建成功。

    2. 使用SHOW CREATE TABLE语句 或 manage index 查看index4数据表的结构。如下图所示:
    在这里插入图片描述

    从上图中可以看出,在subject字段上已经建立了一个名为index4_st的单列索引。

    注意:subject字段长度为30,而index4_st设置的索引长度只有10,这样做是为了提高查询速度。对于字符型的数据,可以不用查询全部信息,而只查询它前面的若干字符信息。

    1.5 MySQL创建多列索引

    创建多列索引是在表的多个字段上创建一个索引。

    实例:创建一个名为index5的数据表,在表中的name和sex字段上建立名为index5_ns的多列索引。

    1. 创建多列索引的SQL代码如下:

    CREATE TABLE index5(id INT,
    name VARCHAR(20),
    sex CHAR(4),

    INDEX index5_ns(name,sex)

    );
    在DOS提示符窗口中或可视化工具中查看MySQL创建多列索引的操作效果。如下图所示:
    在这里插入图片描述

    从上图中可以看出,代码的执行结果显示index5_ns索引创建成功。

    从上图中可以看出,name和sex字段上已经建立了一个名为index5_ns的多列索引。

    2. 多列索引中,只有查询条件中使用了这些字段中第一个字段时,索引才会被使用。

    先在index5数据表中添加一些数据记录,然后使用EXPLAIN语句可以查看索引的使用情况。如果只是使用name字段作为查询条件进行查询。如下图所示:
    在这里插入图片描述

    EXPLAIN SELECT id,NAME,sex FROM index5;
    

    在这里插入图片描述

    EXPLAIN SELECT id,NAME,sex FROM index5 WHERE id = 3;
    在这里插入图片描述

    在这里插入图片描述

    从上图中可以看出,possible_keys和key的值都是index5_ns。Extra(额外信息)显示正在使用索引。这说明使用name字段进行索引时,索引index5_ns已经被使用。

    4. 如果只使用sex字段作为查询条件进行查询。如下图所示:

    EXPLAIN SELECT id,NAME,sex FROM index5 WHERE sex = '女';
    

    在这里插入图片描述

    从上图中可以看出,possible_keys和key的值都是NULL。Extra(额外信息)显示正在使用where条件查询,而未使用索引。

    提示

    使用多列索引时一定要特别注意,只有使用了索引中的第一个字段时才会触发索引。如果没有使用索引中的第一个字段,那么这个多列索引就不会起作用。因此,在优化查询速度时,可以考虑优化多列索引。

    1.5 MySQL创建空间索引

    使用SPATIAL参数能够创建空间索引。创建空间索引时,表的存储引擎必须是MyISAM类型。而且,索引字段必须有非空约束。

    实例:创建一个名为index6的数据表,在表中的space字段上建立名为index6_sp的空间索引。

    1. 创建空间索引的SQL代码如下:

    CREATE TABLE index6
    (
    id INT,
    SPACE GEOMETRY NOT NULL,
    SPATIAL INDEX index6_sp(SPACE)
    ) ENGINE=MYISAM;
    

    在DOS提示符窗口中或可视化工具中查看MySQL创建空间索引的操作效果。如下图所示:
    在这里插入图片描述

    从上图可以看出,代码执行的结果显示空间索引创建成功。

    1. 使用SHOW CREATE TABLE语句可看index6数据表的结构。如下图所示:
      从上图中可以看出,在space字段上已经建立了一个名为index6_sp的空间索引。从上图中可以看出,在space字段上已经建立了一个名为index6_sp的空间索引。

    注意,space字段是非空的,而且数据类型是GEOMETRY类型。这个类型是空间数据类型。

    空间数据类型包括GEOMETRY、POINT、LINESTRING和POLYGON类型等。这些空间数据类型平时很少用到

    2 添加索引

    1.添加PRIMARY KEY(主键索引)
    mysql>ALTER TABLE table_name ADD PRIMARY KEY ( column )
    2.添加UNIQUE(唯一索引)
    mysql>ALTER TABLE table_name ADD UNIQUE (
    column
    )
    3.添加INDEX(普通索引)
    mysql>ALTER TABLE table_name ADD INDEX index_name ( column )
    4.添加FULLTEXT(全文索引)
    mysql>ALTER TABLE table_name ADD FULLTEXT ( column)
    5.添加多列索引
    mysql>ALTER TABLE table_name ADD INDEX index_name ( column1, column2, column3 )

    3 建立索引常用的规则

    转:https://www.cnblogs.com/JimLy-BUG/p/6812682.html
    建立索引常用的规则如下:
    1、表的主键、外键必须有索引;
    2、数据量超过300万的表应该有索引;
    3、经常与其他表进行连接的表,在连接字段上应该建立索引;
    4、经常出现在Where子句中的字段,非凡是大表的字段,应该建立索引;
    5、索引应该建在选择性高的字段上(枚举型字段不建索引);
    6、索引应该建在小字段上,对于大的文本字段甚至超长字段,不要建索引;
    7、复合索引的建立需要进行仔细分析;尽量考虑用单字段索引代替:
    A、正确选择复合索引中的主列字段,一般是选择性较好的字段;
    B、复合索引的几个字段是否经常同时以AND方式出现在Where子句中?单字段查询是否极少甚至没有?假如是,则可以建立复合索引;否则考虑单字段索引;
    C、假如复合索引中包含的字段经常单独出现在Where子句中,则分解为多个单字段索引;
    D、假如复合索引所包含的字段超过3个,那么仔细考虑其必要性,考虑减少复合的字段;
    E、假如既有单字段索引,又有这几个字段上的复合索引,一般可以删除复合索引;
    8、频繁进行数据操作的表,不要建立太多的索引;
    9、删除无用的索引,避免对执行计划造成负面影响;
    以上是一些普遍的建立索引时的判定依据。一言以蔽之,索引的建立必须慎重,对每个索引的必要性都应该经过仔细分析,要有建立的依据。因为太多的索引与不充分、不正确的索引对性能都毫无益处:在表上建立的每个索引都会增加存储开销,索引对于插入、删除、更新操作也会增加处理上的开销。另外,过多的复合索引,在有单字段索引的情况下,一般都是没有存在价值的;相反,还会降低数据增加删除时的性能,凡是对频繁更新的表来说,负面影响更大

    展开全文
  • 空间索引初探

    2012-03-20 17:20:58
     本文简单介绍了GIS分析中常用的空间索引,并进行简单实验分析,给出了简单实验结果说明。  本文主要介绍包含格网索引、四叉树、k-d Tree、R-Tree等常用空间索引。   参考 1. Libspatialindex ...
     
    

                                                                                      空间索引初探

    ---by wangsh 2012-03-20

     

           本文简单介绍了GIS分析中常用的空间索引,并进行简单实验分析,给出了简单实验结果说明。

           本文主要介绍包含格网索引、四叉树、k-d Tree、R-Tree等常用空间索引。

          

    参考

    1.     Libspatialindex http://libspatialindex.github.com/

    2.     JTS空间索引 http://www.blogjava.net/lanfanss/archive/2007/12/21/169295.html

    3.     GIS中创建空间索引的方法 http://www.cnblogs.com/shawy/archive/2008/12/31/1365707.html

    4.     Oracle Spatial中的空间索引 http://cryolite.iteye.com/blog/491453

    5.     msdn使用空间索引 http://msdn.microsoft.com/zh-cn/library/bb895265.aspx

    6.     空间索引概述 http://technet.microsoft.com/zh-cn/library/bb964712.aspx

    7.     esri添加空间索引 http://help.arcgis.com/zh-cn/arcgisdesktop/10.0/help/index.html#//001700000060000000

    8.     SaIL空间索引 http://www.r-tree.net/blog/?p=22

    9.     空间索引blog http://www.r-tree.net/blog/

    10.  Spatiallite 空间索引 http://www.haogongju.net/art/1330302

    11.  GIS空间索引 http://www.haogongju.net/art/509871

    12.  FME 空间索引 http://www.haogongju.net/art/325090

    13.  orbisGIS http://www.orbisgis.org/ http://trac.orbisgis.org/t/

    14.  grid index http://en.wikipedia.org/wiki/Grid_(spatial_index)

    15.  希尔伯特曲线 http://blog.csdn.net/firecoder/article/details/7178928

    16.  曲线 http://people.sc.fsu.edu/~jburkardt/presentations/sgmga_coefficient.pdf

    17.  Code  http://people.sc.fsu.edu/~jburkardt/cpp_src/cpp_src.html

    展开全文
  • 摘 要:介绍了常用的空间索引算法,对其性能进行了比较,认为这些算法用于需要动态更新空间索引结构的移动GIS系统中时具有较大的局限性。针对移动GIS系统中对空间索引的特殊要求,提出了动态四叉树空间索引算法,对...
  • GIS空间索引技术

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

    地理信息系统(Geography Information System,简称GIS)的主要任务之一是有效地检索空间数据及快速响应不同用户的在线查询
    地理空间索引技术和方法是GIS的关键技术。是快速高效查询、检索和显示地理空间数据的重要指标。

    常用的空间索引技术介绍和比较:
     网格空间索引四叉树空间索引R树系列空间索引最为常见。
     
     目前国内外主要的空间数据库也大都采用网格空间索引、四叉树 与 R树 这三类的空间索引结构。如著名的Oracle公司的数据库则同时采用 四叉树和R树两种索引结构。

    1。 空间索引技术的发展和分类
       以传统的索引技术观点来看,可以把空间索引技术大致分为 四大类:基于B树、基于Hashing、基于二叉树和基于空间填充区。
       
       就目前的空间索引研究成果而言,在建立索引时,按照划分区域是否与空间对象的分布特征有关的标准,空间索引分为两大类:
                     划分区域与空间对象分布特征无关的;       ---包括 网格索引、四叉树;
                     划分区域与空间对象的分布特征有关的索引方法;  ---包括 BSP树、R树及其变种树、Cell树、KD树等
      
      
      1.1基于固定网格划分的空间索引
            基于固定网格划分的空间索引技术 面向地图对象的空间位置和分布。应该属于 栅格索引,是一种高效、简洁、易于实现的一种空间索引。
            固定网格划分的空间索引技术 顾名思义就是将一副地图数据按照固定的网格划分,如将一幅地图分割成 M行、N列,可表示为M*N,
            以落入每个网格内的地图目标建立索引,这样只需检索原来区域的1/(M*N),以达到 快速检索的目的。
            如下图所示:
             

           问题的关键在于 如何建立检索,将落入每个网格的目标正确放入该网格,在检索过程中,通过鼠标 点选 准确的判断出目标所在网格。
           并运用相应算法精确的剔出所选的目标,以获得其空间数据和对应的属性数据。
       
       
      1.2 四叉树
         四叉树是基于空间划分组织索引结构的索引机制,与规则网格划分不同。
         它将已知范围的二维空间划成4个相等的子空间。如果需要,可以将每个或其中几个子空间 继续划分下去,这样就形成了一个基于四叉树的空间划分。
         如下图所示:
          

          四叉树索引通过将 数据空间逐层细分来组织数据,结构和操作比较简单,实现比较方便。
          其中 满四叉树空间索引,还可用 顺序存储的线性表 来表示。内存需求小。
          
          
          关键是 建立四叉树空间索引,要预先知道空间对象分布的范围。因而不能满足 空间数据的动态要求;此外,一旦索引建立后,树的层次即被
          固定,无法根据 数据空间对象数目的变化来调整树高,可调节性差。
          
          
      
      1.3 R-树
         R-树是空间索引结构中最重要的一种层次结构,其构建思想是以最小边界矩形(简称MBR)递归的对数据集空间按照“面积”规则进行划分。
         R-树中的非叶子节点代表一个划分的空间区域,即一个矩形空间区域;
         R-树中的叶子节点包含的矩形区域对应空间对象的MBR。
         
         构造矩形空间的原则是:
             1) 矩形之间尽可能少重叠;
             2) 矩形尽可能的包含更多的空间对象;
             3) 矩形可以嵌套,即 矩形中可以包括更小的矩形;
             
         R-树的平面划分与数据结构如图所示:
          

          关键是 进行空间检索时,首先判断哪些矩形区域与检索窗口相交,再进一步判断落在检索窗口内的矩形区域中由哪些被检索的对象。
          
         优点:
            R-树具有很强的灵活性与可调节性,建树过程中无需预知整个空间对象所在的空间范围,同时他具有较高的执行效率。
            被公认为是 较好的空间索引结构,已经得到广泛应用。
            
         缺点:
            但是,R-树也存在许多问题,可归纳为两方面:
                   。由于空间对象千姿百态,其索引空间经常重叠,且其重叠的程度随着数据量后空间维数的增加而剧增。
                     索引空间的重叠必然造成树的深度及存储空间的增加,从而导致遍历时间增加,查询效率下降。
                  
                   。在动态构建R-树时,还会产生大量“死空间”(不包含空间目标的索引空间),造成存储空间的浪费,产生无效的遍历。
                  
       
       
       1.4 BSP树           
          BSP树是一种二叉树,它将 地理空间逐级进行一分为二的划分,如图所示:
          

          BSP树能很好地与地理对象的空间分布情况相适应,但对一般处理情况而言,BSP树深度较大,对各种操作均有不利影响。                
             

    2。主要空间索引方法对比
         在众多空间索引中,不同的索引有不同的优势和不足及使用范围。在选取哪一种作为空间数据库的空间索引时,要根据实际情况和需要来确定。
         所以,目前很多GIS软件中采用 多种索引机制并存、取长补短的策略

    展开全文
  • 四叉树空间索引

    千次阅读 2014-02-24 16:39:14
    四叉树的结构比较简单,并且当空间数据对象分布比较均匀时,具有比较高的空间数据插入和查询效率,因此四叉树是GIS中常用的空间索引之一。常规四叉树的结构如图所示,地理空间对象都存储在叶子节点上,中间节点以及...

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

     

    四叉树示意图

     

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

     

    本节将介绍一种改进的四叉树索引结构。四叉树结构是自顶向下逐步划分的一种树状的层次结构。传统的四叉树索引存在着以下几个缺点:

    (1)空间实体只能存储在叶子节点中,中间节点以及根节点不能存储空间实体信息,随着空间对象的不断插入,最终会导致四叉树树的层次比较深,在进行空间数据窗口查询的时候效率会比较低下。

    (2)同一个地理实体在四叉树的分裂过程中极有可能存储在多个节点中,这样就导致了索引存储空间的浪费。

    (3)由于地理空间对象可能分布不均衡,这样会导致常规四叉树生成一棵极为不平衡的树,这样也会造成树结构的不平衡以及存储空间的浪费。

    相应的改进方法,将地理实体信息存储在完全包含它的最小矩形节点中,不存储在它的父节点中,每个地理实体只在树中存储一次,避免存储空间的浪费。首先生成满四叉树,避免在地理实体插入时需要重新分配内存,加快插入的速度,最后将空的节点所占内存空间释放掉。改进后的四叉树结构如下图所示。四叉树的深度一般取经验值4-7之间为最佳。

     

    图改进的四叉树结构

     

    为了维护空间索引与对存储在文件或数据库中的空间数据的一致性,作者设计了如下的数据结构支持四叉树的操作。

    (1)四分区域标识

    分别定义了一个平面区域的四个子区域索引号,右上为第一象限0,左上为第二象限1,左下为第三象限2,右下为第四象限3。

    typedef enum

    {

          UR = 0,// UR第一象限

          UL = 1, // UL为第二象限

          LL = 2, // LL为第三象限

          LR = 3  // LR为第四象限

    }QuadrantEnum;

    (2)空间对象数据结构

    空间对象数据结构是对地理空间对象的近似,在空间索引中,相当一部分都是采用MBR作为近似。

    /*空间对象MBR信息*/

    typedef struct SHPMBRInfo

    {

          int nID;       //空间对象ID号

          MapRect Box;    //空间对象MBR范围坐标

    }SHPMBRInfo;

    nID是空间对象的标识号,Box是空间对象的最小外包矩形(MBR)。

    (3)四叉树节点数据结构

    四叉树节点是四叉树结构的主要组成部分,主要用于存储空间对象的标识号和MBR,也是四叉树算法操作的主要部分。

    /*四叉树节点类型结构*/

    typedef struct QuadNode

    {

          MapRect            Box;                   //节点所代表的矩形区域

          int                nShpCount;        //节点所包含的所有空间对象个数

          SHPMBRInfo* pShapeObj;          //空间对象指针数组

          int         nChildCount;            //子节点个数

          QuadNode *children[4];             //指向节点的四个孩子

    }QuadNode;

    Box是代表四叉树对应区域的最小外包矩形,上一层的节点的最小外包矩形包含下一层最小外包矩形区域;nShpCount代表本节点包含的空间对象的个数;pShapeObj代表指向空间对象存储地址的首地址,同一个节点的空间对象在内存中连续存储;nChildCount代表节点拥有的子节点的数目;children是指向孩子节点指针的数组。

    上述理论部分都都讲的差不多了,下面就贴上我的C语言实现版本代码。

    头文件如下:

    1. #ifndef __QUADTREE_H_59CAE94A_E937_42AD_AA27_794E467715BB__  
    2. #define __QUADTREE_H_59CAE94A_E937_42AD_AA27_794E467715BB__  
    3.   
    4.   
    5.   
    6.   
    7. /* 一个矩形区域的象限划分:: 
    8.  
    9. UL(1)   |    UR(0) 
    10. ----------|----------- 
    11. LL(2)   |    LR(3) 
    12. 以下对该象限类型的枚举 
    13. */  
    14. typedef enum  
    15. {  
    16.     UR = 0,  
    17.     UL = 1,  
    18.     LL = 2,  
    19.     LR = 3  
    20. }QuadrantEnum;  
    21.   
    22. /*空间对象MBR信息*/  
    23. typedef struct SHPMBRInfo  
    24. {  
    25.     int nID;        //空间对象ID号  
    26.     MapRect Box;    //空间对象MBR范围坐标  
    27. }SHPMBRInfo;  
    28.   
    29. /* 四叉树节点类型结构 */  
    30. typedef struct QuadNode  
    31. {  
    32.     MapRect     Box;            //节点所代表的矩形区域  
    33.     int         nShpCount;      //节点所包含的所有空间对象个数  
    34.     SHPMBRInfo* pShapeObj;      //空间对象指针数组  
    35.     int     nChildCount;        //子节点个数  
    36.     QuadNode  *children[4];     //指向节点的四个孩子   
    37. }QuadNode;  
    38.   
    39. /* 四叉树类型结构 */  
    40. typedef struct quadtree_t  
    41. {  
    42.     QuadNode  *root;  
    43.     int         depth;           // 四叉树的深度                      
    44. }QuadTree;  
    45.   
    46.   
    47.     //初始化四叉树节点  
    48.     QuadNode *InitQuadNode();  
    49.   
    50.     //层次创建四叉树方法(满四叉树)  
    51.     void CreateQuadTree(int depth,GeoLayer *poLayer,QuadTree* pQuadTree);  
    52.   
    53.     //创建各个分支  
    54.     void CreateQuadBranch(int depth,MapRect &rect,QuadNode** node);  
    55.   
    56.     //构建四叉树空间索引  
    57.     void BuildQuadTree(GeoLayer*poLayer,QuadTree* pQuadTree);  
    58.   
    59.     //四叉树索引查询(矩形查询)  
    60.     void SearchQuadTree(QuadNode* node,MapRect &queryRect,vector<int>& ItemSearched);  
    61.   
    62.     //四叉树索引查询(矩形查询)并行查询  
    63.     void SearchQuadTreePara(vector<QuadNode*> resNodes,MapRect &queryRect,vector<int>& ItemSearched);  
    64.   
    65.     //四叉树的查询(点查询)  
    66.     void PtSearchQTree(QuadNode* node,double cx,double cy,vector<int>& ItemSearched);  
    67.   
    68.     //将指定的空间对象插入到四叉树中  
    69.     void Insert(long key,MapRect &itemRect,QuadNode* pNode);  
    70.   
    71.     //将指定的空间对象插入到四叉树中  
    72.     void InsertQuad(long key,MapRect &itemRect,QuadNode* pNode);  
    73.   
    74.     //将指定的空间对象插入到四叉树中  
    75.     void InsertQuad2(long key,MapRect &itemRect,QuadNode* pNode);  
    76.   
    77.     //判断一个节点是否是叶子节点  
    78.     bool IsQuadLeaf(QuadNode* node);  
    79.   
    80.     //删除多余的节点  
    81.     bool DelFalseNode(QuadNode* node);  
    82.   
    83.     //四叉树遍历(所有要素)  
    84.     void TraversalQuadTree(QuadNode* quadTree,vector<int>& resVec);  
    85.   
    86.     //四叉树遍历(所有节点)  
    87.     void TraversalQuadTree(QuadNode* quadTree,vector<QuadNode*>& arrNode);  
    88.   
    89.     //释放树的内存空间  
    90.     void ReleaseQuadTree(QuadNode** quadTree);  
    91.   
    92.     //计算四叉树所占的字节的大小  
    93.     long CalByteQuadTree(QuadNode* quadTree,long& nSize);  
    94.   
    95.   
    96. #endif  


    源文件如下:

    1. #include "QuadTree.h"  
    2.   
    3.   
    4. QuadNode *InitQuadNode()  
    5. {  
    6.     QuadNode *node = new QuadNode;  
    7.     node->Box.maxX = 0;  
    8.     node->Box.maxY = 0;  
    9.     node->Box.minX = 0;  
    10.     node->Box.minY = 0;  
    11.   
    12.     for (int i = 0; i < 4; i ++)  
    13.     {  
    14.         node->children[i] = NULL;  
    15.     }  
    16.     node->nChildCount = 0;  
    17.     node->nShpCount = 0;  
    18.     node->pShapeObj = NULL;  
    19.   
    20.     return node;  
    21. }  
    22.   
    23. void CreateQuadTree(int depth,GeoLayer *poLayer,QuadTree* pQuadTree)  
    24. {  
    25.     pQuadTree->depth = depth;  
    26.   
    27.     GeoEnvelope env;    //整个图层的MBR  
    28.     poLayer->GetExtent(&env);  
    29.       
    30.     MapRect rect;  
    31.     rect.minX = env.MinX;  
    32.     rect.minY = env.MinY;  
    33.     rect.maxX = env.MaxX;  
    34.     rect.maxY = env.MaxY;  
    35.       
    36.     //创建各个分支  
    37.     CreateQuadBranch(depth,rect,&(pQuadTree->root));  
    38.   
    39.     int nCount = poLayer->GetFeatureCount();  
    40.     GeoFeature **pFeatureClass = new GeoFeature*[nCount];  
    41.     for (int i = 0; i < poLayer->GetFeatureCount(); i ++)  
    42.     {  
    43.         pFeatureClass[i] = poLayer->GetFeature(i);   
    44.     }  
    45.   
    46.     //插入各个要素  
    47.     GeoEnvelope envObj; //空间对象的MBR  
    48.     //#pragma omp parallel for  
    49.     for (int i = 0; i < nCount; i ++)  
    50.     {  
    51.         pFeatureClass[i]->GetGeometry()->getEnvelope(&envObj);  
    52.         rect.minX = envObj.MinX;  
    53.         rect.minY = envObj.MinY;  
    54.         rect.maxX = envObj.MaxX;  
    55.         rect.maxY = envObj.MaxY;  
    56.         InsertQuad(i,rect,pQuadTree->root);  
    57.     }  
    58.   
    59.     //DelFalseNode(pQuadTree->root);  
    60. }  
    61.   
    62. void CreateQuadBranch(int depth,MapRect &rect,QuadNode** node)  
    63. {  
    64.     if (depth != 0)  
    65.     {  
    66.         *node = InitQuadNode(); //创建树根  
    67.         QuadNode *pNode = *node;  
    68.         pNode->Box = rect;  
    69.         pNode->nChildCount = 4;  
    70.   
    71.         MapRect boxs[4];  
    72.         pNode->Box.Split(boxs,boxs+1,boxs+2,boxs+3);  
    73.         for (int i = 0; i < 4; i ++)  
    74.         {  
    75.             //创建四个节点并插入相应的MBR  
    76.             pNode->children[i] = InitQuadNode();  
    77.             pNode->children[i]->Box = boxs[i];  
    78.   
    79.             CreateQuadBranch(depth-1,boxs[i],&(pNode->children[i]));  
    80.         }  
    81.     }  
    82. }  
    83.   
    84. void BuildQuadTree(GeoLayer *poLayer,QuadTree* pQuadTree)  
    85. {  
    86.     assert(poLayer);  
    87.     GeoEnvelope env;    //整个图层的MBR  
    88.     poLayer->GetExtent(&env);  
    89.     pQuadTree->root = InitQuadNode();  
    90.   
    91.     QuadNode* rootNode = pQuadTree->root;  
    92.   
    93.     rootNode->Box.minX = env.MinX;  
    94.     rootNode->Box.minY = env.MinY;  
    95.     rootNode->Box.maxX = env.MaxX;  
    96.     rootNode->Box.maxY = env.MaxY;  
    97.   
    98.     //设置树的深度(   根据等比数列的求和公式)  
    99.     //pQuadTree->depth = log(poLayer->GetFeatureCount()*3/8.0+1)/log(4.0);  
    100.     int nCount = poLayer->GetFeatureCount();  
    101.   
    102.     MapRect rect;  
    103.     GeoEnvelope envObj; //空间对象的MBR  
    104.     for (int i = 0; i < nCount; i ++)  
    105.     {  
    106.         poLayer->GetFeature(i)->GetGeometry()->getEnvelope(&envObj);  
    107.         rect.minX = envObj.MinX;  
    108.         rect.minY = envObj.MinY;  
    109.         rect.maxX = envObj.MaxX;  
    110.         rect.maxY = envObj.MaxY;  
    111.         InsertQuad2(i,rect,rootNode);  
    112.     }  
    113.   
    114.     DelFalseNode(pQuadTree->root);  
    115. }  
    116.   
    117. void SearchQuadTree(QuadNode* node,MapRect &queryRect,vector<int>& ItemSearched)  
    118. {  
    119.     assert(node);  
    120.   
    121.     //int coreNum = omp_get_num_procs();  
    122.     //vector<int> * pResArr = new vector<int>[coreNum];  
    123.   
    124.     if (NULL != node)  
    125.     {  
    126.         for (int i = 0; i < node->nShpCount; i ++)  
    127.         {  
    128.             if (queryRect.Contains(node->pShapeObj[i].Box)  
    129.                 || queryRect.Intersects(node->pShapeObj[i].Box))  
    130.             {  
    131.                 ItemSearched.push_back(node->pShapeObj[i].nID);  
    132.             }  
    133.         }  
    134.   
    135.         //并行搜索四个孩子节点  
    136.         /*#pragma omp parallel sections 
    137.         { 
    138.             #pragma omp section 
    139.             if ((node->children[0] != NULL) &&  
    140.                 (node->children[0]->Box.Contains(queryRect) 
    141.                 || node->children[0]->Box.Intersects(queryRect))) 
    142.             { 
    143.                 int tid = omp_get_thread_num(); 
    144.                 SearchQuadTree(node->children[0],queryRect,pResArr[tid]); 
    145.             } 
    146.  
    147.             #pragma omp section 
    148.             if ((node->children[1] != NULL) &&  
    149.                 (node->children[1]->Box.Contains(queryRect) 
    150.                 || node->children[1]->Box.Intersects(queryRect))) 
    151.             { 
    152.                 int tid = omp_get_thread_num(); 
    153.                 SearchQuadTree(node->children[1],queryRect,pResArr[tid]); 
    154.             } 
    155.  
    156.             #pragma omp section 
    157.             if ((node->children[2] != NULL) &&  
    158.                 (node->children[2]->Box.Contains(queryRect) 
    159.                 || node->children[2]->Box.Intersects(queryRect))) 
    160.             { 
    161.                 int tid = omp_get_thread_num(); 
    162.                 SearchQuadTree(node->children[2],queryRect,pResArr[tid]); 
    163.             } 
    164.  
    165.             #pragma omp section 
    166.             if ((node->children[3] != NULL) &&  
    167.                 (node->children[3]->Box.Contains(queryRect) 
    168.                 || node->children[3]->Box.Intersects(queryRect))) 
    169.             { 
    170.                 int tid = omp_get_thread_num(); 
    171.                 SearchQuadTree(node->children[3],queryRect,pResArr[tid]); 
    172.             } 
    173.         }*/  
    174.         for (int i = 0; i < 4; i ++)  
    175.         {  
    176.             if ((node->children[i] != NULL) &&   
    177.                 (node->children[i]->Box.Contains(queryRect)  
    178.                 || node->children[i]->Box.Intersects(queryRect)))  
    179.             {  
    180.                 SearchQuadTree(node->children[i],queryRect,ItemSearched);  
    181.                 //node = node->children[i];  //非递归  
    182.             }  
    183.         }  
    184.     }  
    185.   
    186.     /*for (int i = 0 ; i < coreNum; i ++) 
    187.     { 
    188.         ItemSearched.insert(ItemSearched.end(),pResArr[i].begin(),pResArr[i].end()); 
    189.     }*/  
    190.   
    191. }  
    192.   
    193. void SearchQuadTreePara(vector<QuadNode*> resNodes,MapRect &queryRect,vector<int>& ItemSearched)  
    194. {  
    195.     int coreNum = omp_get_num_procs();  
    196.     omp_set_num_threads(coreNum);  
    197.     vector<int>* searchArrs = new vector<int>[coreNum];  
    198.     for (int i = 0; i < coreNum; i ++)  
    199.     {  
    200.         searchArrs[i].clear();  
    201.     }  
    202.   
    203.     #pragma omp parallel for  
    204.     for (int i = 0; i < resNodes.size(); i ++)  
    205.     {  
    206.         int tid = omp_get_thread_num();  
    207.         for (int j = 0; j < resNodes[i]->nShpCount; j ++)  
    208.         {  
    209.             if (queryRect.Contains(resNodes[i]->pShapeObj[j].Box)  
    210.                 || queryRect.Intersects(resNodes[i]->pShapeObj[j].Box))  
    211.             {  
    212.                 searchArrs[tid].push_back(resNodes[i]->pShapeObj[j].nID);  
    213.             }  
    214.         }  
    215.     }  
    216.   
    217.     for (int i = 0; i < coreNum; i ++)  
    218.     {  
    219.         ItemSearched.insert(ItemSearched.end(),  
    220.             searchArrs[i].begin(),searchArrs[i].end());  
    221.     }  
    222.   
    223.     delete [] searchArrs;  
    224.     searchArrs = NULL;  
    225. }  
    226.   
    227. void PtSearchQTree(QuadNode* node,double cx,double cy,vector<int>& ItemSearched)  
    228. {  
    229.     assert(node);  
    230.     if (node->nShpCount >0)       //节点            
    231.     {  
    232.         for (int i = 0; i < node->nShpCount; i ++)  
    233.         {  
    234.             if (node->pShapeObj[i].Box.IsPointInRect(cx,cy))  
    235.             {  
    236.                 ItemSearched.push_back(node->pShapeObj[i].nID);  
    237.             }  
    238.         }  
    239.     }  
    240.   
    241.     else if (node->nChildCount >0)                //节点  
    242.     {  
    243.         for (int i = 0; i < 4; i ++)  
    244.         {  
    245.             if (node->children[i]->Box.IsPointInRect(cx,cy))  
    246.             {  
    247.                 PtSearchQTree(node->children[i],cx,cy,ItemSearched);  
    248.             }  
    249.         }  
    250.     }  
    251.   
    252.     //找出重复元素的位置  
    253.     sort(ItemSearched.begin(),ItemSearched.end());  //先排序,默认升序  
    254.     vector<int>::iterator unique_iter =   
    255.         unique(ItemSearched.begin(),ItemSearched.end());  
    256.     ItemSearched.erase(unique_iter,ItemSearched.end());  
    257. }  
    258.   
    259. void Insert(long key, MapRect &itemRect,QuadNode* pNode)  
    260. {  
    261.     QuadNode *node = pNode;     //保留根节点副本  
    262.     SHPMBRInfo pShpInfo;  
    263.       
    264.     //节点有孩子  
    265.     if (0 < node->nChildCount)  
    266.     {  
    267.         for (int i = 0; i < 4; i ++)  
    268.         {    
    269.             //如果包含或相交,则将节点插入到此节点  
    270.             if (node->children[i]->Box.Contains(itemRect)  
    271.                 || node->children[i]->Box.Intersects(itemRect))  
    272.             {  
    273.                 //node = node->children[i];  
    274.                 Insert(key,itemRect,node->children[i]);  
    275.             }  
    276.         }  
    277.     }  
    278.   
    279.     //如果当前节点存在一个子节点时  
    280.     else if (1 == node->nShpCount)  
    281.     {  
    282.         MapRect boxs[4];  
    283.         node->Box.Split(boxs,boxs+1,boxs+2,boxs+3);  
    284.   
    285.         //创建四个节点并插入相应的MBR  
    286.         node->children[UR] = InitQuadNode();  
    287.         node->children[UL] = InitQuadNode();  
    288.         node->children[LL] = InitQuadNode();  
    289.         node->children[LR] = InitQuadNode();  
    290.   
    291.         node->children[UR]->Box = boxs[0];  
    292.         node->children[UL]->Box = boxs[1];  
    293.         node->children[LL]->Box = boxs[2];  
    294.         node->children[LR]->Box = boxs[3];  
    295.         node->nChildCount = 4;  
    296.   
    297.         for (int i = 0; i < 4; i ++)  
    298.         {    
    299.             //将当前节点中的要素移动到相应的子节点中  
    300.             for (int j = 0; j < node->nShpCount; j ++)  
    301.             {  
    302.                 if (node->children[i]->Box.Contains(node->pShapeObj[j].Box)  
    303.                     || node->children[i]->Box.Intersects(node->pShapeObj[j].Box))  
    304.                 {  
    305.                     node->children[i]->nShpCount += 1;  
    306.                     node->children[i]->pShapeObj =   
    307.                         (SHPMBRInfo*)malloc(node->children[i]->nShpCount*sizeof(SHPMBRInfo));  
    308.                       
    309.                     memcpy(node->children[i]->pShapeObj,&(node->pShapeObj[j]),sizeof(SHPMBRInfo));  
    310.   
    311.                     free(node->pShapeObj);  
    312.                     node->pShapeObj = NULL;  
    313.                     node->nShpCount = 0;  
    314.                 }  
    315.             }  
    316.         }  
    317.   
    318.         for (int i = 0; i < 4; i ++)  
    319.         {    
    320.             //如果包含或相交,则将节点插入到此节点  
    321.             if (node->children[i]->Box.Contains(itemRect)  
    322.                 || node->children[i]->Box.Intersects(itemRect))  
    323.             {  
    324.                 if (node->children[i]->nShpCount == 0)     //如果之前没有节点  
    325.                 {  
    326.                     node->children[i]->nShpCount += 1;  
    327.                     node->pShapeObj =   
    328.                         (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->children[i]->nShpCount);  
    329.                 }  
    330.                 else if (node->children[i]->nShpCount > 0)  
    331.                 {  
    332.                     node->children[i]->nShpCount += 1;  
    333.                     node->children[i]->pShapeObj =   
    334.                         (SHPMBRInfo *)realloc(node->children[i]->pShapeObj,  
    335.                         sizeof(SHPMBRInfo)*node->children[i]->nShpCount);  
    336.                 }  
    337.   
    338.                 pShpInfo.Box = itemRect;  
    339.                 pShpInfo.nID = key;  
    340.                 memcpy(node->children[i]->pShapeObj,  
    341.                     &pShpInfo,sizeof(SHPMBRInfo));  
    342.             }  
    343.         }  
    344.     }  
    345.   
    346.     //当前节点没有空间对象  
    347.     else if (0 == node->nShpCount)  
    348.     {  
    349.         node->nShpCount += 1;  
    350.         node->pShapeObj =   
    351.             (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->nShpCount);  
    352.   
    353.         pShpInfo.Box = itemRect;  
    354.         pShpInfo.nID = key;  
    355.         memcpy(node->pShapeObj,&pShpInfo,sizeof(SHPMBRInfo));  
    356.     }  
    357. }  
    358.   
    359. void InsertQuad(long key,MapRect &itemRect,QuadNode* pNode)  
    360. {  
    361.     assert(pNode != NULL);  
    362.   
    363.     if (!IsQuadLeaf(pNode))    //非叶子节点  
    364.     {  
    365.         int nCorver = 0;        //跨越的子节点个数  
    366.         int iIndex = -1;        //被哪个子节点完全包含的索引号  
    367.         for (int i = 0; i < 4; i ++)  
    368.         {  
    369.             if (pNode->children[i]->Box.Contains(itemRect)  
    370.                 && pNode->Box.Contains(itemRect))  
    371.             {  
    372.                 nCorver += 1;  
    373.                 iIndex = i;  
    374.             }  
    375.         }  
    376.   
    377.         //如果被某一个子节点包含,则进入该子节点  
    378.         if (/*pNode->Box.Contains(itemRect) ||  
    379.             pNode->Box.Intersects(itemRect)*/1 <= nCorver)  
    380.         {   
    381.             InsertQuad(key,itemRect,pNode->children[iIndex]);  
    382.         }  
    383.   
    384.         //如果跨越了多个子节点,直接放在这个节点中  
    385.         else if (nCorver == 0)  
    386.         {  
    387.             if (pNode->nShpCount == 0)    //如果之前没有节点  
    388.             {  
    389.                 pNode->nShpCount += 1;  
    390.                 pNode->pShapeObj =   
    391.                     (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*pNode->nShpCount);  
    392.             }  
    393.             else  
    394.             {  
    395.                 pNode->nShpCount += 1;  
    396.                 pNode->pShapeObj =   
    397.                     (SHPMBRInfo *)realloc(pNode->pShapeObj,sizeof(SHPMBRInfo)*pNode->nShpCount);  
    398.             }  
    399.   
    400.             SHPMBRInfo pShpInfo;  
    401.             pShpInfo.Box = itemRect;  
    402.             pShpInfo.nID = key;  
    403.             memcpy(pNode->pShapeObj+pNode->nShpCount-1,&pShpInfo,sizeof(SHPMBRInfo));  
    404.         }  
    405.     }  
    406.   
    407.     //如果是叶子节点,直接放进去  
    408.     else if (IsQuadLeaf(pNode))  
    409.     {  
    410.         if (pNode->nShpCount == 0)    //如果之前没有节点  
    411.         {  
    412.             pNode->nShpCount += 1;  
    413.             pNode->pShapeObj =   
    414.                 (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*pNode->nShpCount);  
    415.         }  
    416.         else  
    417.         {  
    418.             pNode->nShpCount += 1;  
    419.             pNode->pShapeObj =   
    420.                 (SHPMBRInfo *)realloc(pNode->pShapeObj,sizeof(SHPMBRInfo)*pNode->nShpCount);  
    421.         }  
    422.   
    423.         SHPMBRInfo pShpInfo;  
    424.         pShpInfo.Box = itemRect;  
    425.         pShpInfo.nID = key;  
    426.         memcpy(pNode->pShapeObj+pNode->nShpCount-1,&pShpInfo,sizeof(SHPMBRInfo));  
    427.     }  
    428. }  
    429.   
    430. void InsertQuad2(long key,MapRect &itemRect,QuadNode* pNode)  
    431. {  
    432.     QuadNode *node = pNode;     //保留根节点副本  
    433.     SHPMBRInfo pShpInfo;  
    434.   
    435.     //节点有孩子  
    436.     if (0 < node->nChildCount)  
    437.     {  
    438.         for (int i = 0; i < 4; i ++)  
    439.         {    
    440.             //如果包含或相交,则将节点插入到此节点  
    441.             if (node->children[i]->Box.Contains(itemRect)  
    442.                 || node->children[i]->Box.Intersects(itemRect))  
    443.             {  
    444.                 //node = node->children[i];  
    445.                 Insert(key,itemRect,node->children[i]);  
    446.             }  
    447.         }  
    448.     }  
    449.   
    450.     //如果当前节点存在一个子节点时  
    451.     else if (0 == node->nChildCount)  
    452.     {  
    453.         MapRect boxs[4];  
    454.         node->Box.Split(boxs,boxs+1,boxs+2,boxs+3);  
    455.   
    456.         int cnt = -1;  
    457.         for (int i = 0; i < 4; i ++)  
    458.         {    
    459.             //如果包含或相交,则将节点插入到此节点  
    460.             if (boxs[i].Contains(itemRect))  
    461.             {  
    462.                 cnt = i;  
    463.             }  
    464.         }  
    465.   
    466.         //如果有一个矩形包含此对象,则创建四个孩子节点  
    467.         if (cnt > -1)  
    468.         {  
    469.             for (int i = 0; i < 4; i ++)  
    470.             {  
    471.                 //创建四个节点并插入相应的MBR  
    472.                 node->children[i] = InitQuadNode();  
    473.                 node->children[i]->Box = boxs[i];  
    474.             }  
    475.             node->nChildCount = 4;  
    476.             InsertQuad2(key,itemRect,node->children[cnt]);   //递归  
    477.         }  
    478.   
    479.         //如果都不包含,则直接将对象插入此节点  
    480.         if (cnt == -1)  
    481.         {  
    482.             if (node->nShpCount == 0)     //如果之前没有节点  
    483.             {  
    484.                 node->nShpCount += 1;  
    485.                 node->pShapeObj =   
    486.                     (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->nShpCount);  
    487.             }  
    488.             else if (node->nShpCount > 0)  
    489.             {  
    490.                 node->nShpCount += 1;  
    491.                 node->pShapeObj =   
    492.                     (SHPMBRInfo *)realloc(node->pShapeObj,  
    493.                     sizeof(SHPMBRInfo)*node->nShpCount);  
    494.             }  
    495.   
    496.             pShpInfo.Box = itemRect;  
    497.             pShpInfo.nID = key;  
    498.             memcpy(node->pShapeObj,  
    499.                 &pShpInfo,sizeof(SHPMBRInfo));  
    500.         }  
    501.     }  
    502.   
    503.     //当前节点没有空间对象  
    504.     /*else if (0 == node->nShpCount) 
    505.     { 
    506.         node->nShpCount += 1; 
    507.         node->pShapeObj =  
    508.             (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->nShpCount); 
    509.  
    510.         pShpInfo.Box = itemRect; 
    511.         pShpInfo.nID = key; 
    512.         memcpy(node->pShapeObj,&pShpInfo,sizeof(SHPMBRInfo)); 
    513.     }*/  
    514. }  
    515.   
    516. bool IsQuadLeaf(QuadNode* node)  
    517. {  
    518.     if (NULL == node)  
    519.     {  
    520.         return 1;  
    521.     }  
    522.     for (int i = 0; i < 4; i ++)  
    523.     {  
    524.         if (node->children[i] != NULL)  
    525.         {  
    526.             return 0;  
    527.         }  
    528.     }  
    529.   
    530.     return 1;  
    531. }  
    532.   
    533. bool DelFalseNode(QuadNode* node)  
    534. {  
    535.     //如果没有子节点且没有要素  
    536.     if (node->nChildCount ==0 && node->nShpCount == 0)  
    537.     {  
    538.         ReleaseQuadTree(&node);  
    539.     }  
    540.   
    541.     //如果有子节点  
    542.     else if (node->nChildCount > 0)  
    543.     {  
    544.         for (int i = 0; i < 4; i ++)  
    545.         {  
    546.             DelFalseNode(node->children[i]);  
    547.         }  
    548.     }  
    549.   
    550.     return 1;  
    551. }  
    552.   
    553. void TraversalQuadTree(QuadNode* quadTree,vector<int>& resVec)  
    554. {  
    555.     QuadNode *node = quadTree;  
    556.     int i = 0;   
    557.     if (NULL != node)  
    558.     {  
    559.         //将本节点中的空间对象存储数组中  
    560.         for (i = 0; i < node->nShpCount; i ++)  
    561.         {  
    562.             resVec.push_back((node->pShapeObj+i)->nID);  
    563.         }  
    564.   
    565.         //遍历孩子节点  
    566.         for (i = 0; i < node->nChildCount; i ++)  
    567.         {  
    568.             if (node->children[i] != NULL)  
    569.             {  
    570.                 TraversalQuadTree(node->children[i],resVec);  
    571.             }  
    572.         }  
    573.     }  
    574.   
    575. }  
    576.   
    577. void TraversalQuadTree(QuadNode* quadTree,vector<QuadNode*>& arrNode)  
    578. {  
    579.     deque<QuadNode*> nodeQueue;  
    580.     if (quadTree != NULL)  
    581.     {  
    582.         nodeQueue.push_back(quadTree);  
    583.         while (!nodeQueue.empty())  
    584.         {  
    585.             QuadNode* queueHead = nodeQueue.at(0);  //取队列头结点  
    586.             arrNode.push_back(queueHead);  
    587.             nodeQueue.pop_front();  
    588.             for (int i = 0; i < 4; i ++)  
    589.             {  
    590.                 if (queueHead->children[i] != NULL)  
    591.                 {  
    592.                     nodeQueue.push_back(queueHead->children[i]);  
    593.                 }  
    594.             }  
    595.         }  
    596.     }  
    597. }  
    598.   
    599. void ReleaseQuadTree(QuadNode** quadTree)  
    600. {  
    601.     int i = 0;  
    602.     QuadNode* node = *quadTree;  
    603.     if (NULL == node)  
    604.     {  
    605.         return;  
    606.     }  
    607.   
    608.     else  
    609.     {  
    610.         for (i = 0; i < 4; i ++)  
    611.         {   
    612.             ReleaseQuadTree(&node->children[i]);  
    613.         }  
    614.         free(node);  
    615.         node = NULL;  
    616.     }  
    617.   
    618.     node = NULL;  
    619. }  
    620.   
    621. long CalByteQuadTree(QuadNode* quadTree,long& nSize)  
    622. {  
    623.     if (quadTree != NULL)  
    624.     {  
    625.         nSize += sizeof(QuadNode)+quadTree->nChildCount*sizeof(SHPMBRInfo);  
    626.         for (int i = 0; i < 4; i ++)  
    627.         {  
    628.             if (quadTree->children[i] != NULL)  
    629.             {  
    630.                 nSize += CalByteQuadTree(quadTree->children[i],nSize);  
    631.             }  
    632.         }  
    633.     }  
    634.   
    635.     return 1;  
    636. }  
    展开全文
  •  今天查阅书籍时,偶然间发现“在对某个索引行执行删除操作时,只是为该行增加了一个删除标记,这个索引行并不会释放它存储空间,Insert产生的索引行也不能被插入到该位置。索引修改过程其实是将对应列...
  • 缺点:创建和维护索引的时间增加了,同时占用硬盘空间。 3.索引分类 1) 普通索引:是最基本的索引,它没有任何限制; 2) 唯一索引:与前面普通索引类似,不同就是:索引值必须唯一,但允许有空值。如果是...
  • 转自原文四叉树空间索引原理及其实现 ...四叉树的结构比较简单,并且当空间数据对象分布比较均匀时,具有比较高的空间数据插入和查询效率,因此四叉树是GIS中常用的空间索引之一。常规四叉树的结构...
  • 创建索引的标准语法:CREATE INDEX 索引名 ON 表名 (列名)TABLESPACE 表空间名;创建唯一索引:CREATE unique INDEX 索引名 ON 表名 (列名)TABLESPACE 表空间名;创建组合索引:CREATE INDEX 索引名 ON 表名 (列名1,列名2...
  • 常用索引简介

    2019-04-02 12:04:22
    引言 提到sql性能优化,索引是最常用的手段之一,我们经常会看到create index on 表名(列名...)之类的脚本,这就是最为常用的索引,它具有加快查询速度的作用,当数据库数据量大的时候,效用将会比较明显。...
  • 例如用Document替换BasicDBObject、通过Builders类构建Bson替代直接输入$命令等,本文整理了基于3.2版本的常用增删改查操作使用方法。为了避免冗长篇幅,分为增删改、查询、聚合、地理索引等几部分。随着移动...
  • 用于球体空间(2dsphere)和二维平面(2d)地理空间索引。 一、全文索引 MongoDB有一个特殊索引用在文档中搜索文本,之前博客都是用精确匹配来查询字符串,这些技术有一定限制。在搜索大块文本速度...
  • R*-树空间索引的改进

    2011-05-03 12:12:18
    为了克服R*树在时间与效率上不足 给出了一种新型存储结构,并给出了这种存储结构插入、溢出、分裂等空间索引常用操作算法
  • 例如用Document替换BasicDBObject、通过Builders类构建Bson替代直接输入$命令等,本文整理了基于3.2版本的常用增删改查操作使用方法。为了避免冗长篇幅,分为增删改、查询、聚合、地理索引等几部分。 随着移动...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,381
精华内容 552
关键字:

常用的空间索引