计算机应用 ›› 2013, Vol. 33 ›› Issue (09): 2474-2476.DOI: 10.11772/j.issn.1001-9081.2013.09.2474

• 数据库技术 • 上一篇    下一篇

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

胡廷波,钟俊   

  1. 四川大学 电气信息学院,成都 610065
  • 收稿日期:2013-03-21 修回日期:2013-05-03 出版日期:2013-09-01 发布日期:2013-10-18
  • 通讯作者: 胡廷波
  • 作者简介:胡廷波(1987-),男,四川广元人,硕士研究生,主要研究方向:嵌入式Linux;
    钟俊(1972-),男,重庆人,副教授,博士,主要研究方向:信号与信息处理、嵌入式Linux、图像处理、扩频通信。
  • 基金资助:

    四川省科技支撑计划项目

Database index optimization algorithm based on cluster B+ tree

HU Tingbo,ZHONG Jun   

  1. School of Electrical Engineering and Information, Sichuan University, Chengdu Sichuan 610065, China
  • Received:2013-03-21 Revised:2013-05-03 Online:2013-10-18 Published:2013-09-01
  • Contact: HU Tingbo

摘要: 在数据库中普遍采用的索引结构为适合随机查找的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 树

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

中图分类号: