FQM-tree:基于B~+树的时态索引

提出了一种基于B~+树的、针对有效时间区间的索引模式:FQM-tree(fast query map tree).FQM-tree将有效时间区间映射为一维空间上的点,对映射点建立索引;同时增加一个基于内存的辅助索引结构,最大程度地减少对无效节点的访问.该索引结构具有如下优点:首先,将时问区间映射为点,可以直接利用已有应用成熟的、被广泛支持索引结构(如B~+树),这就意味着可以在数据库中快速实现对时态索引的支持,而无需更改DBMS的内核;其次,基于内存的辅助索引结构可以直接定位叶节点,提高了时态查询效率;另外,由于当前B~+树仍是数据库中应用最成熟、最广泛的索引结构,因此借助B+树的基本结构研究时态索引,使得时态索引能够快速地得到具体应用,所以FQM-tree的研究具有广泛的应用价值.理论分析及大量的实验结果均表明,FQM-tree的查询性能优于传统的时态索引方法.

FQM-tree: Temporal Index Based on B~+-tree

A B~+-tree based index model for valid time interval FQM-tree(fast query map tree)is designed.It maps time interval into a point in one dimensional spaces,and then builds index structure for these mapping points;at the same time,reduces the access for the invalid nodes in the greatest degree by building a memory-based auxiliary index structure.The advantages of FQM-tree are listed as followings:firstly,FQM-tree can be implemented in TDB easily without modifying the kernel of its DBMS;secondly,the memory-based auxiliary index structure helps to improve temporal query efficiency;additionally,B~+-tree is still the most mature and widely used index structure in database at current,so studying temporal index based on the basic structure of B~+-tree makes it achieve specific applications rapidly.That makes the research of FQM-tree with wide application value.Theoretical analysis and excessive experiments show that the performance of FQM-tree is superior to traditional methods of temporal index.