嵌入式数据库大多用在诸如掌上电脑、PDA、车载设备、移动电话等存储容量非常有限的嵌入式系统中。由于嵌入式数据库存储容量的限制,如何充分利用这些有限的存储空间,提高嵌入式数据库的空间利用率一直是倍受关注的研究课题。目前,绝大多数嵌入式数据库都提供B~+-树索引机制。它的最大优点是效率高,能同时进行随机查找和顺序查找,且动态调整平衡。但对嵌入式系统而言,B~+-树存在着浪费存储空间的缺点。根据研究显示B~+-树索引机制平均空间利用率仅能保证在50%左右,浪费了近一半的存储空间。 本文的主要任务是研究和实现一个具有较高空间利用率的面向嵌入式数据库的改进B~+-树索引机制。首先分析了B~+-树索引机制的主要实现思想及其优缺点,在此基础上提出了一种改进B~+-树索引机制;然后在一个开放源码的嵌入式数据库—Berkeley DB中实现了这个索引机制;接着使用改进后的嵌入式数据库中API接口实现了一个具有基本数据存取功能的软件系统,通过反复调试、裁减将这个软件系统移植到本实验室自主开发的嵌入式开发板ES860上;最后,利用Berkeley DB中提供的TCL测试平台进行了一系列测试实验,对B~+-树和改进B~+-树索引机制在空间利用率和消耗时间两个方面进行了详细的实验分析;实验结果表明改进B~+-树索引机制能在牺牲部分实时性的基础上较大提高嵌入式数据库的空间利用率,同时随着扩展度N值的增加,空间利用率提高的幅度也随之增加。