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

Database index optimization algorithm based on cluster B^+ tree

作　　者：胡廷波[1] 钟俊[1] 

机构地区：[1]四川大学电气信息学院,成都610065

出　　处：《计算机应用》2013年第9期2474-2476,2481,共4页journal of Computer Applications

基　　金：四川省科技支撑计划项目(2011GZ005;2012GZ0009)

摘　　要：在数据库中普遍采用的索引结构为适合随机查找的B+树结构,当关键字之间存在顺序关系时,该类索引方式效率较低。针对以上问题,提出了基于分簇的B+树——CB+树(CB+Tree)结构。该树在B+树的基础上充分考虑了记录集关键字之间的顺序关系,通过降低索引树的高度来提高关键字的索引效率。仿真结果显示,在记录数为100万的情况下,CB+树和B+树效率相当。当记录数达到500万时,CB+树插入用时6.7 s,比B+树插入用时7.6 s减少了8%;CB+树查询用时9.9 s,比B+树查询用时11.1 s减少了10%;CB+树删除用时10.1 s,比B+树删除用时11.2 s减少了10%。由此说明,在记录集关键字有序且记录数大于100万时,提出的CB+树是更为高效的索引结构,且其效率随记录数的增大提升更为明显。Currently, the most popular index structure used in database is B ＋ tree, which is easy to search randomly. But in some cases of which keywords are sequential, this structure is not efficient. In order to solve this problem, this paper proposed Cluster B ＋ tree （CB ＋ tree） on the basis of B ＋ tree. This tree considered the order between keywords to a large extent, and also reduced the tree height to improve the efficiency of search. Simulation shows that when the record number was one million, CB ＋ tree had the same efficiency as B ＋ tree. When the record number was five million, it took CB ＋ tree 6.7 s to insert, which was 8% less than B ＋ tree＇s 7.6 s, and it took CB ＋ tree 9.9 s to inquire, which was 10% less than B ＋ tree＇s 11.1 s. Otherwise, CB＋ tree also reduced the time of deleting by 10% compared with that of B＋ tree＇s, from 11.2 s to 10.1 s. According to the simulations, when the key words are in order and the record number is larger than one million, CB ＋ tree is a more efficient index structure, and its efficiency will promote obviously while the record number increases.

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

分 类 号：TP312[自动化与计算机技术—计算机软件与理论] TP301.6[自动化与计算机技术—计算机科学与技术]