基于树的索引结构介绍

转眼又七月份了。6月份后来就变成考试月了。因为图论要求写阅读报告，某天看数据库的空间索引时，又正好看到关于基于树的一些索引技术，于是产生了以此为主题写份阅读报告的想法。今天算是完成了。总共介绍了5种树，二分查找树、AVL树、2-3树、B树及其变种B+树。B+树是现在运用最多的基于磁盘的索引方法。我打算等考完试再把这些树实现一下。以下是我的阅读报告，主要参考Clifford A. Shaffer的《数据结构与算法分析》。

 

基于树的索引结构

很多大型的计算机应用都需要处理大量的数据，这些数据通常不能一次性装入内存。但是访问存储在主存中的数据要比访问存储在磁盘或其他存储设备中的数据快得多, 所以对文件结构用于组织存储在磁盘中的大量记录时, 如何支持高效率的插入、删除和检索操作是非常重要的。一般来说, 有两种方法可以提高对磁盘中数据的操作: 一种是适当安排信息位置, 如果需要访问辅助存储器中的数据, 尽可能少的访问次数得到数据, 而且最好第一次访问就能得到; 另一种减少磁盘访问次数的方法是合理组织信息, 使每次磁盘访问都能得到更多的数据, 从而减少将来的访问需要。索引因此可以定义为将关键词值与该值对应的记录的磁盘位置联系起来的过程。索引的基本构件是索引项。一个索引项中有关键词值和指针，通过指针就可以找到含有此关键词值的记录，即一个索引项为：（关键词值，指针），多个索引项就构成了一个索引（表）。

索引本身也是一个文件，当索引很大时，也可以将其分块，建立高一层的索引，如此继续下去，直到最高级索引不超过一个块时为止，这样就得到了一个多级索引结构。索引通常置于磁盘或内存，内存中一般只存放最高级索引。一旦对一个大型数据文件建立了索引而形成了索引文件，则不论是对随机查找，还是对顺序查找都是方便的。

如何组织索引文件是索引技术中的主要问题，高效的组织方式必须便于数据的查找、更新和删除。线性索引将关键值进行排序，索引的时候通过如二分法等查找方法找到数据项，这种方法查找效率高，但是一旦插入或删除某个值，整个索引表都可能发生变化，因此这种方法只适用静态的数据库。而大多数数据库应用存在如下特性：

1.       存在大量的更新

2.       查找时可能使用一个至多个key值

3.       有范围的key值也可能用于查找。

树是数据结构中重要的非线性结构，由于其良好的动态性质得以在算法中大量应用。从存储上看，树的节点可以离散的存储，不必像数组那样必须有固定的大小，而是可以动态扩张；从操作上看，对树节点的插入/删除、查找、取后继等操作都具有良好的性能特性。因此树的数据结构是数据库索引的理想选择。

1.      二分查找树（BST）

二分查找树或者是一棵空树，或者是具有以下性质的二叉树：

（1）       若左子树不为空，则左子树上所有结点的值都小于它的根结点的值

（2）       若右子树不为空，则右子树上所有结点的值都大于或等于它的根结点的值

（3）       左子树跟右子树也分别为一棵二分查找树

 

查找特点键值时，从根节点出发，如果根节点与查找值相等，查找成功；否则，如果查找值小于根节点，则递归地查找左子树；如果查找值大于或等于根节点，则递归地查找右子树。若子树为空，查找不成功。查找算法的复杂度为logn。

在树中插入新节点时，首先执行查找算法，找出被插节点的父节点，判断被插节点是其父亲节点的左孩子还是右孩子，将被插节点作为叶子节点插入。被插节点都是叶子节点。

