基于改进B~+树算法的数据索引机制研究
摘要
本文主要研究分析了B~+树索引,针对B~+树算法从搜索性能和空间利用率方面做了改进。改进B~+树算法的核心思想是让非叶子结点可含有的最多关键字个数是叶子结点的N倍。其中在搜索性能方面,算法的改进体现在降低了树的深度,减少了访问磁盘的次数,从而降低了检索时间;在空间利用率方面,主要体现在删除关键字时,除合并操作外,还进行了节点的左右旋转,将其各结点平衡,使树的整体平衡性比较好,提升了结点的空间利用率。本文采用Visual C++对改进的算法进行了验证,从时间开销、空间利用率、树的深度等方面综合比较,其结果证明了改进B~+树算法在搜索性能和空间利用率方面都有所改进。
The article mainly analyzes the index of B~+ tree and improves search performance and space utilization of B~+ tree algorithm. The central idea of improved B~+ tree algorithm is to allow the number of keys in non-leaf node is N times of leaf node. In search performance, the improvement of the algorithm reflects that it reduces the depth of the tree and the number of disk access, so that it reduces the search time; in the utilization of space, it mainly represents in the deletion of keywords. With the exception of the combined operation, but also the nodes are rotated around and balances its nodes so that the tree's overall balance is better and enhances the nodes' space utilization. The article uses Visual C++ to validate the improved algorithm from spending time, space utilization, and the depth of the tree and so on to compare synthetically. The results prove that the improved B~+ tree algorithm improves search performance and space utilization.
The article mainly analyzes the index of B~+ tree and improves search performance and space utilization of B~+ tree algorithm. The central idea of improved B~+ tree algorithm is to allow the number of keys in non-leaf node is N times of leaf node. In search performance, the improvement of the algorithm reflects that it reduces the depth of the tree and the number of disk access, so that it reduces the search time; in the utilization of space, it mainly represents in the deletion of keywords. With the exception of the combined operation, but also the nodes are rotated around and balances its nodes so that the tree's overall balance is better and enhances the nodes' space utilization. The article uses Visual C++ to validate the improved algorithm from spending time, space utilization, and the depth of the tree and so on to compare synthetically. The results prove that the improved B~+ tree algorithm improves search performance and space utilization.
引文
[1]Clifford A.Shaffer著,张铭,刘晓丹译.数据结构与算法分析(C++版)[M].北京:电子工业出版社,2004.
[2]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2004.
[3]陈嘉.嵌入式主存数据库索引机制的研究与改进[D].湖南:湖南师范大学,2006:15-94.
[4]Chanho Ryu,Eunmi Song etc.Hybrid-TH:a Hybrid Access Mechanism for Real-Time Memory-Resident Database Systems.Real-Time Computing System and Applications.Proceeding of the Fifth International Conference,1998:303-310.
[5]Ronald Fagin,Jurg Nievergelt.Extendable Hashing-A Fast Access Method for Dynamic Files.ACM Trans on Database Systems,1979,4(3):315-344.
[6]Witold Litwin.Linear Hashing:A New Tool for File and Table Addressing.Proceeding of the Sixth Conference on VLDB,1980:212-223.
[7]Anastasia Analyti,Sakti Pramanik.Fast Search in Main Memory Databases.Proceeding of ACM SIGMOD Conference on Management of Data,1992:215-224.
[8]王洪海,潘朝华.内存数据库的数据结构分析[J].现代电子技术,2004,3:96-97.
[9]Tobin J.Lehman,Michael J.Carey.A Study of Index Structures for Main Memory Database Management Systems.Proceedings of the Twelfth International Conference on Very Large Databases,1986:294-302.
[10]Comer D.The Ubiquitou B-Tree[J].ACM Computing Surveys,1979,11(2):121 - 137.
[11]Mary E.S.Locmis.Data Management and File Structures.second edition,Prentice Hall,Inc,1989.
[12]David J.DeWitt,Randy H.Katz,Frank Olken,Leonard D.Shapiro,Michael R.Stonebraker,David Wood.Implementation Techniques for Main Memory Database System.Proceedings of 1984 ACM SIGMOD Annual Meeting,1984.
[13]http://www.sqlite.org/.
[14]Michael Owens.The Definitive Guide to SQLite.ISBN- 13:978-1-9059-673-9:171-175.
[15]David M.Arnow,Aaron M.Tenenbaum.An Empirical Comparison of B-trees,Compact B-trees and Multiway Trees.Proceedings of 1984 ACM SIGMOD Annual Meeting,1984.
[16]毛法尧.B树分析[J].计算机工程与应用,1995,2:22-24.
[17]李军,孙智锋,王鑫.B-树在数据存储与搜索中的应用[J].信息技术,2000,2:17-18.
[18]盛小亮.嵌入式数据库索引机制研究与实现[D].成都:电子科技大学,2007:29-31.
[19]黄加喜,陈天煌,郑胜英.嵌入式数据库索引机制的研究[J].计算机安全,2008,9:55-57.
[20]刘彩苹.面向嵌入式数据库索引机制研究[D].湖南:湖南大学,2004:17-23.
[21]刘彩苹,李仁发.面向嵌入式数据库的改进B~+-树索引机制[J].计算机工程与科学,2007,29(1):37-42.
[22]魏小亮,蔡弘.B-树/B~+树的批量插入算法[J].中央民族大学学报(自然科学版),2001,10(1):57-60.
[23]吴永英,雷红利,许向阳.一种自底向上构造索引B~+树的方法[J].计算机工程与应用,2004.6:200-201.
[24]陆志峰,陈新建.全链接指针B~+树的研究[J].计算机工程与应用,2000,1:37-40.
[25]陆志峰.B~+树阶数m的最优选取[J].计算机应用与软件,2002,7:57-60.
[26]Abraham Silberschatz,Henry E Korth,s.Sudarsham.数据库系统概论[M].北京:机械工业出版社,2001.
[27]王英强,石永生.B~+树在数据库索引中的应用[J].长江大学学报(自然科学版),2008,5(1)理工:233-235.
[28]http://blog.csdn.net/manesking/archive/2007/02/09/1505979.aspx.
[29]V Gaede,O Gunther.Multidimensional Access Methods.ACM Computing Surveys,1997:15-16.
[30]Ailamaki A,Dewitt D J,Hill M D,et al.DBMS on a modern processor:where does time go?[A].Proceedings of the 25th International Conference on Very Large Data Bases[C],Edinburgh,Scotland,UK,1999.
[31]Boncz P A,Manegold S,Kersten M L.Database architecture optimized for the new bottleneck:memory access[A].Proceedings of the 25th International Conference on Very Large Data Bases[C],Edinburgh,Scotland,UK,1999.
[32]Rao J,Ross K A.Cache conscious indexing for decision-support in main memory[A].Proceedings of the 25th International Conference on Very Large Data Bases[C],Edinburgh,Scotland,UK,1999.
[33]徐德智,滕婧.XML数据的B树存储实现及更新[J].计算技术与自动化,2002,21(3):42-45.
[34]陈雍,谢旭升,魏根芽.Oracle B~*树索引内部机制及其应用的研究[J].计算机与现代化,2008,10:56-59.
[35]王晨,陈刚,董金祥.改进型缓存敏感B~+树的研究[J].计算机测量与控制,2006,14(11):1531-1534.
[36]唐文龙.几种典型树形索引技术对比分析[J].百色学院学报,2007,20(6):91-94.
[37]吴恒山,徐晓军.基于改进B~+树索引的结构连接算法[J].计算机工程,2005,31(16):86-88.
[38]代崴,周剑锋.B~+树索引文件研究与应用[J].软件导刊,2006,11:38-40.
[39]陆志峰,陈新建.B~+树索引文件结构的优化设计[J].计算机工程与设计,2000,21(3):40-44.
[40]《电脑编程技巧与维护》杂志社主编.Visual C/C++编程精选集锦[M].北京:科学出版社,2003.
[41]杨敏.Visual C++6.0实用教程[M].成都:电子科技大学出版社,2001.
[42](美)Stephen D.Gilbert著,赵军锁,龚波,李志等译.跟我学Visual C++6[M].北京:机械工业出版社,1999.
[43]中国IT培训工程编委会编.VC++6.0入门与进阶[M].珠海:珠海出版社,2002.
[2]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2004.
[3]陈嘉.嵌入式主存数据库索引机制的研究与改进[D].湖南:湖南师范大学,2006:15-94.
[4]Chanho Ryu,Eunmi Song etc.Hybrid-TH:a Hybrid Access Mechanism for Real-Time Memory-Resident Database Systems.Real-Time Computing System and Applications.Proceeding of the Fifth International Conference,1998:303-310.
[5]Ronald Fagin,Jurg Nievergelt.Extendable Hashing-A Fast Access Method for Dynamic Files.ACM Trans on Database Systems,1979,4(3):315-344.
[6]Witold Litwin.Linear Hashing:A New Tool for File and Table Addressing.Proceeding of the Sixth Conference on VLDB,1980:212-223.
[7]Anastasia Analyti,Sakti Pramanik.Fast Search in Main Memory Databases.Proceeding of ACM SIGMOD Conference on Management of Data,1992:215-224.
[8]王洪海,潘朝华.内存数据库的数据结构分析[J].现代电子技术,2004,3:96-97.
[9]Tobin J.Lehman,Michael J.Carey.A Study of Index Structures for Main Memory Database Management Systems.Proceedings of the Twelfth International Conference on Very Large Databases,1986:294-302.
[10]Comer D.The Ubiquitou B-Tree[J].ACM Computing Surveys,1979,11(2):121 - 137.
[11]Mary E.S.Locmis.Data Management and File Structures.second edition,Prentice Hall,Inc,1989.
[12]David J.DeWitt,Randy H.Katz,Frank Olken,Leonard D.Shapiro,Michael R.Stonebraker,David Wood.Implementation Techniques for Main Memory Database System.Proceedings of 1984 ACM SIGMOD Annual Meeting,1984.
[13]http://www.sqlite.org/.
[14]Michael Owens.The Definitive Guide to SQLite.ISBN- 13:978-1-9059-673-9:171-175.
[15]David M.Arnow,Aaron M.Tenenbaum.An Empirical Comparison of B-trees,Compact B-trees and Multiway Trees.Proceedings of 1984 ACM SIGMOD Annual Meeting,1984.
[16]毛法尧.B树分析[J].计算机工程与应用,1995,2:22-24.
[17]李军,孙智锋,王鑫.B-树在数据存储与搜索中的应用[J].信息技术,2000,2:17-18.
[18]盛小亮.嵌入式数据库索引机制研究与实现[D].成都:电子科技大学,2007:29-31.
[19]黄加喜,陈天煌,郑胜英.嵌入式数据库索引机制的研究[J].计算机安全,2008,9:55-57.
[20]刘彩苹.面向嵌入式数据库索引机制研究[D].湖南:湖南大学,2004:17-23.
[21]刘彩苹,李仁发.面向嵌入式数据库的改进B~+-树索引机制[J].计算机工程与科学,2007,29(1):37-42.
[22]魏小亮,蔡弘.B-树/B~+树的批量插入算法[J].中央民族大学学报(自然科学版),2001,10(1):57-60.
[23]吴永英,雷红利,许向阳.一种自底向上构造索引B~+树的方法[J].计算机工程与应用,2004.6:200-201.
[24]陆志峰,陈新建.全链接指针B~+树的研究[J].计算机工程与应用,2000,1:37-40.
[25]陆志峰.B~+树阶数m的最优选取[J].计算机应用与软件,2002,7:57-60.
[26]Abraham Silberschatz,Henry E Korth,s.Sudarsham.数据库系统概论[M].北京:机械工业出版社,2001.
[27]王英强,石永生.B~+树在数据库索引中的应用[J].长江大学学报(自然科学版),2008,5(1)理工:233-235.
[28]http://blog.csdn.net/manesking/archive/2007/02/09/1505979.aspx.
[29]V Gaede,O Gunther.Multidimensional Access Methods.ACM Computing Surveys,1997:15-16.
[30]Ailamaki A,Dewitt D J,Hill M D,et al.DBMS on a modern processor:where does time go?[A].Proceedings of the 25th International Conference on Very Large Data Bases[C],Edinburgh,Scotland,UK,1999.
[31]Boncz P A,Manegold S,Kersten M L.Database architecture optimized for the new bottleneck:memory access[A].Proceedings of the 25th International Conference on Very Large Data Bases[C],Edinburgh,Scotland,UK,1999.
[32]Rao J,Ross K A.Cache conscious indexing for decision-support in main memory[A].Proceedings of the 25th International Conference on Very Large Data Bases[C],Edinburgh,Scotland,UK,1999.
[33]徐德智,滕婧.XML数据的B树存储实现及更新[J].计算技术与自动化,2002,21(3):42-45.
[34]陈雍,谢旭升,魏根芽.Oracle B~*树索引内部机制及其应用的研究[J].计算机与现代化,2008,10:56-59.
[35]王晨,陈刚,董金祥.改进型缓存敏感B~+树的研究[J].计算机测量与控制,2006,14(11):1531-1534.
[36]唐文龙.几种典型树形索引技术对比分析[J].百色学院学报,2007,20(6):91-94.
[37]吴恒山,徐晓军.基于改进B~+树索引的结构连接算法[J].计算机工程,2005,31(16):86-88.
[38]代崴,周剑锋.B~+树索引文件研究与应用[J].软件导刊,2006,11:38-40.
[39]陆志峰,陈新建.B~+树索引文件结构的优化设计[J].计算机工程与设计,2000,21(3):40-44.
[40]《电脑编程技巧与维护》杂志社主编.Visual C/C++编程精选集锦[M].北京:科学出版社,2003.
[41]杨敏.Visual C++6.0实用教程[M].成都:电子科技大学出版社,2001.
[42](美)Stephen D.Gilbert著,赵军锁,龚波,李志等译.跟我学Visual C++6[M].北京:机械工业出版社,1999.
[43]中国IT培训工程编委会编.VC++6.0入门与进阶[M].珠海:珠海出版社,2002.