【作者】 吕俊燕；

【导师】 徐世国；

【作者基本信息】 辽宁工程技术大学 ， 计算机应用技术， 2008， 硕士

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

【Abstract】 The article mainly analyzes the index of B~+ tree and improves search performance and space utilization of B~+ tree algorithm. The central idea of improved B~+ tree algorithm is to allow the number of keys in non-leaf node is N times of leaf node. In search performance, the improvement of the algorithm reflects that it reduces the depth of the tree and the number of disk access, so that it reduces the search time; in the utilization of space, it mainly represents in the deletion of keywords. With the exception of the combined operation, but also the nodes are rotated around and balances its nodes so that the tree’s overall balance is better and enhances the nodes’ space utilization. The article uses Visual C++ to validate the improved algorithm from spending time, space utilization, and the depth of the tree and so on to compare synthetically. The results prove that the improved B~+ tree algorithm improves search performance and space utilization.更多还原