Abstract: Overflow page is commonly used to deal with the duplicate keys of a B+ tree index, although it is easy to implement, it introduces great space waste. This paper adopts an alternative approach to make the B+ tree explicitly support the duplicate keys by revising the index structure, and provides the basic algorithms to implement the idea. Experiment indicates that the revised B+ tree can significantly reduce the size of the index file, which broadens the application area of B+ tree.

Key words: B+ tree, duplicate keys, overflow page

摘要： 当前B+树索引结构常采用“溢出页”处理重复出现的键值，易于实现，但存在严重的空间浪费。该文通过改进索引结构的定义，使B+树能够显式支持重复键值，并给出相应算法。实验证明，采用该方法的B+树能有效减少索引文件的大小，使B+树满足更多数据库索引的需求。

关键词: B+树, 重复键值, 溢出页

CLC Number: 

• TP311.12