B+树索引机制的研究及优化

Research and improvement of B + tree indexing mechanism

当数据庞杂时,B+树索引在查找效率和空间利用率方面还存在不足。针对该问题提出一种改进的B+树结构,首先通过调整叶子节点与非叶子节点的数量关系,以降低树的深度;然后优化原插入算法,在分裂节点前进行平衡处理(BP),以提高树的空间利用率。经实验,改进后的B+树与传统B+树相比,在查找效率和空间利用率上分别提高了10%和6%,证明对B+树的改进具有可行性。

B ＋ tree is short in search efficiency and space utilization when processing mass data. This paper proposed an im- proved structure of B ＋ tree. Firstly, the method reduced the depth of B ＋ tree by adjusting the number of leaf nodes and nonleaf nodes. Then, it increased the utilization of B ＋ tree by optimizing the original insertion algorithm, which taking balance process （BP） before splitting the non-leaf nodes. Through experiment, compared with the traditional B ＋ tree, searching efficiency and space utilization of the improved B ＋ tree got increased by an average of 10% and 6%. It shows that the improvement is feasible.