一种处理B^+树重复键值的方法  

Approach for Handling Duplicate Keys in B^+Tree

作　　者：徐逸文[1,2] 方钰[1,2] 陈闳中[1,2] 

机构地区：[1]同济大学计算机科学与技术系,上海201804 [2]同济大学嵌入式系统与服务计算教育部重点实验室,上海201804

出　　处：《计算机工程》2009年第5期25-27,共3页Computer Engineering

基　　金：上海市国际科技合作基金资助项目"智能交通信息服务技术及移动终端导航系统"(062107037);上海市国际科技合作基金资助项目"车辆网络感知导航的关键技术与高性能支撑平台"(075 1 07005)

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

关 键 词：B^+树 重复键值 溢出页 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]