（控制科学与工程专业论文）组态实时数据库索引机制的研究与实现.pdf

摘要 实时数据库是指对数据存储、传输、读取有严格的时间限制的数 据库，它应用于对数据库和实时处理两者的功能和特性均有要求的场 合。实时数据库的数据和事务都具有显式的定时限制，系统的正确性 不仅依赖于逻辑结果，更依赖于逻辑结果产生的时间，为了满足实时 数据库的高性能要求，必须解决许多理论和关键技术问题，这其中需 要解决的一个关键问题是建立合适的实时数据库索引机制。 经典的索引机制主要分为三大类：一类是基于h a s h 函数对数 据随机组织的索引机制，如可扩展h a s h ( e h ) ，线性h a s h ( l h ) ，带 冲突链的h a s h ( c b h ) 等；另一类是基于查询树对数据有序组织的索 引机制，如b 树，b + 树，t 树，t 串树等；最后一类是c h a n b o r y u 等提出的综合h a s h 表和查询树特点的混合索引机制h y b r i d h t ，但 这些传统的索引机制难以满足组态实时数据库的高效数据存储要求， 因而建立一种合适的数据库索引机制就有了突出的意义。 本文在详细分析了传统索引机制如h a s h ，t 树，t 术树以及 h y b r i d - t h 的基础上，提出了一种改进的混合索引机制h t 术，详细介 绍了h - t * 索引的设计思路以及实现过程，从理论上分析了h t 术的时 空性能，并通过h y b r i d t h 和h - t * 两种混合索引机制的一系列对比 实验验证了h t 木索引机制的优良时空性能，最后对h t 冰的实际应用 性能进行了测试。理论分析和实验证明，h t 术索引是一种高效与合理 的混合索引机制。 关键词：实时数据库，索引，h a s h ，h t 术 a b s t r a c t t h ei h d b ( r e a l t i m ed a t a b a s e ) i sak i n do fd a t a b a s es y s t e m w h i c hh a ds t r i c tc o n s t r a i n t so nd e l a yo ft h ed a t as t o r a g e ，t r a n s m i t t i n g ，a n d r e a d i n g r t d bi sw i d e l yu s e di nt h ef i e l d s w h e r et h e r ea r eu r g e n t d e m a n d so nt h ef u n c t i o n so fd a t a b a s es y s t e ma n dt h e p r o p e r t i e so f r e a l t i m et r a n s a c t i o n d a t aa n dt r a n s a c t i o n si nar e a l t i m ed a t a b a s e s y s t e ms h o u l dh a v ee x p li c i tt i m i n gc o n s t r a i n t s ，t h u st h ec o r r e c t n e s so ft h e s y s t e mr e l i e sn o to n l yo nl o g i cr e s u l t sb u ta l s ot h et i m ew h e nt h el o g i c a l r e s u l t sa r ep r o d u c e d i no r d e rt om e e tt h eh i g hp e r f o r m a n c er e q u i r e m e n t o fr t d b ，t h e r ea r em a n yk e yt h e o r i e sa n dt e c h n o l o g i e sm u s tb es o l v e d o n eo ft h e mi st ob u i l dar i g h tr e a l t i m ed a t a b a s ei n d e xm e c h a n i s m 。 c l a s s i c a li n d e xm e c h a n i s mi sm a i n l ys o r tt ot h r e ek i n d s ：o n eo f t h e mi sh a s ht a b l e b a s e di n d e xm e c h a n i s mb e i n gt h a td a t ai sr a n d o m o r g a n i z e d ，f o re x a m p l e ，e x p a n dh a s h ( e h ) ，l i n e a r i t yh a s h ( l h ) ， c o n f l i c t c h a i nb a s e dh a s h ( c b h ) a n ds oo n ；a n o t h e ri sb a s e do n q u e r y - t r e eb e i n gt h a tt h ed a t ai so r d e ro r g a n i z e d ，f o ri n s t a n c e ，bt r e e ，b + t r e e ，tt r e e ，t 木t r e ea n ds oo n ，f i n a li s t h eh y b r i di n d e xm e c h a n i s m h y b r i d h tb e i n gt h a t t h ec h a r a c t e r i s t i e so fh a s h t a b l ea n dq u e r y - t r e e i sc o m p o u n d b u tt h e s et r a d i t i o n a li n d e xm e c h a n i s mi sd i f f i c u l tt o s a t i s f i e dt h eh i g h e f f e c td a t aa c c e s sr e q u e s to fc o n f i g u r a t i o nr e a l t i m e d a t a b a s e 。t h e r e f o r e t ob u i l dak i n do fr i g h ti n d e xm e c h a n i s mh a sa n o u t s t a n d i n gm e a n i n g 。 a f t e rt h ea n a l y s i so fc l a s s i c a li n d e xm e c h a n i s mw h i c hi n c l u d i n g h a s h ，tt r e e ，t 冰t r e e ，a n dh y b r i d h t , t h i st h e s i sd e s i g nai m p r o v e dh y b r i d m e c h a n i s mc a l l e dh t 宰i te l a b o r a t e st h ed e s i g nt h o u g h ta n dt h e r e a l i z a t i o np r o c e s so fh t 木i n d e xm e c h a n i s mi nd e t a i l i ta n a l y z e st h e t i m ea n ds p a c ep e r f o r m a n c eo ft h en e wi n d e xm e c h a n i s mi nat h e o r e t i c a l l e v e l n e x t i tv e r i t i e st h ee x c e l l e n tp e r f o r m a n c eo nt i m ea n ds p a c eo f h t 水t h r o u g has e r i e so fe x p e r i m e n t sw h i c hm a k ec o m p a r i s o n sb e t w e e n t h et w oh y b r i dm e c h a n i s m h y b r i d t ha n dh t ，l c 1 a s t l y , i tv e r i f i e st h e a p p l i c a t i o np e r f o r m a n c eo fh t 水，t h er e s u l th a sp r o v e dt h a th t 木i n d e x m e c h a n i s mi sh i g h e m c i e n ta n dc o r r e c t k e yw o r d s ：r e a l t i m e d a t a b a s e ，i n d e x ，h a s h ，h t 木 i i l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：趟曰期：皇翌l 年劝翌日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：丞绝导师签名盎垒二日期：幽年月盈曰 第一章绪论 1 1 本文的研究意义 第一章绪论 随着计算机技术的发展和自动化水平的提高，出现了许多对数据的存取和管 理具有时间约束的应用，例如工业控制、数据通信、证券交易、电力调度、航空 ：】j c 犬等等。这些应用通常要维护海量的数据，要求在指定的时刻或时间期限内对 数锯逊行采集、处理并正确响应，数据只在一定的时间范围内有效，具有明显的 时效性。传统的数据库主要针对永久性数据，没有定时限制，为满足实时应用需 求，要求设计出符合实时要求的数据管理系统即实时数据库( r e a lt i m ed a t a b a s e ，r t d b ) 。实时数据库是数据库与实时系统两者概念、技术、方法和机制的 有机结合【1 1 。实时应用对实时数据库的要求有： ( 1 ) 时效性：具备时间约束要求的数据在截止期内处理完毕； ( 2 ) 可靠性：在高负载和外部异常等情况下仍然正确运行； ( 3 ) 开放性：与应用控制系统连接灵活； ( 4 ) 资源占用：充分利用系统中有限的计算和存储等资源。 传统的数据库称作磁盘式数据库( d i s kr e s i d e n td a t ab a s e ，d r d b ) ，数据 是保存在非易失性设备一磁盘上的，数据从磁盘上取到内存经过处理再写回磁 毹。伴随半导体工艺的飞速发展，内存的容量得到大幅攀升，成本却在过去的 2 0 年下降了1 0 倍，为机器装配上g 级别的主存成为可能。鉴于访问主存的时间 比访问磁盘的时间小几个数量级，如果将需要访问的数据事先装入主存将会大大 提升系统处理速度。这种将需要处理的全部或者大部分数据直接放入主存的数据 库被称作内存数据库【2 i ( m a i nm e m o r yd a t ab a s e ，m m d b ) 。内存数据库作为实时 数据库的底层实现方式被广泛采纳。 把实时数据库系统建立在内存数据库基础之上，不仅能极大地提高系统的性 能f - 3 1 ，弥补因实时事务运行带来的系统丌销，而且最大限度地减少了实时事务执 行过程中的动态不可预测因素，提高了实时事务的可预测性1 4 1 ；从而为优先级分 派、事务调度和并发控制提供可靠依据，减少事务在数据和资源上的冲突，减少 雨务的非预计夭折，进而保证硬截止事务的按时完成，为整个实时数据库系统的 实现奠定了良好的基础【5 j 。 然i 而，内存数据库与传统的数据库却有着极大的区别。传统的磁盘数据库系 统中使用的数据结构通常足旨在减少磁盘存取【6 j 。其思想是便于很快找到数据所 存的磁盘l 二的块并将其取到内存，一旦进入内存，则搜索整块以找到相应数据。 硕士学位论文第一章绪论 在内存中搜索一块的时间比起i o 操作时问来要短很多。在内存数据库中，i o 操作在正常情况下已经极少或者消除了，其目标已由减少i o 操作时间变为了 c p u 时间和内存空间的高效使用1 8 j 。所以，内存数据库系统的设计应该打破传统 磁盘数据库系统的设计观念，考虑内存的直接快速存取的特点，以c p u 和内存 空间的高效利用为目标来重新设计开发各种策略与算法、技术、方法和机制【9 j 。 通过上述分析可知，传统的索引机制已不再适合，建立一种适合实时数据库的索 引机制就具有了突出的意义。 在实时数据库中每一数据对象不再唯一由其值来表示，每一值还有一与之相 联的时间，即数据是二维的( 值、时问) ，这就使得实时数据库的查询处理有了 新的含义l l 叭。实时数据库不仅记录数据对象的当前映象，也管理对象的变化历 史。因此相对传统数据库来说，实时数据库中的数据量可能要大得多【1 0 】。保证 实时数据库的高效查询也就成了一个亟待解决的问题。同时，实时数据库中具有 几个不等性谓词合取的联接查询较频繁的出现，故其优化也更困难。 实时数据库的这些显著特征都向传统索引技术提出了挑战，在时态数据中， 其时间区间特有的特性将使得传统的索引技术在运用到时态索引上时显得比较 困难【l 引。首先，该时态索引需要搜寻的属性类型有效时间，大多数情况下 是一个时间区间而不是一个时间点。各数据对象的不同映象其有效时问区f n j 以任 意得方式重叠着。时间区间得特性使得其不能进行完全排序。其次，传统数据库 中的索引技术也不适应实时数据库中的海量数据特征。建立合适的索引是提高实 时数据库的查询执行效率的根本解决方法之一。基于以上这些情况，我们在综合 分析多种索引技术的基础上，对实时数据库的索引技术进行了深入的分析。 1 2 国内外研究现状 索引机制是数据库系统的重要组成部分，它是一种能提供对大量繁杂的数据 进行快速查找和操作的机制。经典的索引机制主要分为三大类：一类是基于 h a s h 函数对数据随机组织的索引机制，如可扩展h a s h ( e h ) 1 3 j ，线性 h a s h ( l h ) 1 14 1 ，带冲突链的h a s h ( c b h ) 1 1 引，受控查询多方向h a s h ( c s m h ) 1 6 】 等；另一类是基于查询树对数据有序组织的索引机制，如b 树1 15 1 ，b + 树【17 1 ，a v l 树【18 1 ，t 树f 1 9 】，t 木树1 2 0 】，t - t a i l 2 1 1 树等；最后一类是c h a n b o r y u 等提出的综合 h a s h 表和查询树特点的混合索引机制h y b r i d h t l 2 2 j 。 哈希索引机制足一种通过哈希函数实现键值和记录地址快速映射以提供高 速随机访| 、u j 的机制。现己针对磁盘和内存数据库系统提出了多种哈希机制【2 3 1 ， 它们主要在扩充哈希表地址空间和处理具有相同哈希地址的不同键值的存放技 术上有所不同。使用哈希机制能实现快速奄询，杏找时间复杂度为0 ( 1 ) 。它的主 硕士学位论文第一章绪论 要缺点是对空间的利用率不高，且范围查询效率不高。 带冲突链的哈希机制( c b h ) 能提供对静态文件的随机访问，但不适用于对动 态文件的访问。这是因为当需要扩充或缩减哈希表空问时，需要对整个哈希表进 行重组织。 可扩充的哈希机制( e h ) 【1 3 】由r o n a l df a g i n ，j u r gn i e v e r g e l t 等于19 7 9 年提出， 线性哈希机制( l h ) 【l4 1 ，由w i t o l dl i t w i n 于1 9 9 0 年提出。这两种哈希机制都具有 能根据动态文件的大小变化灵活伸缩哈希表空间的能力。然而，这两种机制并不 适用于内存数据库系统。特别是e h 机制在叶节点相对小的情况下，操作性能将 受大型哈希表的影响而大大下降。而l h 机制对查找和插入操作的反应速度较慢 【2 4 】。最近，针对内存数据库系统提出了两种新的哈希机制，一种是专为保存在 主存中的哈希表设计的改进线性哈希机$ 1 j ( m o d i f i e dl h ，另一种是受控查询多方 向哈希机制c s m h ) 1 1 6 1 。m o d i f i e dl h 和c s m h 都实现了哈希表大小随插入键值 的数量线性增长的目标。但m o d i f i e dl h 的一个显著缺点是由于哈希表空间的线 性增长，用于键和记录地址的转换时间不再是一个常量。而当前对c s m h 的分 析仅限于一个为找到指定记录所需要的键值平均比较次数少于2 的高性能优化 环境中，并且对c s m h 的键加载时间尚未进行分析。由于以上两种机制都假定 记录的哈希值是唯一的，因此可能并不适用于实际应用程序1 2 引。 最新的一种哈希机制称为可扩充的带冲突链的哈希机带i ( e c b h ) 1 2 6 j ，它是e h 和c b h 机制的无缝结合，适用于内存数据库系统中的动态文件。e c b h 用哈希 冲突链代替e h 中的每一个叶节点。但和e h 中的叶节点不同，e c b h 中哈希表 的查找时问可被控制在o ( 1 ) 。在e c b h 中一个足够大的哈希表产生的效果和e h 中一个足够大的叶节点相同。因此，e c b h 继承了c b h 和e h 两者的优点，既 具有高性能，又具有可扩充性1 2 6 1 。 ， 数组曾在i b m 的o b e 项目巾作为索引结构使用。它使用最少量的空间，结 构简单，使用折半查找法可以达到高速的搜索效率，其大小可以预知并且可以方 便地扩充( 可以使用虚存的映像单元使数组动态增长) 。但数组的最大缺点是修改 性能极低，每次插入或删除平均数据移动次数为o ( n ) 州是数组中的元素个数) 。 所以数组只适用于仅读或静态应用环境1 27 。 平衡二叉树( a v l 树) 曾在a t & t 贝尔实验室的s i l i c o n 数据库机器上作为索 引结构使用。a v l 树本质上是一棵二叉树，采用二分检索法，查询速度很快。 但a v l 树上的更新操作经常导致树的不平衡，用于平衡旋转操作的歹f 销过大。 a v l 树每个节点仪存放一个元素，同时还要存储两个子树指针和一些控制信息， 导致存储利用率过低【2 引。 b 树是一种适用于磁钴数据库系统的索引机制。b 树的每个节点有多棵予树， 硕十学位论文第一章绪论 形状宽而浅，从而只需较少次数的磁盘i o 就可以找到目标数据【2 。它规定了 节点的最小容量，从而保证了磁盘空间的有效利用率。很多数据库系统使用b 树的一个变种b + 树。在b + 树中，仅在叶节点中存放实际数据。对于内存数据库 系统，b 树比b + 树要好。因为在m m d b s 中，仅用叶节点存放数据会浪费存储 空问。总的来说，b 树具有下列优点【2 9 1 ： 在b 树中叶节点占多数，而叶节点没有子树指针，故指针相对数据的空间 占用量小很多，从而提高了内存空间的利用率；b 树深度不大，采用二分查找法 仅需搜索少量节点，查询速度较高； b 树上的修改操作通常仅涉及一个节点中的元素移动，故修改速度也较高。 但b 树和b + 树的设计原则均与内存数据库系统柏悖，在这两种树型结构中， 子树指针的空问占用率都较大，并且采用将索引项和数据存放在一起的策略以减 少对磁盘的随机访问。也就是说，它们是以空间换时间。而在m m d b 系统中， 减少对内存的耗用量是关键问题，所以b 树和b + 树均不适用于内存数据库系统 3 0 1 o t 树是t o b i n j l e h m a n 和m i c h e a l j c a r e y 在19 8 6 年提出的一种用于内存数 据库的有序数据索引机制。它是在一个节点中存放多元素的平衡二叉树。既然t 树是a v l 树，它就保留有a v l 树上二叉搜索特性，查询时问复杂度为o ( 1 0 9 2 n ) 。 又由于t 树在一个点中存放多个元素，因此它具有b 树的优良存储和修改性能 p 。t 树还具有下列优点： 它在节点中有序存放元素，混合操作中体现出优良性能；故它在由插入，删 除，查询构成的混合操作中体现了优良的性能； 内存的耗用量相对较少； 可以方便地扩充和缩减； 可以用较少的工作量处理重复键值的记录。 但在数据库运行过程中，频繁的新增和删除操作将引起t 树不断进行节点 分裂合并和平衡旋转，这成为t 树的主要性能歹i ：销。但树的平衡旋转频度较a v l 树要小很多。t 树已被多个系统所采包括i b ma l m a d e n 研究中心s t a r b u r s t 系统 的主存关系管理器和a t & t 贝尔实验室的d a l i 系统，己成为内存数据库的一种 最主要的索引机制。 为适应实时应用程序的要求，k o n gr i mc h o i ，k y u n gc h a n gk i m y 于1 9 9 6 年提出了t 半树。t 丰树是一种在内存数据库管理系统( m m d b m s ) 中实现对数据的 快速访问且节约内存空间的索引机制。 由于每个t 奉树节点具有指向后继节点的指针，所以在进行范围查询时可以 利用该指针直接定位到后继节点而不用对树进行遍历1 2 0 1 ，从而使范围奄询速度 4 硕：上学位论文第一章绪论 大为提高。 为减少t 树中平衡旋转的次数，刘红君等提出了一种新索引机制t - t a i l 树【2 l l 。 t - t a i l 树允许当节点上溢时在其后接一个尾节点，存放溢出的元素。而当节点下 溢时，可移动尾节点中的元素进行补充。这样，通过延迟平衡旋转时机，减少了 平衡转次数，从而提高了数据库的修改性能。 为适应实时数据库系统的可预见性和限时性要求，c h a n h or y u ，e u n m is o n g 等提出了一种混合索引机制即h y b r i d h t 。该机制将哈希结构快速查询和树结构 对数据进行有序组织的优点相融合，显著提高了查询效率，并将最坏情况下的执 行时间限定在指定的界限内【2 列。 实时数据库系统数据索引机制今后主要将有以下几个研究方向【3 2 】： ( 1 ) 实时性 内存数据库的某些应用具有很强的实时性【3 3 】，因此要求内存数据库具备非 常高的数据处理速率，传统的索引机制不能满足这种实时应用的需要。因此，很 多国内外学者在进行这方面的研究，并取得了一定的成绩【3 4 1 。 ( 2 ) 处理复杂数据能力 内存数据库经常需要对高度庞杂的数据进行管理。一个理想的内存数据库应 该能处理各种各样庞杂的数据，而目前的大部分索引机制不能满足这种需要【3 5 。 ( 3 ) 存储空间利用率 内存数据库系统中很多应用场合中，对存储空问是否满足应用的需要成为了 需要解决的首要问题。国内外的很多学者进行了这方面的研究和探索，提出了几 种比传统的索引机制具有更高的空间利用率的索引机制，例如矿树1 36 。，溢出技 术刚等。 1 3 本文的主要内容 本文研究的组念实时数据库系统作为项目“深圳赛为系统集成平台”的子部 分，旨在对集成系统中各现场数据进行实时采集、加工、存储和更新、并对这些 实时数据分类组织实现检索和维护等数掘管理： 作，完成数据处理和数据管理任 务，以供其它服务使用。该实时数据库是“深圳赛为系统集成平台”的中枢部分。 结合该实时数掘库，以实时数据库的索引技术为研究核心，本文将以下几点 作为主要的研究内容： ( 1 ) 组念实时数据库的体系结构以及数据组织方式； ( 2 ) 一种改进索引h t 木机制的实现； ( 3 ) 改进的索引机制h t 幸的性能分析 ( 4 ) h t 木索引与传统的混合索引机制h y b r i d h t 的性能对比 硕十学位论文第一章绪论 各章节安排如下： 第二章首先概要介绍了该实时数据库的总体结构、各模块功能，然后介绍了 它的数据组织，这部分是设计系统索引的基础。 第三章分析了传统数据库系统中的索引技术，并重点分析了与本系统索引设 计相关的几种传统索引技术，c b hh a s h ，t 树，t 术树等，分析这几种传统数据 库索引的优点，缺点。 第四章对本实时数据库采用的索引技术的具体实现过程，并对改进的索引的 算法做了详细的介绍，分析了h t 木的时间性能与空问性能。索引不仅是一种高 效的查询于段和访问方法，而且能影响系统中相关模块的执行性能。 第五章是对改进的h t 木索引与传统的h y b i r d h t 索引的性能对比测试，通 过测试说明了h t 丰的优异时空性能，并进行了实际的应用性能测试。 最后是对全篇的总结和展望。 6 硕+ 学位论文第二章纽态实时数据库的体系结构 第二章组态实时数据库的体系结构 本文涉及的组态实时数据库系统是实时数据库与内存数据库系统的无缝集 成，因此本章将对实时数据库体系结构与内存数据库数据组织特点做一个基本的 介绍。 2 1 实时数据库的体系结构 一个严格的实时数据库管理系统( r t d b m s ) 也是一个数据库管理系统 ( d b m s ) ，所以，它也具有一般d b m s 的基本功能【3 8 】： 永久数掘管理包括数据库的定义、存储、维护等。 有效的数据存取各种数据操作、查询处理、存取方法、完整性检查。 事务管理事务的概念、调度与并发控制、执行管理。 存取控制安全性检验。 数据库的可靠性恢复机制。 但传统的d b m s 的设计目标是维护数据的绝对正确性、保证系统的低代价、 提供友好的用户接口1 3 9 。这种数据库系统对传统的商务和事务型应用是有效的、 成功的，然而，它不适合实时应用，这关键在于它不考虑与数据及事务相联的定 时限制，其系统的性能指标是吞吐量和平均响应时问，而不是数据及事务相联的 定时限制，调度与处理决策根本不管各种实时特性。 与之相反，r t d b m s 的设计目标首先是对事务定时限制的满足，其基本原 则是： 宁要部分正确而及时的信息，也不要绝对正确但过时的信息。系统性能指标 是满足定时限制的事务的比率，它要求必须确保硬实时事务的截止期，必要时宁 肯牺牲数据的准确性与一致性。软实时事务满足截止期的比率相对较高，但要 1 0 0 满足截止期很难或几乎不可能。因此，除了上述一般d b m s 的功能外，一 个r t d b m s 还具有以下功能特性【4 l j ： 数据库状态的最新性即尽可能地保持数据库的状态为不断变化的现实世界 当前最真实状态的映像。 数据值的时问一致性即确保事务读取的数据是时间一致的。 事务处理的”识时m | 生即确保市务的及时处理，使其定时限制尤其足执行的截 止期得以满足。 从系统的组成结构来看，r t d b m s 与传统d b m s 没有什么大的区别。图2 1 给出了它的丰要功能部件及其组成。 7 硕十学位论文 第二章组态实时数据库的体系结构 图2 1 实时数据库的体系结构 在组态软件中，实时数据库的功能和要求又有其不同的特点【4 2 】： 实时数据库管理系统首先是能够对实时数据库中的点信息进行配置，描述数 据库中各种数据点的特征，属性，起到数据字典的功能，因此它需要存储在磁盘 中，以便下次启动项目时，不需要重新配置。这就是实时数据库的组态功能，它 是实时数据库运行系统的基础。实时数据库运行系统的基本功能就是根据组态数 据库的组态信息，构造实时内存数据库，事件库，主动规则库，优先级库，历史 数据库及其缓冲区，并根据事务优先级，创建事务处理线程，完成事务处理，且 给外部应用提供访问接1 2 1 1 4 3 1 。这些实时组件的构造，其同的足为了构造一种系 统机制，在该机制的驱动下，尽可能的满足其作为实时数据库的特点，数据库状 态最新，保障时旺l j 一致性和识时的及时的事务处理等。 实时数据库管理系统的运行分为组态状态和运行状态。其中组态状态和传统 数据库的设计状念类似，用于实时数据库组态丌发阶段，不考虑实时性问题；运 行状态是实时数据库系统的主要状态，它不同于传统数据库的执行模式，是一种 基于优先级的事务执行模式。一旦系统进入实时运行模式，系统就根据事先定义 的事务优先级进行执行，不能动态增减。系统如需要进行修改，必须切换到组态 模式进行处理。 因此监控组态软件的实时数据库系统分为以下几个部分【删： 组态数据库( 数据字典) ，组态系统。 硕十学位论文 第二章组态实时数据库的体系结构 事件库 主动规则库，及其规则编辑系统。 优先级库 历史数据库记录实时数据，数据压缩，以及冗余备份。 内存实时数据库， 实时运行系统： 1 、组态数据库 由于其主要用于系统罩项目工程的特殊配置，记录项目中的设备配置情况， 数据点的属性，时间相关性等，考虑到充分利用操作系统的功能和现有成熟技术 的廉价性，采用传统的关系数据库，用于记录组态信息，以便构造实时数据库系 统。传统的关系数据库现在发展的比较成熟，各个公司都开发出相应的数据库系 统比如o r a c l e ，s q l s e r v e r ，a c c e s s ，f o x p r o 等，为了方便异种数据库的互 联，各数据库系统都对统一的数据库访问接口提供了支持，比如 o d b c 。d a o ，a d o 等【4 5 】，a d o 是目前在w i n d o w s 环境中比较流行的客户端数据 库编程技术。a d o 是建立在o l ed b 底层技术之上的高级编程接口，因而它兼 具有强大的数据处理功能( 处理各种不同类型的数据源、分布式的数据处理等等) 和极其简单、易用的编程接口，因而得到了广泛的应用。而且按微软公司的意图， o l ed b 和a d o 将逐步取代o d b c 和d a o ，在现实上，所有的数据源都可以 通过a d o 来访问。 2 、事件库 事件从概念的语义上，可以看成是一种突发的紧急的，需要立刻处理的事情， 有点类似于计算机系统罩的中断【4 6 1 。它可以看作主动机制的一部分，它导 致系统停止现在进行的工作，并保存当前的状态，对突发事情进行处理，处理完 毕后，再调出保存的状态，继续原来的任务。在实时数据库系统罩加入事件库， 目的在于处理系统中出现的未可预知的事件，使得最重要的事情得以及时处理。 ( 包括数字量报警，模拟量报警，采样周期到，历史缓冲区满等事件，以触发相 应的事务) 3 、主动规则库，及其规则编辑系统。 事件和状态评测，正足主动规则得体现，对于复杂得情形，某种事务活动有 可能与多个数据状态相关，必须多个数据状态满足一定条件，事务活动需要触发 执行，因此主动舰则库功能如下【4 7 】： ( 1 ) 用户可以显式地定义想要监丰见的情形( 事件与条件) ； ( 2 ) 系统自动探测与评价情形的出现； ( 3 ) 一旦说明的情形出现，则触发执行相应的活动。 9 硕十学位论文第一二章组态实时数据库的体系结构 主动机制规则的编辑，是系统组态得一部分。在运行状态下，也需要载入内 存中以提高运行速度，系统线程周期性扫描该规则库，同时触发相应的事务。 2 、优先级库 其功能在于评测实时数据库系统数据的优先级状态，为事务调度提供依据。 该优先级与数据点的实时特性和现在的时间息息相关，为了满足系统的时间一致 性，和定时限制，动态调整优先级，使最需要更新的数据获得系统资源。从而保 证实时性。 3 、历史数据库记录实时数据，数据压缩，以及冗余备份。 在监控组态系统中，有些数据是需要以时间作为横坐标进行历史存储的，为 系统的将来决策提供历史依据，但是历史数据的存储所需要消耗磁盘i 0 ，而磁 盘l d o 又是系统速度的瓶颈，大规模，频繁的磁盘调度不仅减慢系统的运行，而 且也降低磁盘的使用寿命，甚至造成系统瘫痪破坏。因此历史数据的转储机制也 相当重要，为了不丢失历史数据，又减轻磁盘的i o 重负，引入历史数据的缓冲 技术，缓冲区满，才将数据转储到磁盘一l ，缓冲区的大小，可以根据系统可用内 存和历史数据的采样周期而定。即使如此，我们又会看到新的问题，历史数据的 数据量是很大的，而磁盘的容量有限，怎样才能保证系统不会因磁盘容限而导致 系统瘫痪。一个是采用数据压缩技术，尽可能使磁盘能存储更大的数据量。再就 是，当磁盘容量到达危险容量值时，作出报警，要求将历史数据转储到别的备份 磁盘。二者结合起来就能保证历史数据的正常转储。 1 0 贞；、甜- 沧文第二章组态实时数据库的体系结构 图2 2 组态实时数据库体系结构图 4 内存实时数据库4 8 1 ，包含对内存数据库的访问接口，数据库索引，历史 数捌缓冲区，内存实时数据的时间戳，以及实时数据本身的各种属性，是系统交 住的核心区，系统驱动运行的数据来源。 5 、实时运行系统：利用w i n d o w s 多线程机制，再多线程内完成事件管理， 实时事务优先级分派，实时调度算法( 价值函数评估优先级) ，实时并发控制策 略，历史数据缓冲转储以及主动机制等功能。 其体系结构如上图2 2 所示： 组念实时数据库系统执行模型 a ) 系统的组念阶段： 1 ) 通过人机界面的交互，用户可以对组态数据库的组态信息，比如点号， 点名，点描述，点类型，读写模式，实时模式( 硬实时，软实时，固实时等) ， 物王q ! 连接描述，物理设备类型，是否报警，报警信息，报警时值，报警上限，报 警一卜限，工程单位，优先级因子，采样周期，是否存盘等点记录信息进行查询， 更新，删除，插入等数据操纵，为实时数据库的运行提供基础。 2 ) 主动规则库用于描述各个设备点或变量之间的关系，比如某些输入的某 种变化，导致某个输出的变化。 3 ) 界面系统的组态足将图像的变化反应设备点或内存变量的变化建立映射 关系。 b ) 实时数据库的启动 1 ) 系统数据结构初始化。 2 ) 内存数据库管理完成内存数据初装，包括对数据字典内容的初装，主动 规则库的初装，优先级的初始分配。对整个实时数据库初始扫描一遍，建立以点 名或点号位关键字的索引，对于有存盘需求的数据，为其分配历史数据缓冲区， 并建立相应的历史数据库文件。 3 ) 启动事务管理、优先级库扫描，事件库扫描，主动规则库扫描等核心模 块，使系统处于动态运转中。 c ) 实时数据库的运行 1 ) 事件库扫描线程，扫描事件库，有事件触发，则优先执行相应事务。 2 ) 优先级库扫描线程，扫描优先级库，根据点的时标信息，以及本身的优 先级颁殴，扫描周期，实时类型等因子，计算评估优先级评价函数，得出现时的 优先级。 3 ) 事务调度管理线程，处理事务的并发控制，调度事务的执行线程。 4 ) 事务执行线程，对于满足事务执行条件，即优先级水平在需执行范网内， 硕士学位论文第二章组态实时数据库的体系结构 则执行事务。 5 ) 主动规则库扫描线程，进行主动规则情形评价，符合条件的，触发相应 的事务。 6 ) 界面扫描线程，将界面子系统的动态变化与相联系的变量对应起来，多 个线程拥有不同的优先级，事务执行线程是实时数据库的主要工作所在，优先级 设为最高，其余都可以设为较低的优先级。所有线程的执行，又受w i n d o w s 的 线程调度管理器管理。 2 2 内存数据库的数据组织 内存数据库的数据放在主存，可直接被c p u 处理，内存数据库数据组织结 构设计的目标包括加速数据操作的执行速度和提升有限内存空间的利用率。 1 区段式【5 0 j 区段式结构中，内存空问首先被划分为若干“分区”，每一个分区存储一个 关系。一个区由若干“段”组成，段是内存中固定长度的若干区域，相当于页的 概念，但比页大。段是内外存i o 的基本单位，也是内存空问分配和内存数据恢 复的基本单位。区段式组织结构如图2 3 ： ；瓣 澎陆：矗l 备毫l? 一。， l 翌竺5 鼍量婴jt 碧芬i 兢繁掌j ，一。， | 移弑l ；7 ； 一i 童苫告亳- i 结缝籀磊e 缓 一 - | 段t ll 。 ，“ 、 0r 1e1 r 1 ： q 一羔麴j ? 蕊碜万弋：一x 一 飞。 图2 3 区段式结构 一个段中的一个数据记录就是一个关系元组，每个记录拥有唯一标识符 r i d ( r e c o r di d e n t i f i e r ) ，r i d 为三元组 ，其中p 、s 、l 分别为分区号、 段号、段内记录槽号，记录槽( r e c o r ds l o t ) 包含了对应记录的长度和记录首地址。 通过r i d 查找分区表和段表内容即可找到对应的记录槽，再按照槽中地址和长 度定位到具体存取的记录数据。 2 影了内存式1 5 0 j 硕上学位论文 第二章组态实时数据库的体系结构 影子内存式结构中，数据空间被划分为两部分：主拷贝p d b ( p r i m a r yd a t a b a s e ) 和影子拷贝s m ( s h a d o wm e m o r y ) 。事务操作期间，对p d b 和s m 分别产生对应 的地址，且总是首先对s m 试探，若不成功，再对p d b 操作。所有操作在s m 中进行，并且记录活动同志。 当事务提交时将其在s m 中的“后映像”拷贝到p d b 中【5 引，影子内存式组 织结构如图2 4 所示： h 马 b 囝 图2 4 影子内存式组织结构 使用影子内存的主要优点是减少目志缓冲，先对s m 操作成功后再刷新p d b 的方式省去事务失败时的u n d o 操作，只要清除相应影子内存中数据，p d b 中 数据没有影响。影子内存结构更多的是作为内存数据库的一种事务并发及恢复策 略的实现【5 0 】。 硕+ 学位论文第三章传统索引机制分析 第三章传统索引机制分析 本文在h y b r i d - - t h 索引机制的基础上提出了一种改进索引机制h t 枣索引， h y b r i d h t 是c b h 和t 树的混合，而改进索引机制h t 木索引涉及哈希表，t 木树。 因此本章将对c b h ，t 树，t 枣树，h y b r i d t h 这几种传统索引机制的原理，基本 操作算法进行较为详细的阐述。 3 1h a s h 索引 h a s h 表提供了通过关键字来定位表中记录的最快方法。根据h a s h 表的大小 和h a s h 函数的性能，需要一个或多个探针来定位记录。当所有的查询对记录字 段使用“等值比较”时，h a s h 表的访问性能是最好的。对于内存数据库，h a s h 不但仍然是一种有效的数据组织技术，而且得到很大的发展，形成了多种形式的 h a s h 索引，这里介绍几种典型的形式【b l ： ( 1 ) 桶散布h a s h 桶散布h a s h 如图3 1 所示，对每一个文件有一个h a s h 函数，它将该文件 的关键字值空间映射到一个“桶散布表”( b u c k e ts c a t t e r t a b l e ) 。每一个桶由 一块或者少数几块链接组成，链头就是“桶散布表”中的一项。每一这样的链实 际就足h a s h “碰撞”的一个同义链。 变换 关键字 l h a s h 函数 o 桶敞柿农桶 图3 - 1 桶散布h a s h 结构图 这种方式的h a s h 组织比较适合静态索引，因为要事先较准确的选定一桶数， 即桶散却表的大小( 项数) ，过大会浪费空间，过小则使每个桶的链变长而降低 存取性能。理想的是每桶一块，故桶散布表的大小是文件的记录数除以组块因子 而得的商。这种方法的另缺点是额外需要b ( 桶数) + n b ( 块数) 个指针的存储。 ( 2 ) 线性扩展h a s h 线性扩展它类似于可扩展h a s h ，但又具有桶敝行h a s h 的特色，其组织结构 1 4 顺 乞：l ? i 论文第三章传统索引机制分析 为图3 2 所示，它使用一个可与扩展h a s h 一样目录，但数据块组织却具有桶散 ji t a s h 式的特色，即有拉链的块( 或桶) ，不过这罩链的语义与桶散布h a s h 的 一i 1 样它不是“碰撞”的“同义链”，而且这里块的组成也仅是为了提高空间 的利用牢，它本来是可以单个数据记录的拉链的。对于数据块( 节点) ，这里没 有像口了扩展h a s h 那样溢出概念，每当一块已满而又有新数据要插入时，只要向 内存缓冲区申请一块并加入相应链即可，故也不存在可扩展h a s h 中那样的“块 分裂“操作。然而这里也有目录分裂，只是：( 1 ) 它不是由于块分裂而引起的， 而地基于链的定长( 桶的大小) ；( 2 ) 分裂时目录增长不是翻倍，而是线性的。 图3 - 2 线性可扩展h a s h 结构图 ( 3 ) 多目录h a s h 另一种h a s h 式索引结构是多目录h a s h ( m d h ) 。如图3 3 所示，它首先将 关键字映射成h a s h 地址，然后划分h a s h 地址成荫部分，分别用来定位和检索 响应目录，这里目录的个数是阎定的。每一目录以和叶大小为l 的可扩展h a s h 目录增长一样的方法增长，每个目录项最多指向一个数据记录。 变换 l 。9 2 n b i 5 图3 - 3 多目录h a s h 的结构图 地址 硕士学位论文 第二章传统索引机制分析 这种方法性能比可扩展h a s h 好，因为它的目录项直接指向数据记录。然而， 若可扩展h a s h 的叶节点大小也选择为l ，则其目录会急速增长。可以证明，m d h 总目录大小的期望值随目录增加而减少到某一值