R树优化：现代数据库索引设计原理

近几年来，在国内外的诸多行业中，空间数据信息在信息处理上的比重不断增加，并且在许多业务领域得到了广泛应用，尤其是密切关系到地理和空间在数据上分布情况的空间信息系统（GIS），如物流管理控制和网格计算等。

由此可见，相对于传统的数据库而言，在管理系统上对空间数据信息的管理往往不一定是有效的。因此，基于空间数据信息，在管理和处理上相应出现了空间数据库管理系统。目前，空间数据库管理系统已经成为具有一定发展前景的主流系统。它通常是基于中间件技术加以利用，从而实现对空间数据信息进行管理的。中间件技术是在转换层实现的，也就是居于GIS和空间数据库载体之间。中间件技术对很多不同的数据库平台和操作系统进行差异化屏蔽，从而对所需要的技术和空间数据进行专业化管理，由此实现了许多前台终端在功能和数据共享上的相互操作。中间件的杰出代表是空间数据库引擎。这一引擎是基于关系数据库开展管理工作的，其中的数据空间在数据分析和关系运算上提供相应的功能。

对于空间数据来说，良好的组织和管理是必不可少的。同时，空间数据库引擎与空间数据库索引技术一样，在开展空间数据管理工作时，其效率和机制是同等重要的。此外，空间数据库处理也是重要的一部分。

（一）经典的R树和R*树

1.R树

1984年，来自美国的Gutman教授对R树空间索引结构进行了首创。这一结构在数据结构上是高度平衡的。R树空间索引结构是对经典的B+树索引结构的进一步扩展和改进，也是对空间数据信息的一种有效处理方式。R树所具有的结点都含有一个索引码，这个索引码对应一个矩形区域。这一矩形区域所对应的结点中的子结点所具有的最小外包矩形嵌套了该区域，其中的最小外包矩形的全局坐标和边都与坐标轴平行。它在树状结构上的特征如下：

第一，如果根结点不是叶子结点，则它至少有两棵子树。

第二，除根之外的所有中间结点（乃至叶子结点）均至少有m个子结点，至多有M个子结点。

第三，所有的叶子结点都要出现在同一层（体现了R树的高度平衡）。

因为对于一个给定的结点，其在两个子结点的边框上出现重叠的情况是被允许的，所以对于一个有着较高效率的R树来说，在其构造的成败上由以下两个指标所决定：覆盖因子和交叠因子。对于覆盖因子，如果数值过大，就会导致R树在索引上有所降低；对于交叠因子，它基于R树在索引的路径上不是唯一的。覆盖因子对R树覆盖到的空白区域进行度量，也就是说，它是在静态空间对覆盖程度进行间接衡量的；而交叠因子则对有相同水平结构的索引码在其叠加程度上进行度量。在理想的情况下，R树在交叠因子和覆盖因子上的应力是最小的。有一种设想指出R树在交叠因子上的最小化这一问题，以实现对R树索引方法的改进。

2.R*树

R★树在树状结构上与R树是相同的，同时基于R★树所具有的索引方法可以对R★树进行算法上的构造。例如，构造算法、结点插入算法、结点删除算法和结点检索算法等，它们在基本算法上与索引方法是相同的。其主要区别就是实现R★树状结构上的交叠因子的最小化，同时也体现在以下方面：在R★树结点插入算法和构造算法上对插入路径和机制上的选择，以及对结点的有效分裂机制在其策略的强制性上进行多方面的考虑。

第一，对于R★树来说，在对机制的选择上进行路径的插入时，除了要适当考虑到其面积之外，还要考虑矩形在索引码上的重叠问题。我们可以对这一选择机制进行思想上的总结：由于插入路径的选择是从根结点开始的，这一结点的子结点所指向的就是中间结点，当对矩形进行插入后，其在重叠面积上的矩形索引项就是最小的。如果矩形的重叠面积有所增长，出现了矩形索引项相同的情况，此时就要对矩形在最小面积增长的矩形索引项上进行选择。如果矩形面积的增长所具有的矩形索引项有多个且同时是相同的，就要对矩形面积在其最小的矩形索引项上进行选择。对于当前的子结点，若其指向的是叶子结点，则要对其进行选择，同时在矩形中进行插入。对于面积来说，其中增长最小的就是矩形索引项。如果面积增长的叶子结点是多个且相同的，就要对其在矩形面积上最小的索引项进行选择。

第二，结点的有效分裂机制针对的就是多维空间矩形，是一种映射关系。对于每一维度，它在等待中根据索引码对M+1个矩形进行排序，这样在一定维度下的两组具有一定顺序的矩形索引码就有了针对性，然后对M+1项进行M-2m+2种的划分。它可以分为两组，每一组元素的个数介于m与M之间，在第一组的前m项或M-m+1项进行分类，而另一组是针对M-m+1或m项进行分类。然后，根据每一组在分类结构上的不同，对其最终的量化公式进行确定。该公式是基于对矩形索引码面积、边长和相应重叠度进行定义的，并对其有效权值进行计算，同时根据权值本身的大小来确定分裂方法的有效性。

在强制重新插入策略上，R★树是动态的。也就是说，比起空间数据集合，空间数据项的插入次序是不同的。这就说明R★树在构造上也是不同的，并且在效率和性能上对索引产生了影响。从构造算法上来说，R★树在相对小的范围内实现对动态重组机制的引入，以保证全局范围内的实现，同时还要预防R★树中间层上索引码重叠的情况。在结点的删除和插入算法上，R★树应采用强制重新插入的策略。

（二）R-树的索引结构与算法

1.R-树的结构

R-树是B-树在多维数据空间的扩展，由Guttman于1984年提出。R-树的结点结构可以描述如下。

