时态数据的可变Hash索引  

Variable Hashing for Temporal Data

作　　者：蒋夏军[1] 吴慧中[1] 李蔚清[1] 

机构地区：[1]南京理工大学计算机系,南京210094

出　　处：《计算机科学》2006年第1期130-133,242,共5页Computer Science

基　　金：受国防科技预先研究项目支持。

摘　　要：索引技术是时态数据库查询优化的重要方法之一。本文提出的可变 Hash(VH)索引是建立在时间属性上的一种新的动态索引技术,主要目的是提高时态数据库快照查询的效率。由于时间的不确定性,在时态数据的时间属性上建立 Hash 索引比较困难。VH 索引克服了 Hash 索引这一难点,提出了索引参数可变的思想,并应用 B^+-树对Hash 参数进行组织。查询时由时间值在 B^+-树上获得 Hash 参数,进而确定数据的存储地址。通过对其时间复杂度和空间复杂度的理论分析以及实验验证,表明该索引技术可以减少索引查找以及读取数据的 I/O 次数,并具有理想的空间利用率。Index technology is one of the important factors during the process of data query optimizing, especially tar temporal database. A new hashing method for temporal data is designed to improve the efficiency of database snapshot query in this paper, and the method is called Variable Hashing （VII）. Generally, it ~s difficult to establish hashing index for time value because of the time＇s indeterminacy. VH solves this problem, and it is based on the start time of a database＇s transaction time attribute. The parameters of hashing function are variableaccording to the time attribute of tuples, and they are organized as a B^＋-tree. Using a time value to query the B^＋-tree can get the hashing parameters, and the parameters can be used to calculate the address of target data. Carefull analysis and experimental test show that the time complexity of VH＇s snapshot query is better than other snapshot index methods, and its space complexity is also optimal.

关 键 词：时态数据库 可变Hash索引 快照查询 时间复杂度 索引技术 HASH 可变 时间属性 查询优化 空间复杂度 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] TP311.132[自动化与计算机技术—计算机科学与技术]