面向嵌入式数据库的改进 B + 一 树索引机制.pdf

维普资讯 CN43—1258／TP 计算机工程与科学 2007年第29卷第 1期 ISSN 1007—130X COMPUTERENGINEERING SCIENCE Vo1．29．No．1，2007 文章编号 ：1007-130X(2007)001—0101—02 面向嵌入式数据库的改进 B+一树索引机制 An ImprovedB+-TreeAccessM ethodBased onEmbeddedDatabases 刘彩苹 ，李仁发 ，刘喜苹 LIU ca．卜pin ，LIRen-fa~，LIU Xi-ping2 (1．湖南大学计算机与通信学院，湖南 长沙 410082；2．湖南大学软件学院，湖南 长沙 410082) (1．SchoolofComputerandCommunications，HunanUniversity，Changsha410082； 2．SchoolofSoftware，HunanUniversity，Changsha410082，China) 摘 要：B 一树是数据库中常用的索引机制，它最大的优点是效率高，而最大的缺点是空间利用率较差。这对空间资 源非常有限的嵌入式数据库来说影响尤为巨大。本文针对B一树的这个缺点，研究了一种改进 B 一树，并将改进后的B 一 树索引机制成功地应用在嵌入式数据库一伯克利数据库 中。这种改进B+一树索引机制不仅继承了B 一树效率高，能同时 进行随机查找和顺序查找的优点，还克服了B 一树空间利用率较差的缺点，更提高了数据库查找记录的速度。实验结果证 明了改进 B+一树索引机制比B 一树索引机制具有更高的空间利用率。 Abstract：B+一treeisacommonly-usedorganizationindatabasesystems．Itsstrongpointisitshighefficiency，andits sho~comingisthelow utilizationofstorag~ Thisdrawbackhasbadimpactespeciallyonembeddeddatabasesystemswhich havelimitedstorage．Thisprojectimprovestheaccessmethodaimingatthisdeficiencyandappliesthisimprovedaccess methodtOanembeddeddatabase-BerkeleyD＆ Thisimprovedaccessmethodnotonlyinheritsthestrongpo intofB 一tree whichhashighefficiencyand canperform sequentialandrandom search，butalsoovercomestheshortcomingsofB 一tree which hasalow utiliaztionofstorage．Experimentalresultsshow thatthemiprovedB+一treeaccessmethodCanattainhigher storageutilizationattheexpenseofmoreexecutiontimethantheconventionalB+一treeaccessmethod． 关键词：B 一树；数据库；空间利用率 Keywords：B 一tree；database；storageutilization 中图分类号：TP311．13 文献标识码：A 和顺序查找，而且动态调整平衡。但是，对内存空间极为宝 1 引言