Journal of Computer Applications ›› 2013, Vol. 33 ›› Issue (09): 2474-2476.DOI: 10.11772/j.issn.1001-9081.2013.09.2474
• Database technology • Previous Articles Next Articles
HU Tingbo,ZHONG Jun
Received:
Revised:
Online:
Published:
Contact:
胡廷波,钟俊
通讯作者:
作者简介:
基金资助:
四川省科技支撑计划项目
Abstract: 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.7s to insert, which was 8% less than B+ tree's 7.6s, and it took CB+ tree 9.9s to inquire, which was 10% less than B+ tree's 11.1s. Otherwise, CB+ tree also reduced the time of deleting by 10% compared with that of B+ tree's, from 11.2s to 10.1s. 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.
Key words: database, index, efficiency, B Tree, CB Tree
摘要: 在数据库中普遍采用的索引结构为适合随机查找的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 树
CLC Number:
TP312
TP301.6
HU Tingbo ZHONG Jun. Database index optimization algorithm based on cluster B+ tree[J]. Journal of Computer Applications, 2013, 33(09): 2474-2476.
胡廷波 钟俊. 基于分簇的B+树数据库索引优化算法[J]. 计算机应用, 2013, 33(09): 2474-2476.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2013.09.2474
https://www.joca.cn/EN/Y2013/V33/I09/2474