执行特定值的删除操作时，首先执行查找算法，找到该节点，如果节点是叶子节点，删除该节点并不影响树的结构，因此可以直接删除该节点。如果节点只有一棵子树（左子树或右子树），被删除节点的父节点成为该子树的父节点，并不影响整棵树的结构与性质。如果节点有两棵子树，要将该节点删除而不影响树的结构，有一个比较好的方法，就是在树里找到一个可以替换该节点的叶子节点（因为我们知道删除叶子节点并不影响树的结构），而为了保证替换后的树的性质不变，叶子节点必须是大于该节点的最小节点（右子树的最左节点），或小于该节点的最大节点（左子树的最右节点）（这样才能保证两棵子树，一边均小于该节点，一边均大于该节点）。如果树节点没有重复值，选择哪个值并没有什么区别，如果树节点是存在重复值的，那么我们必须选择来自右子树的大于被删除节点的最小值，因为右子树存放的是大于等于根节点的值，如果我们选择了左子树的最右节点，可能破坏树的性质。

二分查找树很容易引起树不平衡的问题，即一边子树比另外一边长很多，如果出现不平衡，则在检索时平均查找次数可能变大，使得查找效率大为降低，最极端的状况就是变成线性检索。即使通过插入控制使二分查找树相对平衡，如果树很庞大，也就是说，部分树节点在内存中，而部分树节点在磁盘上，如果节点很深，查找这个节点将经历多次读取磁盘的操作，这在很大程度上影响了检索的效率。因此，二分查找树更适于内查找，即所要查找的资料均放在内存中。

2.      AVL树

要使BST能够在基于磁盘的索引中达到高效可用，必须解决两个问题：一是使树平衡；二是合理地安排节点在块中的组织方式，使得从根节点到叶节点所经历的磁盘块数尽量地少。AVL树正是为使BST平衡而提出来的。

AVL树可以看成是在二分查找树的基础上添加以下属性：对于所有节点，其左子树和右子树的高度最大为1。只要树的节点满足这个性质，对于存储了n个记录的AVL树，其高度最大为O(logn)，这样，对一个值进行查找，路径最长为O(logn)。

AVL树的查找算法与BST自然是一样的，所以复杂度也为O(logn)。

为了维持AVL本身所特有的特性，AVL在插入与删除的操作上有所修改。首先考虑插入。在插入前，树本身符合AVL的性质（即左右子树高度最多只相关1），插入值后，左右子树的高度差最多为2，对于最底下的不平衡子节点S，存在四种可能的情况：

1.       额外的节点是S的左孩子的左孩子

2.       额外的节点是S的左孩子的右孩子

3.       额外的节点是S的右孩子的左孩子

4.       额外的节点是S的右孩子的右孩子

可以看到，1跟4是对称的，正如2跟3也是对称的一样。对于情况1跟4， 一个简单的旋转即可保持BST的性质。而对于情况2跟4， 则需要两次旋转，分别如下图所示：

 

 

 

至于删除，也是在BST的删除结果的基础上，考虑不平衡节点的旋转。因此，AVL的插入、删除操作跟BST的复杂度一样，均为O(logn)。它通过旋转规则，使树达到平衡，从而使树的高度降低，提高检索的效率。然而与BST一样的是，它更多的适用于内查找。对于基于磁盘的查找，同样没有比较好的组织方式。

3.      2-3树

2-3树不是一种二叉树，但他的形状满足以下性质：

（1）       一个节点包含一个或两个键值

（2）       每个内部节点有两个子节点（如果它有一个键值）或三个子节点（如果它有两个键值）

（3）       所有叶节点都在树结构的同一层，因此树的高度总是平衡的。

对于每个结点, 左子树中所有后继结点的值都小于第一个键的值, 而其中间子树中所有结点的值都大于或等于第一个键的值。如果结点有右子树的话( 相应地, 结点存储两个键值) , 那么其中间子树中所有后继结点的值都小于第二个键的值, 而其右子树中所有后继结点的值都大于或等于第二个键的值。同时，同一层的键值从左到右增大。

2-3树的查找方法与二分查找树相似，从根节点出发，如果在根节点找到查找值则查找成功返回，否则根据节点键的规则递归地查找下去，直到找到或返回失败。

