基于改进B+树算法的数据索引机制研究

论文摘要

本文主要研究分析了B+树索引,针对B+树算法从搜索性能和空间利用率方面做了改进。改进B+树算法的核心思想是让非叶子结点可含有的最多关键字个数是叶子结点的N倍。其中在搜索性能方面,算法的改进体现在降低了树的深度,减少了访问磁盘的次数,从而降低了检索时间;在空间利用率方面,主要体现在删除关键字时,除合并操作外,还进行了节点的左右旋转,将其各结点平衡,使树的整体平衡性比较好,提升了结点的空间利用率。本文采用Visual C++对改进的算法进行了验证,从时间开销、空间利用率、树的深度等方面综合比较,其结果证明了改进B+树算法在搜索性能和空间利用率方面都有所改进。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 课题研究目的及意义
• 1.2 国内外研究现状
• 1.3 课题的主要研究内容
• 1.4 论文的工作安排
• 2 树形索引机制的研究
• 2.1 B树索引
• 2.2 B-树索引
• 2.2.1 B-树的基本概念
• 2.2.2 B-树的查找
• 2.2.3 B-树的插入
• 2.2.4 B-树的删除
• +树索引'>2.3 B⁺树索引
• +树的基本概念'>2.3.1 B⁺树的基本概念
• +树的查找'>2.3.2 B⁺树的查找
• +树的插入'>2.3.3 B⁺树的插入
• +树的删除'>2.3.4 B⁺树的删除
• *树索引'>2.4 B^*树索引
• 2.5 小结
• +树索引机制的改进与应用'>3 基于B⁺树索引机制的改进与应用
• +树索引机制的改进'>3.1 基于B⁺树索引机制的改进
• +树的定义'>3.1.1 对改进B⁺树的定义
• +树的查找'>3.1.2 改进B⁺树的查找
• +树的插入'>3.1.3 改进B⁺树的插入
• +树的删除'>3.1.4 改进B⁺树的删除
• +树索引机制的应用'>3.2 改进B⁺树索引机制的应用
• 3.3 小结
• 4 验证过程和结果
• 4.1 验证过程
• +树与B⁺树的比较'>4.1.1 改进B⁺树与B⁺树的比较
• 4.1.2 空间利用率的比较
• 4.1.3 时间开销的比较
• 4.2 验证结果
• 4.3 小结
• 5 结论和展望
• 5.1 结论
• 5.2 后续工作与未来展望
• 参考文献
• 致谢
• 攻读硕士学位期间公开发表的学术论文