《现代数据库原理与索引设计优化》成果

目前，业界采用较多的是空间数据库索引技术。它起源于B-树的R-树索引。R-树有量化总变体，也就是R★-树索引和R★+树索引，以及基于对空间递归分解的层次型四叉树索引等。R★-树在索引技术上是比较成熟的，同时它在实际中的应用范围也比较广泛。对于传统的R系列索引技术，其空间在数据上是被允许进行索引码的相互覆盖的。这就使得它在空间的索引路径上表现出不唯一性，从而降低了空间数据项的查询效率。因此，将R★-树索引方法与四叉树索引的精髓进行结合，具有严格的空间组织性，通过适当改进R★-树的构造算法，可以出现一种新的混合式的索引技术，也就是R★Q-树索引。

（一）R*Q-树概述

许多空间数据项在进行插入时，采用的索引方法都是R★-树的索引方法。这就保证了它所创造的空间数据项在树状结构上的状态是平衡的。但是，如果它碰到的空间数据项在形状上有较大的差异，或者在相邻空间的数据项中，在距离上相距较远时，就往往会导致 R★-树的索引方法在性能上会有所降低。

因此，要想真正解决R★树索引真实存在的问题和缺陷，就需要一组空间数据在还没有进入分配状态，或在相互形状上和其邻接距离有着较大差异时，使R★-树索引结构在中间结点上的索引码所具有的覆盖度增加，并使其索引码在交叠因子上也相应增加，从而基于 R★-树索引技术中的结点在分裂次数上变得更多，大幅降低R★-树的索引效率。对于这一问题，可以利用基于R★树索引方法的R★Q-树索引进行算法改进。

原有的R★树索引方法通过与传统的四叉树索引思想进行融合，实现了R★Q-树索引算法的改进。四叉树索引思想也通过对区域循环进行分解。这种技术不仅有着清晰的机构，而且具有层次性。因此，相对空间目标而言，它是有着一定的聚集能力的。在引入动态指导机制后，在对空间数据项进行插入的同时，也对整体空间在其对象上进行四叉分解（其形式是嵌套式的），一直到能对这一层矩形索引码中的最小粒度进行包含为止。动态指导机制针对的就是这一最小粒度中的空间对象，要先对其进行判断，确定在空间数据项和该层中所插入的矩形索引码的位置是否表现为不同的四个象限。对于它们来说，如果它们所处的象限是不同的，就可以对它们进行空间数据项在预处理结点上的创建和插入；如果它们所处的象限是相同的，就需要针对这一层的矩形索引码进行进一步的四叉分解。这是一种嵌套的形式。在空间对象上，如果它所进行插入的空间数据项与其兄弟结点在位置上是不同的，就需要在结点上进行预处理；如果它所进行插入的空间数据项与其兄弟结点在位置上是相同的，就根据R★-树原本的插入算法对空间数据项进行插入。

为了配合在结点插入算法上的改进，四叉树的索引思想是对R★-树的结点分裂算法进行的相应使用，也被称为R★Q结点分裂算法。这就说明，结点是需要进行相应分裂的，而空间要首先进行嵌套式的四叉分解。对于结点产生分裂的父结点，其矩形索引码要在最小粒度上进行容纳。在空间对象上，若最小粒度进行分裂，其兄弟结点所占有的象限是不同的，分裂结点在索引码上必须予以保持和深化。这就使得该结点进行相应分裂时，相对这两个结点，其在新层上是同时存在的。

1.R*Q-树插入算法

相对于四叉树分解而言，这一算法是它在基本思想上的引入，这种设想包括“最小包含的标准四分格”。这就说明，如果索引在总体上的空间是X，那么对X所进行的划分是在四分格上进行的。能进行插入的空间的最小标准就是四分格，因此它也被称为空间数据项汇总的最小标准四分格，即MSQ。

R★Q-树结点插入算法需要在空间数据项进行插入之前使用，通过调用Needlndependenc算法，从而明确是否需要进行一个新结点的创建来对其进行存储，否则就调用R★-树的原始插入算法。在插入过程中，如果有结点分裂的情况出现，就需要调用R★Q-树结点分裂算法。

通过对Needlndependenc算法进行调用，可以实现对插入主算法中的预处理点是否需要进行创建的判断。如果针对插入空间项，其自身在层次上与其他子结点的索引目录进行矩形合并之后的MBR中进行存放，则是完全独立的，不属于任何象限集合。其所具有的附加条件应该得到满足，同时还要创建一个全新的独立预处理结点，以实现对插入的空间数据项的存放。

2.R*Q-树分裂算法

当结点所具有的子结点的个数超过其最大值时，插入的空间数据项是需要进行再次分裂的。

3.R*Q-树的应用与展望

本章所提出的R★Q-树索引改进算法实现了对经典的R★-树索引方法的改进，让原本的结点插入算法和结点分裂算法得到了更加合适的改变。这一成果可以在R★Q-树索引方法的构造算法中得到一定的应用。

