（计算机应用技术专业论文）实时内存数据库数据组织结构优化策略研究.pdf

中文摘要 随着自动化程度和系统集成程度的提高，实时内1 竽数据库已经成为企业软件系统中 的核心系统，而且也成为生产过程实时监控、生产信息实时管理与决策支持的基础，是 进行数据分析与优化控制的前提。实时内存数据库强调对数据处理的实时性和正确性， 其设计目标是提高c p u 和内存的利用率，而实时内存数据库的数据组织结构是实现该 目标的基础。 本文主要对实时内存数据库的数据组织结构进行研究，根据数据库总体性能要求与 功能特性，提出了一种基于红黑树作为实时内存数据库的数据组织结构优化解决方案。 首先，深入讨论了实时内存数据库的概念和相关技术。其次，分析了当前实时内存数据 库的数据组织结构，对目f j 以b 树、t 树、a v l 树作为其数据组织结构的方案进行了深 入探讨和对比分析。第三，着重研究了基于红黑树的实时内存数据库数据组织结构及其 查询优化方案。第四，建立了基于红黑树结构的实时内存数据库模型，并且基于c + + 语 言进行了实现。最后，对基于红黑树结构的实时内存数据库模型与基于a v l 树结构的 实时内存数据库模型进行了测试比较实验。最终的测试结果表明，红黑树的奁找和存储 性能仪次于a v l 树，但是其存取性能明显高于a v l 树结构，在节省空间和存取效率等 方面，采用红黑树作为实时内存数据库的数据组织结构足一种可行的优化解决方案。 关键词：实时数据库；内存数据库；红黑树；查询优化 l 一 a b s t r a c t a l o n gw i t ht h ei m p r o v i n go ft h ea u t o m a t i o na n di n t e g r a t i o n ，r e a l t i m e m e m o r yd a t a b a s ew h i c hh a sb e c o m et h ec o r eo fe n t e r p r i s es o f t w a r es y s t e m s ， a n da ls ot h ef o u n d a t i o no fr e a l t i m em o n i t o r i n ga n dm a n a g i n gt h ep r o d u c t i o n i n f o r m a t i o nd u r i n gt h ep r o d u c t i o np r o c e s s ，i st h ep r e m i s eo fa n a l y z i n gt h ed a t a a n do p t i m i z i n gt h ec o n f o r m i t y r e a l t i m em e m o r yd a t a b a s e e m p h a s i z e s r e a l t i m ea n da c c u r a c yo np r o c e s s i n gd a t a e n h a n c i n gt h eu t i l i z a t i o no fc p ua n d m e m o r ya r et h et o t a ld e s i g n i n gg o a lo ft h er e a l - t i m em e m o r yd a t a b a s e ，a n d t h ed a t ao r g a n i z a t i o ns t r u c t u r ei st h ef o u n d a t i o nt or e a l i z et h i sg o a l t h i sp a p e rf o c u s e so nt h eo r g a n i z a t i o n a ls t r u c t u r eo fr e a l t i m em e m o r y d a t a b a s e a c c o r d i n gt ot h eo v e r a l l s y s t e mp e r f o r m a n c er e q u i r e m e n t sa n di t s c h a r a c t e r i s t i co ff u n c t i o n s ，t h ep a p e rp r o p o s e st h er e d b l a c kt r e et ot h ed a t a o r g a n i z a t i o ns t r u c t u r eo ft h er e a l t i m em e m o r yd a t a b a s e f i r s t l y , t h ec o n c e p t a n dr e l a t e dt e c h n o l o g i e so fr e a l t i m ed a t a b a s em e m o r yi sd i s c u s s e d s e c o n d l y , t h i sp a p e rr e s e a r c h e st h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h ed a t as t r u c t u r eo n t o d a y sr e a l - t i m em e m o r yd a t a b a s e ，a n da n a l y z e st h ett r e e ，bt r e ea n da v l t r e e t h e nr e a l t i m em e m o r yd a t a b a s eb a s e do nt h e s ed a t as t r u c t u r ei s c o m p a r e da n ds t u d i e d t h et h i r d ，t h er e a l t i m em e m o r yd a t a b a s eb a s e d o nt h e r e d b l a c kt r e ea n dt h eq u e r y i n go p t i m i z a t i o np r o g r a ma r em a i n l yr e s e a r c h e d t h ef o u r t h ，a c c o r d i n gt ot h er e s e a r c h e sa b o v e ，t h ep a p e re s t a b l i s h e st h em o d e lo f r e a l - t i m em e m o r ys t r u c t u r eb a s e do nr e d - b l a c kt r e ea n du s e sc + + l a n g u a g et o r e a l i z e f i n a l l y , t h et e s ti sc o m p l e t e dt oc o m p a r et h em o d e lo ft h er e a l t i m e m e m o r yd a t a b a s eb a s e do nr e d - b l a c kt r e ew i t ht h em o d e lo ft h er e a l - - t i m e m e m o r yd a t a b a s eb a s e do na v l t r e es t r u c t u r e t h er e s u l to f t h et e s ts h o w st h a t t h er e d b l a c kt r e e sq u e r y i n ga n ds t o r a g ep e r f o r m a n c ei sf o l l o w i n gt h ea v lt r e e b u tt h ea c c e s s i n gp e r f o r m a n c eo u t s h i n e st h ea v lt r e ee v e nm o r e t h e r e f o r e ， c o n s i d e r i n gt h ea c c e s s i n ga n ds t o r a g ep e r f o r m a n c e ，u s i n gt h er e d b l a c kt r e e t o t h ed a t ao r g a n i z a t i o ns t r u c t u r eo ft h er e a l t i m em e m o r yd a t a b a s ei sav i a b l e o p t i m i z a t i o ns o l u t i o n r e a l - t i m ed a t a b a s e ；m e m o r yd a t a b a s e ；r e d - b l a c kt r e e ；q u e r y i n g n l v 目录 第一章引言1 1 1 研究背景1 1 2 国内外研究和应用现状3 1 3 论文研究的组织结构4 第二章实时内存数据库关键技术介绍5 2 1 实时数据库的特征5 2 2 内存数据库6 2 3 实时内存数据库的关键问题6 2 3 1 实时内存数据库物理存储结构6 2 3 2 实时内存数据库事务处理8 2 3 3 实时内存数据库的数据管理1 l 2 3 4 实时内存数据库的恢复技术1 3 第三章实时内存数据库常用数据组织结构1 7 3 1b 树1 7 3 2a v l 树1 8 3 3t 树1 9 第四章基于红黑树的实时内存数据库数据组织结构分析2 l 4 1 红黑树2 1 4 2 红黑树的操作算法2 2 4 2 1 红黑树的旋转操作2 2 4 2 2 红黑树的插入操作2 2 4 2 3 红黑树的删除操作2 5 4 3 红黑树性能分析2 9 4 4 红黑树、b 树、平衡二叉树比较3 0 4 5 基于红黑树数据组织结构数据的查询优化3 1 4 5 1 实时内存数据库的查询处理过程3 1 4 5 2 实时内存数据库的逻辑优化3 3 4 5 3 数据查询过程3 4 第五章基于红黑树数据组织结构的实时内存数据库模犁的设计实现3 7 5 1 模型的提出3 7 v 5 2 模型设计和实现3 7 5 2 1 模型设计3 7 5 2 2 模型实现3 9 第六章基于红黑树数据组织结构的实时内存数据库模型的测试4 7 6 1 测试描述4 7 6 2 测试过程4 7 6 3 测试结果5 4 6 4 测试结论5 5 第七章总结5 7 参考文献5 9 致谢6 1 攻读硕士学位期间发表的学术论文目录6 3 v l 第一章引吉 第一章引言 本章首先概述实时内存数据库技术的研究背景，其次阐明实时内存数据库当i j 订国内 外研究和应用现状、最后给出论文的组织结构。 1 1 研究背景 数据库技术是计算机科学技术中发展最快的领域之一，也是应用最广的技术之一， 在当今的信息社会中，它几乎无所不在。作为当今信息时代、网络时代应用基石的数据 库技术可谓是无处不在。历经3 0 余年，按照数据模型的进展，数据库技术可以相应的 分为三个发展阶段，即第一代的网状、层次数据库系统，第二代的关系数据库系统，发 展到新一代的数据库系统。面向对象型数据库系统到对象关系型数据库系统的技术已相 当成熟，各大数据库公司如i b m ，o r a c l e ，s y b a s e 和i n f o r m i x 等已能提供全系列的数 据库产品，从数据库管理系统、工具平台到应用软件系统无所不包，它们能很好地满足 客户的应用需求，提供全套的应用解决方案和周到的服务【lj 。 现代计算机硬件技术发展非常迅速，尤其是处理器、存储设备等在近几年都取得了 巨大的进展。例如，现代处理器的多线索、多级缓存、多核技术等的实现在很大程度上 提高了处理器自身的计算能力。再如存储设备方面，内存价格越来越低，内存容量不断 增大，而且还出现了采用新技术( 如微机电系统m e m s ) 研制的存储设备。与现有的主 要存储设备一磁盘相比，新一代的存储设备存储密度更大、访问速度更快，存取方式也 发生了巨大的变化，例如可以并行化的存取数据。 这些新技术的出现为数据库技术的发展带来了新的机遇和挑战，数据库研究者应该 充分的利用硬件的新特性和新技术来促进数据库系统的发展。例如，以前数据库在性能 优化方面的研究，主要集中在如何减少磁盘i o ，很少考虑如何高效地利用硬件的特性 来提高数据库性能。所以存储技术的进步带来的查询优化技术已经不是基于磁盘的i o 开销。随着内存容量的不断增大和6 4 位处理器的实现，可以把数据库的数据全部放在 内存中进行操作。在这种情况下，磁盛的i o 将不再是影响数据库性能的唯一瓶颈，还 要考虑内存和c p u 之间的数据交换的代价，或者说是内存的访问代价。 实时内存数据库这个课题足在现代数据库技术从传统应用向实时应用扩展的背景下 提出的，数据库的发展经历了三个主要阶段【9 j 。1 9 6 9 年美国i b m 公训研制的层次模型 数据库管理系统i m s 和美国c o d a s y l 组织的数据库工作小组发表的d b t g 报告是第 一代数据库技术的代表。1 9 7 0 年i b m 研究员e f c o d e 发表的关系数据库的论文标志着 关系数据库( r t d ) 研究的丌始，是第二代数据库的标志。白此以后，关系数据库的理论 实b , i - p , j 存数据库数据组织结构优化策略研究 研究逐渐成熟，其技术开发也随之得到了飞速发展，并在情报检索、企业管理等方面得 到了广泛的应用，成为传统数据库的典型代表。 然而，传统数据库仍然存在着不足。在实际应用的要求下，涌现了一大批的新型更具有 使用价值的数据库，如模糊数据库、时态数据库、空间数据库、主动数据库、工程数据 库和实时数据库、内存数据库等都是其中的典型代表。我们研究的实时内存数据库的理 论与技术正是当前数据库研究领域的热点。 实时数据库是指其处理的事务和数据都具有定时特性或显式定时限制的数据库系 统，系统的正确性不仅依赖与逻辑结果而且还依赖于逻辑结果产生的时间。近年来， r t d b 受到极大的关注。数据库研究工作者关心实时系统中实时数据管理问题；实时系 统研究工作者侧重与为r t d b 提供时阳j 驱动调度和资源分配的算法研究。然而，r t d b 不是两者的概念、机构、工具等的简单集成，需要对如下问题进行综合研究与决策：事 务的截止时间的软硬性；事务的优先级分派、调度和并发控制的协议预算法；i o 调度、 恢复、通信的协议预算法；查询处理算法；数据和事务特性的语义及其与一致性、正确 性的关系；数据与数据的结构与组织等。 实时内存数据库的传统数据组织结构和基于磁盘系统的组织结构有很大不同。实时 内存数据库的数据全部放在内存中，它的目标是减少整体的计算时间同时尽可能少地占 用内存。 目前常用的实时内存数据库数据组织结构方案都存在着一些缺点，数组被用来作为 组织结构的优点是他占用的空间最少，查询速度快，关键是结构简单。数组最大的缺点 就是当增加数据时，数据移动比较麻烦，因此在一个动态换件下是不可用的。链表结构 类似数组结构很简单，但是链表的插入、删除、检索效率太慢。b + 树方式在内存中保存 所有的数据在叶子上并非优点，它太浪费空间。而用a v l 树作为组织结构，在一定的 程度上增加了数据查询的效率，但是它是一个二叉树，最大的缺点是它的数据存取效率 太低。因为为了保持a v l 树的平衡性，a v l 树可能要频繁的对节点进行旋转操作，甚 至有的时候需旋转的次数很多。红黑树是从平衡二叉树改进发展而来的，所以它存储数 据的树层次降低，进而增加了数据的查询效率，更重要的是红黑树相比a v l 树，平衡 规则不是很严格，所以在平衡一棵红黑树的时候，节点的旋转次数很低，最多不超过三 次，所以它的删除、增加、修改资料所需要的时间很少。红黑树有如下特殊的性质【2 j ： 1 所有的结点都被着色为红色或者是黑色。2 每一个叶子结点都是空结点，并且被染为黑 色。3 如果父结点是红色的，那么两个子结点都是黑色的。4 结点到其子孙结点的每条 简单路径上都包含相同数目的黑色结点。5 根结点永远是黑色的。利用红黑树的结构实 2 第一章引言 现对实时内存数据库的内存数据的组织，能够大大缩短检索数据库需要的时间，减少存 储空问。论文拟采用红黑树结构作为实时内存数据库的组织结构。这对于保证实时内存 数据库的定时性有着重要的意义。 另外，现有的传统查询算法不能适应实时内存数据库的查询。传统的查询优化策略 大部分是基于时问代价的，有很多因素对时间有影响。而实时内存数据库要求尽量减少 查询所占用的内存空i 日j ，并提高查询速度。 近年来在工业控制领域中，随着自动化程度和系统集成程度的提高，实时内存数据 库已经成为企业软件系统中的核心系统。它已经成为生产过程实时监控、生产信息实时 管理与决策支持的基础，是进行数据分析与优化控制的前提l l 】。采用一种合适的实时内 存数据库数据组织方法并基于此组织方案进行查询算法优化对提高实时内存数据库的 运行速度有很大的帮助，因此对于实时内存数据库的组织结构及查询算法的研究有着 定的理论和实际意义。 1 2 国内外研究和应用现状 2 0 世纪8 0 年代以来，实时数据库引起了越来越多数据库研究者的兴趣，时至今日， 国外工程类实时数据库的商用产品包括美国的a s e p n t e c h 公司的i n f o p l 2 s u l 、h o n e y w e l l 公司的u i n f o m r a c e n 。理论界认可的实时数据库有z i p r t d b m s 列和m a r t i nm a r i e t t a 公司 的e a g l es p e e d r t d b m s l 4 1 。随后十多年来，各国的学者就实时数据库系统的设计和实现 技术、崩溃恢复、并发控制、事务调度等方面作了一些研究：针对内存数据库中存储结 构的实现机制提出了采用一种动念存储结构机制来改变内存数据库中的表结构以适应 外存表结构的变化【5 1 。为满足现有实时数据库快速查找和节省空间提出一种基于网格+ t 树的索引结构【6 1 。依照内存数据库的特征，提出一种基于t 树的实时内存数据库组织结 构【7 1 。目前大多数实时内存数据库采用t 树作为其数据组织结构【8 】，因为t 树相比以往 内存数据库使用的b 树，存储性能更高。但是t 树的存取性能要低于a v l 树【lj 。如果 以数据库的存取性能为目标，采用a v l 树更优于t 树。 目前实时内存数据库组织优化方面研究热点主要集中在提出一种适合实时内存数 据库要求的数据组织方法，从而提高实时内存数据库的及时性、可预见性、可靠性，改 进数据查询处理算法、查询的执行方法、索引结构等。美国在实时数据库和内存数据库 等领域的研究进行了多年，已达到了一定的理论深度并付渚实践，而且取得了丰硕的成 果，国外一些大公司已针对数组、a v l 树、b 树等组织方案进行了“实时数据库”的开发 与研制，以数据的原型长期在线存储一些特殊用户所有的生产实时数据，用以满足快速 实时内存数据_ 车数据组织结构优化策略研究 高效的数据采集、存储以及对其进行必要的分析处理。 对于实时内存数据库，在数据结构方面有大量的工作要做，什么是有效的目标和技 术需要完全重新评价。在外存数据库中使用的结构不一定再有利，典型地用于程序内的 数据结构也不可能是这里所需要的，因为它们是以小量数据为目标的。同样，我们也不 能通过分别评测索引技术来评价实时内存数据结构，而必须考虑整个内存的存储技术， 包括数据在页面罩的安置，乃至地址的转换方法，地址转换本身就是一种类型的索引结 构。此外，查询处理技术也要考虑，不同的查询处理技术要求不同数据结构，所有这些 的总效果必须研究考察。 1 3 论文研究的组织结构 论文通过参考现有的一些实时内存数据库，从而进行一些有益的研究，利用国内外 的一些研究成果，进行实时内存数据库的组织结构研究。论文主要由六部分组成，第一 部概述了实时内存数据库技术的研究背景与应用现状；第二部分介绍实时内存数据库关 键技术；第三部分对实时内存数据库常用数据组织结构进行讨论；第四部分研究了基于 红黑树的实时内存数据库组织结构及查询处理；第五部分设计和实现基于红黑树的组织 结构的实时内存数据库模型；第六部分对基于红黑树的组织结构的实时内存数据库模型 进行一t i - 能测试；第七章为结论，对全文所作的讨论进行概括和总结。 4 第二章实时内存数据库关键技术介绍 第二章实时内存数据库关键技术介绍 2 1 实时数据库的特征 数据是为实时应用服务的，具备“时间一致性”的特性；事务结构是复杂的，内部 之间相互关联，传统的a c i d 模型已不适用，而且事务执行足彼此“可见”的，要相互依 赖地彼此合作、协同而并发地执行。系统的话确性标准是“正确而及时”，有时“及时 性比一致性更重要”，基于“时间i f 确”与优先级的处理和支持各种相关的“识时 协 议，数据库的不可靠性和不可用性会导致整个实时系统的崩溃。 1 实时数据库的数据对象 实时数据库由映像对象、导出对象和不变对象三大类对象组成i l l 。 映像对象：现实世界对象( r e a lw o r l do b j e c t ，r w o ) 首先通过传感器采样，然后再写 入数据库，这种被写入的数据库对象就称为r w o 的映像对象( i m o ) 。采样时间或有效 时间与一个i m o 相联，称为“采样时标”，自此开始至下一次采样发生的时问就是该i m o 的“外部有效期”或“有效期”。一个i m o 一旦记入数据库，一般就不被更改，而是对 应r w o 在后来时刻的采样值写入数据库作为一新的i m o 。 导出对象( d e r i v e do b j e c t ，d e o ) ：d e o 在一个事务的执行过程中由一组i m o 和其 他数据对象计算而得出。d e o 的有效期由导出它的数据对象的有效期决定。 不变对象( i n v a r i a n to b j e c t ，i v o ) ：一个i v o 就是一个对时间不变的值。若是被看作 一个实时数据，其有效期总是自r t d b s 建立时算起直到“当前”。 2 实时数据的特征 在实时数据库中，数据只在一定时间内是“流行”的，其值随外部环境状态变化而频 繁地改变。所以不仅要考虑数据内部状态的一致性，还必须考虑外部状态与内部状态之 问的一致性，而且并不是每次提供最新的值就是最合适的，还必须考虑它与其他被使用 数据间的“时间一致性”。这些就是r t d b 的数据特征，下面给出下面的相关内容桫j 。 1 数据库的数据对象d 为一个三元组d ： 。其中分量d v 、d 小d e v i 别为d 的当自矿状态或值、观察或采样时标、外部( 绝对) 有效期。 2 数据d 是内部一致的，当且仅当d 。满足所有对其预先定义的完整性和一致性限制。 3 数据d 是内部一致的，当且仅当d 。满足所有对其预先定义的完整性和一致性限制。 4 用来做决策或导出新数据的组数据称为一个相互一致集，每个这样的数据集r 都有一个与之相联的“相有效期”，记为r m 。i 。 5 设r 是一个相互一致集，d r 。d 是相互一致的，当且仪当 实时内存数据库数据组织结构优化策略研究 v d r ( d t p - d t p i 姜r m v i ) 外部一致性用来保证数据是现实世界当前有效的，相：丘一致性则保证了用来决策或导出 新数据的一组数据在公共的有效时问范围内彼此接近地产生的。 6 若一个数据既是外部一致又是相互一致的，则说它是时间一致的。 2 2 内存数据库 关于什么是内存数据库，有过多种不同的说法，如整个数据库常驻内存，对数据的 存耿不需要i o 操作；整个数据库不用常驻内存，但存取数据时，应先进入内存，即数 据库的存取在内存中进行；数据库常驻磁盘，增大缓冲区，在一个事务执行之前，所有 的数据都已经取到内存，经适当的缓冲区管理减少甚至消除i o 。事实上，内存数据库 的定义不能涉及内存的大小、存取数据所需i o 的多少及怎样才留驻内存等这些具体的 实现技术，而只包含数据库永久留驻内存、事务的数据存取只涉及内存等。下面给出了 内存数据库的定义i l l 。 定义l ：设数据库d b ，令d b m ( t ) c d b 为时刻t 数据库在内存中的数据集、t s 为系统 中所有的事务集、a t ( t ) c t s 为时刻t 活动的事务集、d 。( t ) d b 为事务t 在时刻t 所操作的数据集。若在任意时刻t ，均有vt a t ( t ) ，d t ( t ) c _ d b m ( t ) 成立，则称d b 为 一个内存数据库，简称d b m s 。 简单的说，m m d b 就是数据库的“工作版本 ( 也可能是整个数据库) 常驻内存 的数据库，所以它要求较大的内存来存储当前处理的数据。但是它并不要求任何时刻整 个数据库都能存放在内存，而且它还需要外存来存储内存放不下的那些数据，以便用于 恢复备份等，即m m d b 还是要处理i o 。虽然如此，他已经不同于传统的磁盘数据库， 所以有关m m d b 的查询处理、并发控制和恢复等的算法与数据结构都要重新没计。 2 3 实时内存数据库的关键问题 i o 处理是d r d b 系统的“瓶颈”，显然减少i o 时间和提高磁盘空问的利用率是系 统的算法设计目标。而对于r t m m d b ，已不再涉及i o ，在时间和空间矛盾的处理上， 空间是第一位，所以系统的算法设计目标是内存空间和c p u 的高效使用。鉴于此，关 于实时内存数据库的数据组织、事务处理和数据管理、并发控制及恢复技术等方面进行 了大量的研究与讨论。 2 3 1 实时内存数据库物理存储结构 实时内1 竽数据库的物理组织，包括存储结构、索引结构都必须考虑内存卣接存取这 一特征。下面给出了几种适合m m d b 的典型的物理组织方法i l l o 6 第：二章实时内存数据库关键技术介绍 1 影子内存式。内存数据库空问划分成两部分，一部分是m m d b 的主副本p d b ( 主 数据库) ，另一部分为“影子”复制s m ( 影子内存) 。在事务的正常操作期问，每次查询 都产生一个分别对于影子内存和主副本的双地址，且总是先对影子内存试探，若不成功， 再对p d b 操作。所有的更新操作都在影子内存中进行，且都记录在活动日志缓冲区中。 每当一个事务提交时，由它产生的在影子内存中的“后映像”复制到p d b 中。影子内 存式m m d b 的体系结构如图2 1 所示。 a l b 卜 数据席管 影r 王i l ! 系统 内存 卜、一一 p d b s d b 图2 1 影子内存式体系结构 f i g u r e2 1s h a d o wm e m o r ya r c h i t e c t u r e 2 索引式。磁盘数据库有多种索引结构，其代表性的是b 树和b + 树。它也是m m d b 的大型动态索引结构之一，只是在内存中b 树比b 十树更适合，因为b + 树那样高层节点 关键字是叶节点中关键字的重复，叶节点也不含顺序链接指针，所以更省内存。 3 区段式。将存储空间划分成“分区”，每一分区由若干个定长“段”组成。段相 当于“块”，是i 0 、内存空间分配及m m d b 恢复的单位。 每个记录有一个唯一标识符r i d ，它是一个三元组 ，其中p , s ，l 分别为分区号 为分区号、段号、段内的记录槽号。这样由r i d 经分区表和相应段表找到相应记录的槽， 按槽中的地址与长度便可直接存取所要的记录。其实，由于是内存数据库，存取方法返 回的不必是所需记录数据的副本，只需简单地将对应的槽返回即可。 4 h a s h i n g 式。对于m m d b ，h a s h i n g 不但仍然是一种有效的数据组织技术，而且 可构成多种形式的h a s h i n g 组织。这里简要介绍几种h a s h i n g 结构。第一种桶散布h a s h i n g 结构，它就足常规的h a s h i n g 组织。第二种可扩散h a s h i n g ，这种结构的组织是由目录、叶 节点组成的两层结构。目录由一个指明目录深度d 的目录头和2 d 个指针的目录项组成。 深度d 表示取的伪关键字最左的d 来定位目录项。每一目录项是一个指向叶节点的指针。 第三种足线性扩展h a s h i n g ，它是可扩展h a s h i n g 与桶散布h a s h i n g 的结合。其组织结构 足使用一个可扩展h a s h i n g 式的目录和桶散布h a s h i n g 的块拉链，不过这里链的语义不 是“碰撞”的“同义链”，这早块的组成也仅是为了提高空问的利用率。第四种是多目 录h a s h i n g , 色是山h a s h i n g 和索引技术组合的另一种数据组织方法。它是先将关键字映 射成h a s h 地址，然后划分h a s h 地址成两部分，分别用来定位相应目录和检索目录项。 其中目录的个数是同定的。 7 1 包 间要 态在 第二章实时内存数据库关键技术介绍 一定的时问范围内。 行为正确性：一种是通过控制来产生的操作经历，其正确性由可串行化保证；另一 种是在j 下确经历中必须发生的额外操作，它的正确性则要专门丌发。 结构f 确性：它是用来确保相应的“执行依赖性”。例如对嵌套事务结构，设t s 。为 父事务，t s 。为其子事务，则它的结构f 确性表示如下： v t s c t s c ( t s c b d t s p ) 八( t s c a d x t s p ) a ( t s p c d t s c ) v t s c t s 。( b e g i n t s c h t ) _ ( 1 ( ( c o m m i t t s p t b e g i n t s c ) v ( a b o r t t p t b e g i n t c ) ) ) 其中t s 。b d t s 。表示如果子事务先开始，则父事务必须先开始。t s 。a d x t s 。表示若子事务提 交，则父事务必须先提交或者天折。t s 。c d t s 。表示如果父事务夭折，子事务也必须夭折。 实时事务的下确性不仅由内部一致性确定，还有时问一致性。显然传统的“可串行 性 已经不太适用。为了使更多的事务满足串行性定时限制，人们已经开发了一些对经 典的可串行性限制要求很低的正确性准则。 2 优先级分配策略 实时事务的调度和并发控制都是基于事务的优先级进行的，因此，如何分配事务的 优先级是一个重要的问题。实时数据库系统中，已经丌发了许多实时事务的优先级分 配策略，本文只介绍几种典型的分配策略【9 j ： 最早放行最优先e r f ( e a r l i e s tr e l e a s ef i r s t ) ：该策略将最高优先级指派给具有最早“放 行”( r e l e a s e ) 时间的事务。所谓放行时间就是事务可以开始执行的最早时间，与此相联 的有事务到达( a r r i v e ) 时间事务接纳( a d m i s s i o n ) 时间。 截止期最早最优先e d f ( e a r l i e s td e a d l i n ef i r s t ) ：截止期最早的事务的优先级最高。 可达截止期最早最优先( e a r l i e s tf e a s i b l ed e a d l i n ef i r s t ) ：将最高优先级分配给最早达到 截止期的事务。设事务t 的当前时间为t ，e 、r 分别表示事务t 的估算的运行时间和已 经执行的时间。则什( e r ) g ，d 为其截止期。 空余时间最短最优先l s f ( l e a s ts l a c kf i r s t ) ：推迟事务t 的执行而仍然满足其截止期的 可推迟时间量估算。空余时间s 可表示为：t + ( e p ) g 。 价值最高最优先h v f ( h i g h e s tv a l u ef i r s t ) ：每一事务都有一价值函数，其值最大者优先级 最高。其可以表示如下：v ( t ) = c ( w 1 ( t t s ) 一w 2 d + w 3 p - - w 4 s ) ，其中c 、t s 分别为事务 t 的危急度和丌始时间，w i 为加权因子。 价值密度最大最优先g v d f ( g r e a t e s tv a l u ed e n s i t yf i r s t ) ：价值密度函数的定义为：事务 完成时的期望价值与实现这个价值所需计算量的比例，此比例最大者优先级最高。显然， 9 实时内存数据库数据组织结构优化策略研究 对于期望价值一样的事务，该策略偏向实现价值较小者，因为这种实现价值较小者每 单位消耗时间所获得的价值更大。所以这种策略关键足设计这种价值函数。 3 实时事务的并发控制 实时数据库系统对可串行性性质有不同程度的放松，所以研究放松并发控制的可串行 性也是可行的。研究表明可串行性是并发控制的非必要条件。实时应用的数据往往时间 很短，所有由并发事务所引入的不一致性不会在数据库中扩展太大，而且这种“局部” 不一致性可以使用恢复技术来补救。所以，实时数据库系统的并发控制技术包括可串行 化和放宽可串行化。 锁式并发控制 传统的锁式协议2 p l 面临着“优先级颠倒”和“死锁”的问题，这对实时数据库系 统式不适合的。所以开发多种策略以解决这些问题成为需要，典型的解决方法有以下几 种【2 】： 优先级继承：当发生优先级颠倒时，提高“占有者”t h 到“请求者 t r 的优先级， t h 继续执行知道结束( 提交或者夭折) 。在t h 因为某些原因( 成为死锁的牺牲者) 而重启 的时候，它恢复原来的优先级。让t h 继承t r 优先级是为了让它尽快完成，因为t h 的 进展也意味着t r 的进展。这种策略存在的问题是t r 被阻塞的时间可能会任意长，由于 这种继承是传递性的，潜在存在t r 的阻塞链。 高优先级夭折：这种策略的思想是当发生优先级颠倒时，夭折低优先级的t h ，而让 高优先级的t r 执行。该策略称“高优先”法( h p ) 。这种策略可以消除死锁，同时它本 身也存在以下的问题：当那些执行时间很长时间而还需要执行很短时间的t h ，夭折的 代价很大。尤其是执行时间与t h 估算的剩余时问相差很小的时候，重启可能导致其超 截止时间，而且消费大量系统资源，使整个系统性能下降。如果采用动态优先级分配策 略，则重启的t h 的优先级可能升高，甚至其优先级升高到比t r 的优先级还高，t r 可能 夭折，这样导致循环夭折。 优先级顶：这种策略是为每一个数据设置一个。“优先级顶，凡是存取这种数据的事 务的优先级最高。为了防止一个事务( 这种事务的优先级不高于当前由其他事务锁住的 所有数据的最高优先级顶) 在获得一个数据的锁的时候被阻塞，该策略假定在每一事务 执行前就知道其要存取的数据，并且为存取这个数据的所有事务设定其i d 和优先级表。 这种称为“数据优先级 的改进策略可动态地指定每一数据优先级中当前存取该数据的 所有事务的高优先级，按照数据优先级排序各事务对一数据的存取请求，不考虑其所有 被锁住数据的优先级。 l o 第一二章实时内存数据库关键技术介绍 有序共享：引入了第三种“有序共享锁”之间的关系。例如，如果事务t i 已具有数 据对象o 的一个读锁r l t i ( o ) ，现事务t i 请求加写锁w l t j ( o ) ，则建立一个“有序共享 关系”r l t i ( o ) _ w l t i ( o ) ，而后允许w l t j ( o ) 请求。为了保证可串行化，事务必须遵 循有序共享规则：若事务t i 获得一个对于t i 的一个锁有有序共享关系的锁，则对应的 t i 操作必须在t i 的以后执行，且直到t i 结束( 提交或者夭折) 后才能提交。 时标排序并发控制法 时标排序( t i m e s t a m po r d e r i n g ，t o ) 的基本思想如下：第一，按照系统时钟或者计数 器为每一事务t i 赋一时标t s ( t i ) 。所以，时标集是一全序集。第二，若事务t i 请求的操 作与t j 己在处理的一操作冲突，且t s ( t i ) t c ，且该片是变更过的，则建立该片的一个新副本，然后对 新副本进行变更，且更新其t s 成最近的变更时间。 1 6 在关系数据库系统中，数据常驻磁盘，磁盘数据需要按照一定的存取方法调剑内存 后才能被存取。而在实时内存数据库系统中，数据库的工作版本常驻内存，其中的数据 可被事务直接存取。传统的数据结构与存取策略旨在减少i o 代价，而对实时内存数据 库的事务而言，i o 已经基本上消除，所以原有的数据结构与存取策略对实时内存数据 库可能已不再使用。在关系数据库中，对数据的顺序存取速度远远高于随机存取，因此 常采用“记录集群”技术，但“集群”造成许多不能使用的存储孔洞。在实时内存数据 库中，数据操作时，随机访问与顺序访问性能差别不大，但是存储空问却极其宝贵。 近几十年对树形数据组织结构的研究中，丌发了许多利于数据库的数据组织结构， 如b 树、a v l 树等，而这些结构最初都是为传统磁盘数据库服务的。设计这些组织结 构考虑的首要因素是减少i o 代价，其次才足空间的利用率和数据的实时处理。鉴于此， 很多数据组织结构不再适用于内存数据库。现介绍两种常用的树形数据组织结构：b 树 和a v l 树来说明这一点。 3 1b 树 b 树是一种平衡的多路搜索树，由于他是一个宽而浅的树，查找一个数据需要防问 很少的节点，所以它比较适用于磁盘数据库的数据组织结构。目前，大部分关系数据库 系统采用b 树的变种b + 树，b + 树对磁盘式数据库这类减少磁盘访问次数为宗旨的应用 很适合。然而由于b + 树将实际数据均存放在叶子节点，所以对随机访问和顺序访问同 样高速的内存数据库降低了节点的数据覆盖率( 研究表明b + 树的数据覆盖率为5 附2 j ) 。 b 树和b + 树的主要区别是b 树中关键字的值可以出现在树中任何位置，它不像b + 树那 样高层节点关键字是叶节点关键字的重复，叶节点也不含顺序链接指针，所以更省内存。 对于内存数据库，b 树比b + 树更合适。 b 树的查找操作是很简单的，而插入和删除操作有点复杂，因为一个点的插入和删 除可能会导致它的子树的重建。而且b 树的查找效率也不高。因为在b 树的查找过程 中，虽然只访问很少一部分节点，但是需要对访问剑的节点进行二分查找，这对实时性 很强的内存数据库束说检索效率不高。 由以上介绍可以看出b 树对磁盘数据库系统有很好的数据组织结构，但是b 树的每 个结点的数据覆盖率仪为6 0 【7 1 左右，这对内存空间极为宝贵的m m d b 来说效率太低。 所以是不适合内存数据库的。 图3 1 给出了b 树的节点表示和典型的b 树状结构实例。 1 7 实时内存数据库数据耋f l 织结构优化策略研究 b 树i ， 结构 l ! ：! ! i p 1 p 2 p 3 p 1 p 2 p 3 p 1p 2p 3 2 8 2 93 6 6 0 7 5 7 99 0 9 9 图3 1b 树节点和b 树结构买例 f i g u r e3 1 b t r e en o d ea n db t r e es t r u c t u r e 3 2a v l 树 a t & b e l l 实验室s i l i c o n 数据库核心组织以a v l 树作为数据组织结构【7 】。a v l 树是一 个平衡二叉树，提出a v l 树的目的是提高一般二叉树搜索的效率，减少树的平均搜索 高度。由于a v l 树的平衡性，其高度总是保持为对数【2 1 ，因此它的检索速度是很快的。 实现大量数据的实时查询操作时，a v l 树作为一种索引结构效率是比较高的。 a v l 树的插入和删除操作等同于二叉树的插入删除操作，当插入和删除操作引起树 中平衡性破坏时，调用旋转操作维持平衡性。根据节点的失衡状态，a v l 的旋转操作有 l l 型旋转、l r 型旋转，r r 型旋转，r l 型旋转。虽然a v l 树可以通过旋转操作来保 持平衡，进而保证a v l 树有比较高的查找效