面向嵌入式数据库的改进B^+-树索引机制

An Improved B^+-Tree Access Method Basedon Embedded Databases

B^+-树是数据库中常用的索引机制,它最大的优点是效率高,而最大的缺点是空间利用率较差。这对空间资源非常有限的嵌入式数据库来说影响尤为巨大。本文针对B^+-树的这个缺点,研究了一种改进B^+-树,并将改进后的B+-树索引机制成功地应用在嵌入式数据库-伯克利数据库中。这种改进B+-树索引机制不仅继承了B^+-树效率高,能同时进行随机查找和顺序查找的优点,还克服了B^+-树空间利用率较差的缺点,更提高了数据库查找记录的速度。实验结果证明了改进B^+-树索引机制比B+-树索引机制具有更高的空间利用率。

B^＋-tree is a commonly-used organization in database systems.Its strong point is its high efficiency,and its shortcoming is the low utilization of storage. This drawback has bad impact especially on embedded database systems which have limited storage. This project improves the access method aiming at this deficiency and applies this improved access method to an embedded database-Berkeley DB. This improved access method not only inherits the strong point of B^＋-tree which has high efficiency and can perform sequential and random search, but also overcomes the shortcomings of B^＋-tree which has a low utilization of storage. Experimental results show that the improved B^＋-tree access method can attain higher storage utilization at the expense of more execution time than the conventional B^＋-tree access method.