摘要: 当前B+树索引结构常采用“溢出页”处理重复出现的键值,易于实现,但存在严重的空间浪费。该文通过改进索引结构的定义,使B+树能够显式支持重复键值,并给出相应算法。实验证明,采用该方法的B+树能有效减少索引文件的大小,使B+树满足更多数据库索引的需求。
关键词:
B+树,
重复键值,
溢出页
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+树重复键值的方法[J]. 计算机工程, 2009, 35(5): 25-27.
XU Yi-wen; FANG Yu; CHEN Hong-zhong;. Approach for Handling Duplicate Keys in B+Tree[J]. Computer Engineering, 2009, 35(5): 25-27.