嵌入式内存数据库查询算法改进

Improvement of Embedded Memory Database Search Algorithm

目前绝大多数嵌入式数据库系统中使用B树或B+树索引机制,它的优点是效率高,能动态维持平衡。然而研究表明B树索引机制平均空间利用率仅达到50%左右。这对存储空间有限的嵌入式设备而言,存在浪费存储空间的问题。在比较和分析B树索引机制,AVL树索引机制,HASHAVL树索引机制的实现思想及其优缺点后,提出了基于B树的查询改进算法,该算法能够解决B树中存在的顺序查找效率低的问题,保留了随机查找空间利用率高的优点,为实时性要求不高和资源有限的嵌入式系统提供了更好的数据查找方法。

At present most of the embedded database systems use the B tree or B＋ tree indexing mechanism, whose advantages mainly lie in its high efficiency and its ability to balance dynamically. However, studies have shown that the average space utilization ratio of B tree indexing mech- anism is only about 50 %, resulting in a waste of storage space for embedded devices whose storage space is limited. Based on a comparative analysis of the advantages and disadvantages of Btree, AVL-tree and HASHAVL-tree indexing mechanisms, we proposed an improvement algorithm based on the B-tree inquiry. This algorithm could solve the problem of low-efficiency sequential query in the B tree, because it retained the high efficiency in random searching space. It could provide a better data-search method for the embedded system whose timely request was not high and resources were limited.