基于结构摘要的时态索引技术

目前B+树仍是在商业数据库中应用最广泛的基本索引结构,为在现有数据库平台上对时态数据进行有效操作,有必要研究基于B+树的时态索引技术.研究了一种以B+树为基本存储结构、基于结构摘要的时态索引方法CMap-tree. 首先,引入基于内存的结构摘要,通过存储结点必要的结构摘要信息,有效地降低了时态操作过程中对无效结点的访问;其次,提出了时态矩阵的概念,并以时态矩阵为参考详细分析了各时态关系对应的结果集;然后,在结构摘要的基础上,详细讨论了CMap-tree的时态插入、查询和更新算法.最后,通过仿真实验,对CMap-tree的空间利用率、查询效率和更新效率等基本性能与现有时态索引方法进行了比较和分析.实验结果表明,CMap-tree具有明显优势.

Temporal Indexing Technique Based on Structural Summary

With extensive applications of temporal data management technology, temporal index has become one important way to make efficient query and management for temporal data. Now, B+-tree is still the most widely used index structure in commercial databases. So, in order to make effective operation on temporal data in existing databases, it is necessary to research B+-tree based temporal index structure. A structural summary based temporal indexing structure—CMap-tree is proposed, which maps time interval into one-dimensional point when reserving the lexicographic order of time intervals and uses B+-tree as its basic storage structure. Firstly, a main memory structural summary is introduced, and by storing necessary structural summary information of nodes, invalid nodes visited during temporal operations (temporal inserting, querying and updating) have been reduced in greatest degree. Secondly, the concept of temporal matrix for time intervals is proposed, and then based on the temporal matrix, detailed analysis of the resulting set corresponding to each temporal relation is discussed. Then, based on the structural summary, temporal inserting, querying and updating algorithms of CMap-tree are discussed. Finally, the performance of CMap-tree is systemically analyzed and compared with that of other competitors in terms of space utilization, querying and updating performance. Extensive experiments show that CMap-tree has obvious advantages.