叶子结点：（COUNT，LEVEL，＜O11，MBR1＞，＜O，MBR2＞，…，＜OIm，MBRm＞）。

中间结点：（COUNT，LEVEL，＜CP1，MBR1＞，＜CP2，MBR2＞，…，＜CPm，MBRm＞）。

其中，＜O11，MBR1＞是保存空间目标的数据项，O11保存的是该空间目标的特征信息，MBR1保存的是该空间目标的最小包围矩形；＜CP1，MBR1＞是保存空间目标的索引项，CP1保存的是指向下一级子树的指针，MBR1保存的是下一级子树的最小包围矩形，也就是最小索引空间。COUNT≤表示R-树结点中存储的索引项或数据项的个数，LEVEL＞0表示该结点在R-树中的层数。由于叶子结点存储的整数和中间结点存储的指针所占的存储空间是相同的，并且它们之间能够相互转换，所以R-树的叶子结点和中间结点在结构设计上也是相同的。(www.xing528.com)

设m（2≤m≤M/2）为R-树结点结构包含的索引项或数据项的最小数量（m一般取M/2。如果结点中保存的项数少于m，则称为“结点下溢”；如果结点中保存的项数多于M，则称为“结点上溢”），则R-树必须满足以下几个特性：①若根结点不是叶子结点，则至少有2棵子树；②除根之外的所有中间结点至少有m棵子树，至多有M棵子树；③每个叶子结点均包含m至M个数据项；④所有叶子结点都出现在同一层次上；⑤所有结点都需要同样的存储空间。

除此之外，R-树还包括以下几个特征：①数据矩形的重叠是可能出现的，叶子结点在索引空间上的重叠是被允许的；②目录矩形的重叠也是被允许的，也就是说，中间结点的索引空间是允许重叠的；③对于精确匹配查找，其查找路径一般有很多。因为R-树是完全动态的，所以它的查询操作、插入操作、删除操作可以相互交叉，不需要对R-树进行重新构建。

2.R-树的查找

为了在整个索引空间中找到所有的与检索区域有关联的空间目标，R-树的查找必须从根结点开始。

在对整个索引空间中与检索区域进行相交的子树进行递归遍历的过程中，当与叶子结点进行接触后，首先要做的就是对数据矩形和检索区域进行比较。如果数据矩形和检索区域有交集，就对这一数据项进行相关的几何运算。

基于R-树的查找算法可以发现，要想提高R-树的查找效率，以下几个条件是必不可少的：

（1）中间结点在目录矩形上所覆盖的“面积”应该够小，并且R1R4-R5本身应该更小一些。这样一来，就可以进行在分支决策上的更高层次查找，并且改进其查找性能。

（2）中间结点对索引空间上所产生的重叠也应该尽可能小，如此就能够减少对路径搜索数目。

（3）目录矩形在“周长”上应该更小。这是因为在“面积”一定的情况下，“周长”最小的集合图形是“方形”，其在目录矩形上也能进行相应改善。对于一层目录矩形来说，可以对上一层的目录矩形进行包围，从而减少目录矩形在其上的覆盖“面积”。

（4）相应提高空间利用率，减少树的结点数目，同时增加树的深度。

3.R-树的插入

要想在R-树中插入一个空间目标，就要查找其根结点。要想找出合适的根结点所对应的索引空间中的索引项，就需要满足如下条件：

（1）对索引项进行覆盖，从而实现索引空间在目标上的增加，并且索引空间在变化上是最小的。

（2）索引项在索引空间上的变化是相同的，对最小的索引空间要进行查找。

根据以上原则，可对索引项进行递归搜索，并对其中合适的叶子结点进行查找。在叶子结点中，如果其包括的数据项比M更小，则这一叶子结点在进行新的空间目标上的索引时信息会增加，同时对上一级结点的索引空间进行调整；如果叶子结点在数据项上的个数小于M，则这一叶子结点空间目标的增加是不能直接进行插入而实现的，所以需要对这一叶子结点进行分裂，也就是需要增加这一叶子结点。对于父结点来说，在增加一项索引项时，如果父结点中的索引项在增加后发生溢出，就需要对这一父结点进行分裂操作。R-树连锁反应的发生可能由其插入操作导致，所以其操作是相当复杂的。

对于结点分裂，Guttman基于时间复杂度提出了三种分裂算法，即指数级分裂算法、平方级分裂算法和线性级分裂算法。这三种分裂算法使得相对结点发生分裂时，其在矩形面积上是最小的。在指数级分裂算法中，可以找到全局最优解，其时间也是更多的；在平方级分裂算法和线性级分裂算法中，可以得到次优解。对于k维空间来说，分裂结点No表示结点N的第i项第j维的值，它们满足1≤i≤M+1，1≤j≤k。

4.R-树的删除

在R-树中对一个空间目标进行删除时，首先要对R-树进行遍历，也就是查找并保存这一空间目标汇总的叶子结点，同时删除这一空间目标在其所对应的数据项，并对上级结点在索引空间上进行调整。如果在数据项上对这一空间目标进行删除，就会导致叶子结点出现下溢的情况。也就是说，叶子结点在数据项上是小于m的。对于这一叶子结点层而言，要对剩余的数据项进行重新插入，同时要删除这一叶子结点，并对上级结点中的叶子结点所对应的索引项进行删除。如果上级结点对这一叶子结点的删除导致下溢情况的出现，就需要进行同样的操作。需要重视的是，在对数据项进行重新插入时，要对其中的正确层（也就是其中的R树所具有的层级）进行插入。

虽然R-树在删除和插入的操作上是比较复杂的，但是为了维持R-树的平衡，并提高其效率，这些操作是无法避免的。