时间：2022-11-11 10:30:01 | 来源：信息时代
时间：2022-11-11 10:30:01 来源：信息时代
时态数据索引技术 : 支持事务时间和有效时间的一种索引技术。传统索引(例如B+-树)采用单值数据、线性的索引技术,时态数据索引则是非线性的、多维的索引技术。在建立数据的线性索引的同时,需要建立相应的事务时间和有效时间维索引。
时间是分区段的、非单值的,采用传统的索引技术存储时态数据,会导致元组的时间区间要被分割成几块,并映射到不同的索引页上,这会产生重叠问题,降低检索效率。时态索引除了需要考虑其分页和数据聚簇之外,还需要考虑其他问题,如数据的查询方式对时态索引的影响,例如对时间的点切片查询很有效率的索引,可能降低对数据值的点查询效率。随着时间的推移,数据增量巨大,可能需要迁移到其他存取介质上,存取介质的变化也会导致索引结构的变化。
1.支持事务时间的索引技术
根据不同的数据聚簇方式,事务数据库索引技术可以分成三种类型: 按键索引、按时间索引和按键-时间索引。
1982年,Ben-Zvi等人提出了反向链(reverse chaining),并由Lum等人于1984年改进了该方法,这是一种按键索引技术,它将当前状态的数据跟历史数据分开存储。因为当前状态下的数据被查询的多,因此能缩小查找结构,提高查找速度。每个键的所有版本按照其事务时间的降序排列成一条链,按不同的键形成了多条时间链。在此方法中当前状态的数据用传统的B+树做索引。历史数据可以从当前键开始回溯而得到。
Gunadhi和Segev提出的AP-树(appended-only tree)是一种按时间索引方法。AP是树是一种ISAM索引和B+-树相结合的多路搜索树。每一个元组被赋予一个[起始时间,结束时间]的时间区间,并在起始时间上作索引。每个叶子结点用(t,b)表示,其中t表示时间,b是指针,指向其对应的桶,桶内是一些元组的集合: 它们的起始时间比其前一个元素的起始时间晚的,而且比t早或跟t相等;每个非叶子结点的则指向下一层。其更新操作的复杂度为O(1)。
2.支持有效时间的索引技术
历史数据库必须维护数据时间属性的动态变化。Kanellakis等人提出了Metablock树,实现了对数据有效时间动态变化的管理。Metablock树是B维的索引方法,它把二维时间空间的上半部分划分为多个小块,每个小块有B2数据点。但是Metablock树是个半动态的结构,因为只支持时间区间的增添而不支持删除。
3.双时态数据库索引技术
在双时态数据库中比较有代表性的索引是R-tree,GR-tree,4R-树。
(1) R-tree时态索引技术:R-树最早由Auttman在1984年提出,其后又有了许多变形,形成了由R-树、R+-树、R*-树、HilbertR-树、SR-树等组成的R-树系列空间索引。R-tree是一种空间索引技术,为空间搜索提供了一种合适的数据结构,以提高搜索速度。R树空间索引技术的核心是:根据搜索条件(一个矩形)迅速找到与该矩形相交的所有空间对象集合。当数据量巨大,矩形框相对于全图很小时,这个集合相对于全图数据集大为缩小,在这个缩小的集合上再进行各种复杂的搜索,可以减少IO操作,大大提高查询效率。
(2) GR-tree时态索引技术: 通常的R-tree绑定的矩形框是固定不变的,不能用于含有now和UC等时间变元的时态索引,为了解决此问题,扩充一般的R-tree使其可处理带变元的时态数据,称之为GR-tree。在GR-tree的层次上使用变量now和UC,就可以在叶子结点上确切的记录时间域的几何关系,根据有效时间和事务时间的终止值是固定的还是可变的可将双时态域分为四种类型。相应的双时态域对应增长矩形、固定矩形、增长楼梯形和固定楼梯形。
(3) 4R-tree时态索引技术:应用GR-tree能使时态数据的检索速度提高,其不足之处是现有的数据库管理系统内核暂时还不能处理这种带变元的索引方法,而4R-tree就很好地解决了这个问题,它通过变换将不同的变元转化成不同固定值,将GR-tree树分别映射到四种不同形式的R-tree再利用R-tree索引,对于查询中的变元也采用同样的方法有效解决了GR-tree不能应用于实际的不足。4R-树索引由4个R-树组成,索引过程比较复杂。
在线咨询