通过对随机空间数据项的样本插入上的比较，空间数据项在数量上的要求是不少于20 000个。其索引算法是基于R★-树和R★Q-树的构造而言的，并对空间索引在索引码上所进行交叉的程度进行比较。这就说明，对于相同的序列，不同数量级的空间数据项的插入在这两种索引树上结构的交叠因子的交叠率是不同的。在进行一系列的实验统计后，插入数据项本身在数量级上是少于5 000的，对这两种树所进行构造的索引结构在其交叠率上是比较相似的。这说明了R★Q-树在算法改造上所带来的变化较小，但如果空间数据项的插入在数量增加的同时其数值是5 000～15 000，就说明它在改进效果上是比较明显的，改进后的交叠率比改进前的要更小。

通过对实验数据结果进行分析，可以得出以下结论：对于某一结构，如果其拓扑结构是相同的，则R★Q-树在索引结构上的结点数比R★-树要多；同时，对于交叠因子的交叠率，R★Q-树索引结构对交叠率进行缩减。根据实验结果发现，随着时间的推移，在空间数据项插入增多的同时，R★Q-树所具有的结构上的优势将变得更大。这就保证了空间数据在其索引码上的覆盖度和交叠度得到了缩减，同时空间数据项对目标索引在效率上得到了提升。(www.xing528.com)

总的来说，在R★-树索引结构的构造算法的基础上实现R★Q-树索引结构的构造算法的创造与利用，其中还有一定的四分树的精髓。在对空间数据项进行插入时，基于R★Q-树索引结构实现它在动态机制上的指导，也就是空间数据项在其预处理结点上的创立，是需要符合相关条件的，而不是无条件地进行插入或根据权值进行插入的。因此，R★Q-树索引结点在进行空间数据项的插入时会牺牲一定的空间利用率和数据存储空间。但是在空间插入数据项增加的同时，利用动态指导机制对提升原本的R★-树索引结构的索引效率是至关重要的。以上实现了基于R★-树索引结构在其构造算法上的改进，从而提出了基于R★Q-树索引结构的构造算法。但是在完成了R★Q-树索引结构的构造之后，它的维护和进一步调整是需要不断进行尝试的，主要目的是保证空间数据项在空间数据项查询算法和删除算法上工作的适应性。这需要后续的不断发展与探讨。

（二）R*Q-树算法的实现过程

相对于Java而言，R★Q-树算法是具有自身能运行的平台的。R★Q-树索引技术的设计主要是在Java在编程技术上实现的，其版本是JSDK5.0。

1.新型R*Q-树算法中主模块的设计与实现

由于中间结点与叶结点在结构上大致是一致的，所以我们可以用相同的类对其进行表示，对它们的区别进行不同的标记。

新型R★Q-树是通过Entry类完成对MBR的实现的。对于Entry类来说，它不仅是中间结点MNR的代表，同时还是空间数据项MBR的代表。Entry类不仅对空间数据矩形中的不同拓扑结构进行关系上的封装，同时还对空间数据矩形中的基本操作进行封装，如合并等。

2.新型R*Q-树算法中基本操作模块的设计与实现

新型R★Q-树索引方法的外部接口就是R★Q-树类，以此实现对其他应用程序的调用。R★Q-树在许多方面都能对Qnode中的功能进行调用，如插入、删除和查找等。

3.新型R*Q-树索引基本操作的部分核心代码

（1）新型R★Q-树查找方法的设计实现。在查询时，新型R★Q-树可在指定区域中的矩形区域进行查找。一开始时，是根结点对子区域中的所有区域进行查找的。如果这一子区域与被查找矩形在关系上是包含的，就可以在区域汇总的空间数据项进行返回；如果这一子区域与被查找矩形在关系上是相交的，就需对这一子区域进行继续查找，同时将 VR★-树、HR★-树也进行同步查找，直到最后的叶结点被找到为止。

（2）新型R★Q-树插入方法的设计实现。如果采取插入算法，新型R★Q-树的设计则是比较难以实现的。在进行函数调用时可以发现，空间数据项在垂直和水平方向上进行分割。这一分割在相交函数上所起的作用，决定了新型R★Q-树中适合进行空间数据结点插入的时间和位置。如果在结点上已经实现了分割极限，同时周围的兄弟结点都已做好了准备，结点就可以进行分裂。此时，新型R★Q-树的分裂所利用的就是惰性分裂技术，从而实现局部上的优化。

（3）新型R★Q-树删除方法的设计实现。对于新型R★Q-树的删除方法，首先要找到空间数据项所在的位置，其删除操作分为以下两种情况：

第一种，如果删除操作是在父结点中进行的话，就要先对父结点所具有的子区域中是否都在叶结点上进行判断，同时相对父结点和其子结点在空间数据项上的数量进行检查。对于空间数据项来说，如果其在数量上要比分割极限更少的话，就要把这一父结点进行删除，同时还要删除其叶结点，并且保证创建一个子结点。也就是说，原本在父结点上的子结点要在新的叶结点上的数据页面进行放置，否则也可以直接予以删除。

第二种，如果要在叶结点进行删除操作，就要保证这一叶结点在其父结点所具有的子区域中都是叶结点。如果它不是叶结点，就要将这一叶结点中所含有的MBR中的空间数据项进行删除；如果它是叶结点，其删除操作与第一种是相同的。

（4）新型R★Q-树分裂方法的设计实现。如果插入结点已经在分割极限上，或者在周围的兄弟结点都已布满的情况下，就需要进行相应的分裂操作。也就是说，需要使用聚类分裂技术实现这些结点在数据项上的重新组织。