在2-3树中插入新值时并不为其开辟一个新的叶子节点来存储，也就是说，2-3树不是向下生长的。插入算法首先找到一个合适的叶子节点来存放该值，使树的性质不被破坏。如果该叶子节点只包含一个值（每个节点都最多有两个值），则简单将该值放入叶子节点即可。如果叶子结点本身已经包含两个值了，则需要为前加入的叶子开辟新的空间。设节点L为插入节点，但是已经满了，也就是，这个节点因为包含了三个值，所以必须进行分裂，设新分裂出来的节点为L’，则L将存储这三个值中最小的那个值，而L’则存储这三个值中最大的那个。处于中间的值将得到提升，作为插入值晋升到父节点去。如果父节点只包含一个键值，该值直接放入节点即可，否则，同样的“分裂-晋升”过程将在该父节点进行，一直递归到根节点为止。

从2-3树删除一个节点，有三种可能情况需要考虑：最简单的情况是，如果删除的值存储在有两个键值的节点上，直接删除该值并不影响树的性质与结构。如果被删除的值所在的节点只有它一个键值，被删除后该节点将为空，因此通过向兄弟节点借一个记录，并修改父节点来解决。如果兄弟节点不够借，则需要合并相邻节点，并影响双亲，可能导致树的高度下降。如果被删除的值是树的内部节点，则将被删除记录用右边子树中的最小键值代替，然后再根据第一、二种情况将该值删除。

2-3树以比较小的代价维持了树的平衡，使树在相同记录的情况下尽量矮，从而提高了检索的速度。它同时也是后面的B-树使B+树的模型。

4.      B-树

B树，或者B树的变种已经成为需要进行插入、删除、查找操作的应用的标准的文件组织形式，它解决了基于磁盘的查找树必须解决的主要问题，包括：

1.       B树是一种平衡树，所有的叶子节点都在同一层上

2.       更新与查找操作只需动用几个磁盘块，所以性能比较好

3.       B树把相关的键值放在同一个磁盘块上，很好地利用了近邻效果

4.       B树保证所有的节点都有一个最低的饱合度，这样做的好处是提高了空间的效率同时又降低了获取磁盘的次数。

一棵阶数为m的B树必须满足以下的性质：

1.       根节点或者是叶节点，或者至少有两个孩子

2.       所有的内节点，除了根节点外，都必须有m/2到m个孩子

3.       所有的叶子节点都在同一层上，保证了树的平衡性

事实上，B树只是2-3树的一种泛化模式，2-3树是一种3阶的B树。一般的，一个B树节点为一个磁盘块的大小。查找、删除和插入操作跟2-3树也是一样的。

5.      B+树

从理论上说，B 树可以广泛用于实现基于磁盘的大型系统, 但是却从来没有实现过。最普遍使用的是B 树的一个变体, 称为B+ 树。可以这样定义一棵B+ 树:

（1）       树中每个非叶子节点最多有m棵子树；

（2）       根结点至少有两棵子树，除根外，所有的非叶节点至少有m/2棵子树，有n棵子树的非叶节点有n-1个键值

（3）       所有的叶子节点处于同一层上，包含了全部键值及指向相应数据对象存放地址的指针，且叶节点本身按键值从小到大顺序连接

（4）       所有的非叶节点可以看作索引部分，节点中键值与指向子树的指针构成了对树的索引项。

B+树与B树的最显著的区别在于: B+树只在叶结点存储记录, 内部结点存储关键码值，但是这些关键码值只是用于引导索引检索位符，这意味着内部结点与叶结点在结构上有着显著的区别。内部节点存储关键码引导索引，每个关键码与一个指向儿子节点的指针相关联, 而叶结点存储实际记录。m阶B+树中的叶结点可能存储大于或者小于m个记录, B+树的叶节点通常链接起来以便于检索，这样可以看出B+树是B树的一种变形，它把叶子结点和其它结点区别开来，并且建立链路，可见其效率要优于2- 3 树和B 树。