基于分簇的B+树数据库索引优化算法

摘要：在数据库中普遍采用的索引结构为适合随机查找的B+树结构，当关键字之间存在顺序关系时，该类索引方式效率较低。针对以上问题，提出了基于分簇的B+树——CB+树（CB+ Tree）结构。该树在B+树的基础上充分考虑了记录集关键字之间的顺序关系，通过降低索引树的高度来提高关键字的索引效率。仿真结果显示，在记录数为100万的情况下，CB+树和B+树效率相当。当记录数达到500万时，CB+树插入用时6.7s，比B+树插入用时7.6s减少了8%；CB+树查询用时9.9s，比B+树查询用时11.1s减少了10%；CB+树删除用时10.1s，比B+树删除用时11.2s减少了10%。由此说明，在记录集关键字有序且记录数大于100万时，提出的CB+树是更为高效的索引结构，且其效率随记录数的增大提升更为明显。

关键词：数据库；索引；效率；B+树；CB+树

中图分类号：TP312；TP301.6

文献标志码：A

0引言

索引是对数据库表中一列或多列进行排序的一种结构，使用索引可快速访问数据库表中的特定信息。建立索引的目的是加快表中记录的查找或排序[1-2]。经典的索引机制主要分为三类[3-5]：一类是基于HASH函数对数据随机组织的索引机制，如可扩展HASH（EH）、线性HASH（LH）、带冲突链的HASH（CBH）等；另一类是基于查询树对数据有序组织的索引机制，如B树、B+树、T树、T*树等，其中T树是一种用于内存数据库的有序数据索引机制；最后一类是综合HASH表和查询树特点的混合索引机制hybridHT。

国内外研究数据库索引算法的学者很多。2002年文献[6]提出了分形预取B+树（Fractal Perfetchin B+ tree），利用一种自相似的“树中有树”的分形结构，用预取B+树代替磁盘B+树中的每一个节点，在优化Cache性能的同时也兼顾优化磁盘访问性能，并且查找、更新操作的性能都比原来的磁盘B+树有所提高，其不足之处在于没有考虑并况，而现实中使用的索引通常是带有并发读写的。2003年，文献[7]研究了CSB+树的结构后指出：令CSB+树的节点大小刚好等于Cache行的大小可以提高Cache的命中率，然而CSB+树的不足之处在于节点大小必须控制在一个缓存块左右，一般为64B或128B。2012年，文献[8]提出了Hash表与B+树相结合的高效目录索引结构，该结构能快速地处理大量文件，其缺点是该结构只针对文件系统，比如文件创建、查找和删除。同年，文献[9]提出的基于位图索引和B+树的数据存储方式极大地提高了BLAST程序运算速度，其缺点是太消耗空间，对于大小为1GB的序列数据库，该结构至少需要30GB的硬盘空间。2013年，文献[10]提出的针对内存数据库的CST树，利用主机的二级缓存来优化数据库索引。同年，文献[11]提出的pT树则是在CST树和分形预取B+树的基础上更加增大了树叶节点的容量来提高索引效率，这两种树结构的缺点是只适用于内存数据库。

以上提出的索引树结构，都未对记录集关键字有序的情况作出讨论。然而，现实中总是很多时候会存在关键字有序的记录集，在这种情况下如果仍然使用B+树，就会忽略掉“有序”这样的性质，从而造成搜索树较高，降低搜索效率。本文目的就是讨论在该情况下，对B+树进行怎样的改进才能充分利用“有序”这一特性来提高搜索效率。

4结语

综合以上分析，由于B+树考虑关键字的关系随机，所以在关键字有序的情况下，其索引效率不是最优。本文提出的CB+树正是对B+树在这种情况的一个补充，其利用关键字有序的特殊性，将多个关键字依序聚合成簇，多个簇依簇内最小关键字聚合成簇分区，B+树的叶子节点存放着该簇分区表，这样就降低了B+树的高度，且没有降低簇内的索引效率，从而提高了整棵树的访问性能。仿真表明，当关键字有序且记录集较大时，CB+树较B+树有更好的索引效率，且其效率随记录集的增大而增大。

由于本文的实验数据仅仅是对算法的仿真而得出的，还未将其应用到具体的数据库中，所以CB+树在数据库中的表现性能还有待于进一步检验。

参考文献：

[1]史嘉权.数据库系统概论[M].北京：清华大学出版社，2006：85-87.