（计算机应用技术专业论文）过程实时数据库索引算法与压缩算法研究与实现.pdf

摘要 过程实时数据库索引算法与压缩算法研究与实现 摘要 实时数据库是数据和事务都有定时性限制的一类特殊数据库，主 要针对各种时间关键型应用。过程控制是实时数据库的一个非常重要 的应用场合，它主要处理生产装置、生产过程的控制和优化、生产系 统的调度等问题，在现代企业中，它也是企业信息集成系统的重要组 成部分。 过程控制中会产生海量数据，这么多的数据不可能瞬时被存储到 磁盘上，只能先实时存储到内存中。过程实时系统具有数据量大、时 效性强的特点，为了达到实时存储，内存库的空间利用率和响应速度 成为我们首要解决的问题。因此过程实时数据库的索引机制应在尽量 减少内存占用量的同时进一步提高数据操作的速度。本文在b 树、t 树的基础上提出并实现了了一种新的索引机制_ i ，+ 树，l + 树的每 个结点上可以有多个元素，并且采用的是分裂结点办法，减少了t 树的平衡旋转操作，并且结点增加了后继结点指针。这样，它不仅在 内存利用率上与t 树相似，而且较大程度地提高修改操作的速度和查 询速度，尤其是范围查询。 海量数据存储到内存中，方便于查询数据等操作，但最终数据要 存储到磁盘上。由于工业控制系统应用的大型化，系统内的信号数量 会大幅度增加，其需要记录的历史数据量也非常大，如果将这些数据 直接存储，不仅会浪费大量存储空间，且会使得数据查询、传输变得 l 北京化工大学硕士学位论文 困难。因此，需要将数据压缩技术引入实时数据库中。本文研究并实 现了美国p i 公司采用的旋转门压缩算法。 本文侧重于研究轻型的过程实时数据库，因此实时数据库不仅要 能独立工作，有时也要配合其他客户端应用程序进行工作，这就需要 暴露出接口供其他应用程序调用。本文利用c o m 技术实现了上述两 种算法的各种接口，不仅可以使过程实时数据库内核作为应用程序单 独运行，也可以被其他客户端( 应用程序或者d l l ) 调用。尤其是 客户端可以采用其他支持c o m 标准的面向对象的高级语言来编写， 增加了程序的灵活性。 关键词：实时数据库，l + 树索引机制，旋转门压缩算法，c o m n a b s t r a c t p r o c e s sr e a l t i m ed a t a b a s ei n d e x a n dc o m p r e s sa l g o i u t h mr e s e a r c ha n d r e a l i z a t i o n a b s t r a c t t h er e a l t i m ed a t a b a s ei sak i n do fs p e c i a ld a t a b a s ei nw h i c hd a t aa n d t r a n s a c t i o nb o t hh a v et i m i n gr e s t r i c t i o n s ，a n dp r i m a r i l yf o rav a r i e t yo f t i m e - c r i t i c a la p p l i c a t i o n s t h ep r o c e s sc o n t r o li sav e r yi m p o r t a n t d a t a b a s ea p p l i c a t i o n ，w h i c hm a i n l yd e a l sw i t hp r o d u c t i o ni n s t a l l m e n t ， t h ep r o d u c t i o np r o c e s sc o n t r o la n d o p t i m i z a t i o n ，p r o d u c t i o ns y s t e m s c h e d u l ea n ds oo n i nt h em o d e me n t e r p r i s e s ，i ti st h ei m p o r t a n tp a r to f t h ee n t e r p r i s ei n f o r m a t i o ni n t e g r a t i o ns y s t e m p r o c e s sc o n t r o lw i l lg e n e r a t ev a s ta m o u n t so fd a t a ，b u ts om o r ed a t a c a n tb es t o r e dt od i s ko nt h et r a n s i e n t ，a n do n l yb es t o r e di n t om e m o r y p r o c e s sr e a l t i m es y s t e mh a sf e a t u r e so fal a r g ea m o u n to fd a t a ，s t r o n g t i m e l i n e s s i no r d e rt oa c h i e v er e a l - t i m es t o r a g e ，t h eu t i l i z a t i o no ft h e m e m o r yp o o ls p a c ea n dr e s p o n s et i m eb e c o m eo u rt o pp r i o r i t yt o d e a l i n g t h e r e f o r e ，t h ep r o c e s so f r e a l t i m ed a t a b a s ei n d e x i n gm e c h a n i s m s h o u l dm i n i m i z et h ea m o u n to fm e m o r yf o o t p r i n ta n df u r t h e ri m p r o v et h e s p e e do fd a t am a n i p u l a t i o n i nt h i sa r t i c l e ，b a s e do nb t r e ea n d t - t r e e i n d e xm e c h a n i s m ，an e wm e c h a n i s mc a l l e dl + 一t r e ew a sb r o u g h tu p ，i n w h i c he a c hn o d ec o u l dh a v em u l t i p l ee l e m e n t s ，a n du s i n gt h en o d e s p l i t t i n ga p p r o a c ht or e d u c et h eb a l a n c eo ft h et r e er o t a t i o no ft h et i i i 北京化工大学硕上学位论文 o p e r a t i o n ，a n dt h es u b s e q u e n ti n c r e a s ei nn o d ep o i n t e r t h en e w m e c h a n i s mn o to n l yh a st h es a m es p a c eu t i l i z a t i o na st - t r e e ，b u ta l s o p r o m o t e st h es p e e do f m o d i f i c a t i o na n ds e a r c h i n g ，e s p e c i a l l ys c o p e s e a r c h i n g m a s sd a t ai ss t o r e di n t om e m o r yt of a c i l i t a t et h eo p e r a t i o no ft h e q u e r yd a t a ，b u tt h ef i n a ld a t as h o u l db es t o r e dt od i s k d u et oi n d u s t r i a l c o n t r o ls y s t e ma p p l i c a t i o n sw i t hl a r g es c a l e ，t h es y s t e ms i g n a l sm a y i n c r e a s el a r g e l y ，s ot h ea m o u n to fh i s t o r i c a ld a t an e e dt ob es t o r e d i f t h e s ed a t ai ss t o r e dd i r e c t l y ，t h a tw i l ln o to n l yw a s t eal o to fs t o r a g es p a c e ， b u tm a k et h ed a t aq u e r ya n dt r a n s m i s s i o nd i f f i c u l t t h e r e f o r e ，t h ed a t a c o m p r e s s i o nt e c h n o l o g yn e e d st ob ei n t r o d u c e di n t or e a l t i m ed a t a b a s e t h i sp a p e rh a ss t u d i e da n dr e a l i z e dt h er e v o l v i n gd o o rc o m p r e s s i o n a l g o r i t h m u s e db yt h eu s p ic o m p a n y t h i sa r t i c l ef o c u s e so nt h es t u d yo ft h ep r o c e s so fl i g h tr e a l t i m ed a t a b a s e ， s or e a l t i m ed a t a b a s es h o u l dn o to n l yb ea b l et ow o r ki n d e p e n d e n t l y , b u t s o m e t i m e sa l s on e e dt oc o o p e r a t ew i t ho t h e rc l i e n ta p p l i c a t i o n st ow o r k , w h i c hr e q u i r e st oe x p o s ei n t e r f a c e sf o ru s eb yo t h e ra p p l i c a t i o n s i nt h i s a r t i c l e ，c o mt e c h n o l o g yw a su s e dt oa c h i e v et h ev a r i o u si n t e r f a c e so f a b o v e m e n t i o n e dt w ok i n d so fa l g o r i t h m s ，w h i c hn o to n l ym a k e st h e p r o c e s sr e a l t i m ed a t a b a s ek e r n e la sa na p p l i c a t i o nt or u ns e p a r a t e l y , b u t a l s oc a l lb ec a l l e db yo t h e rc l i e n t s ( a p p l i c a t i o n so rd l l ) i np a r t i c u l a r , t h e c l i e n t sc a l lu s eo t h e rs u p p o r t i n gc o ms t a n d a r da n do b j e c t - o r i e n t e d i v a b s t r a c t h i g h - l e v e ll a n g u a g e s ，w h i c h i n c r e a s e sf l e x i b i l i t yo ft h ep r o g r a m k e yw o r l d ：r e a l t i m ed a t a b a s e ，l + t r e ei n d e xm e c h a n i s m ，s w i n g i n g d o o rc o m p r e s s i o na l g o r i t h m ，c o m v 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者签名：日期： 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京化工大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。 保密论文注释：本学位论文属于保密范围，在土年解密后适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授 权书。 1 作者签名：迫一：型 导师签名：丝逸豇 日期：竺：竺：! ： 日期： q 孥! 圣! ! 翌 第一章绪论 1 1 选题的背景 第一章绪论 针对不同的应用，人们将数据库系统同其它领域的学科技术有机的结合起 来，形成各种新数据库技术【l 】。实时数据库( r t d b ：r e a l t i m ed a t a b a s e ) 就是 其中之一，它适用于处理具有不断更新的快速变化的数据和时间限制的事务，应 用于对数据库能力和实时处理技术两者均有要求的各种领域【2 】。 随着计算机在工业控制中的广泛应用，自动化程度不断提高，因此工业控制 系统对控制软件提出了高要求，一方面由于生产过程中产生大量的数据，数据管 理成为必须的功能，另一方面由于工业控制的实时性，必须有一个实时数据库系 统为整个系统的数据处理、组织和管理提供支持【3 】。 实时数据库系统结合了实时数据处理技术和数据库技术，并同时满足数据实 时性和一致性要求，支持大量的数据共享，维护数据的一致性、完整性，又支持 数据和事务的时间限制。实时数据库，作为企业自动化与信息化的实时软件平台 的核心技术，它在实时控制和管理控制一体化上表现出了巨大的应用前景 4 1 。 过程控制系统是实时数据库系统最重要的应用领域之一。实时数据库系统与 现场控制设备直接相连接，使企业管理层实时地得到来自生产过程的数据，为管 理信息系统的开发与应用提供了一个理想的平台，实现了管理与控制一体化，使 企业的管理信息系统实时、高效的运行。 1 1 1 过程控制与实时数据库 过程控制是实时数据库的一个主要和典型的应用场合【5 】。 企业的生产过程连续、复杂，包含了大量的过程动态信息，如温度、压力等， 企业为了实现稳定、高效的生产，必须充分利用过程中的这些实时动态信息。这 类信息具有两个突出的特点：一是活动时间性强，要求在一定的活动时间内从生 产过程中采集、存储、处理信息，并及时做出响应；二是数据只在一定的时间范 围内有效，过期则不能及时反映过程状况，不具任何意义。这就要求必须采用实 时数据库系统为过程控制提供可靠的数据支持。实时数据库和过程控制系统的关 系如图1 1 所示。 北京化工大学硕士学位论文 图1 - 1 过程控制中的实时数据库 f i g 1 - 1r e a l - t i m ed a t a b a s ei np r o c e s sc o n t r o l 从一个数据库的角度来看，一个实时过程控制系统典型的由三个紧密结合的 部分组成：被控系统、执行控制系统、数据系统【6 】。被控系统是所考虑的生产过 程，称为外部环境或者物理世界；执行控制系统通过数据采集装置检测被控过程 的状态，通过控制器和执行装置协同和控制生产过程的活动，称为逻辑世界；数 据系统有效的存储、操作和管理实时信息，称为内部世界，执行控制系统和数据 系统称为控制系统。内部世界的状态是物理世界中的状态在控制系统中的映像， 执行控制系统通过内部世界而感知物理世界状态，基于此与被控系统交互。 1 1 2 实时数据库的历史现状 数据库理论和技术的发展极其迅速，应用日益广泛。以关系型为代表的三大 经典( 层次、网状、关系) 型数据库在理论和技术方面已经比较成熟，在传统的 应用领域，尤其是商务和管理的事务型应用方面取得了极大成功。然而随着软硬 件技术的发展，计算机应用的深入，产生了许多新的应用领域，对数据库系统提 出的新的要求，由此产生了一大批新的数据库技术，实时数据库就是其中之一 【硎 概况的讲，实时数据库就是其数据和事务都有显示定时限制的数据库【i 川， 系统的正确性不仅依赖于事务的逻辑结果，而且依赖于结果所产生的时间。但实 时数据库并不是数据库技术和实时系统两者的简单结合，它在概念、理论、技术、 方法和机制方面具备自身特点，如数据库的结构与组织；数据处理的优先级控制、 调度和并发控制协议与算法；数据和事务特征的语义及其与一致性、正确性的关 系；数据查询事务处理算法与优化；i o 调度、恢复、通信的协议与算法等等， 这些问题之间彼此高度相关。 2 第一章绪论 目前国外一些大公司已针对各种应用进行了实时数据库的开发与研制，已经 开发出比较成熟的商用实时数据库系统，其中在国内应用比较广泛的系统有：美 国o s is o f t w a r e 公司的p i ( p l a n ti n f o r m a t i o ns y s t e m ) 、美国h o n e y w e l l 公司 的p h d ( p r o c e s sh i s t o r yd a t a b a s e ) 、美国a s p e n t e c h 公司的i p 2 1 ( i n f o p l u s 2 1 ) 、 美国w o n d e r w a r e 公司的i n d u s t r i a ls q l 掣】。这些产品技术比较成熟，但价格 非常昂贵，而且受制予人，无法有针对性的开发满足我们实际需求的、适合我国 国情的实时数据库应用产品。 值得注意的是国外已有许多实时数据库系统厂家逐步向综合自动化整体解 决方案供应商转化，他们的产品也从单一的实时数据库系统逐步成为企业综合自 动化系统的一个组成部分。如o s is o f t w a r e 正在淡化p i 的概念，严格来说现在 的p i 不再是实时数据库了，现在o s is o f t 推出的是实时企业智能化解决方案 r t p m ，p i 实时历史数据引擎是r t p m 中r tb a s e l i n e 的小部分。 国内是在2 0 世纪9 0 年代开始进行实时数据库理论研究和实践探索的，目前 已经取得了丰硕的成果，但国内现有的实时数据库产品不论在技术性能、用户功 能扩展等方面同国外的产品相比仍有很大差距。 1 1 3 实时数据库概述 一、实时数据库的发展 数据库技术发展很快，使用范围很广，以数据模型的发展演变作为依据和标 志可以将数据库技术分为三个阶段【1 2 4 钔。第一代数据库系统是指层次和网状数据 库系统，它们的数据模型都是格式化数据模型。第二代是支持关系数据模型的关 系数据库系统，关系模型建立在严格的数学概念基础上，概念简单、清晰，易于 用户理解和使用，因此在实际的应用中获得极大的成功。第三代的数据库系统将 是以更加丰富的数据模型和更强大的数据管理功能为特征，从而满足传统数据库 系统难以支持的新的应用要求。 数据库的应用正向数据通信、电子商务、实时仿真等新领域扩展，这些领域， 一方面，要维护大量共享数据和控制数据；另一方面，其应用活动( 任务或事务) 有很强的时间性，要求在规定的时刻和( 或) 一定的时间内完成其处理，因此对数 据库和实时处理两者的功及特性均有需求，既需要数据库来支持大量数据的共 享，维护其数据的一致性，又需要实时处理来支持其任务( 事务) 与数据的定时 限制。传统数据库无法提供这样的功能，只有实时数据库才能同时支持定时和一 致性。 二、实时数据库的特征 3 北京化工大学硕士学位论文 基于过程控制的实时数据库由于其应用场合的要求，其数据和事务都具有实 时性特征。 实时数据库中，数据随外部环境状态的变化而快速变化，其值在一定的时间 内有效，必须同时考虑数据库内部状态与外部状态的一致，还必须考虑它与其他 被使用的数据间的时间一致性，这些就是实时数据库系统的数据特征【1 5 d 。7 1 。 实时数据库的根本特点在于数据与事务的定时限制，而且数据的时间一致性 也最终将导致事务的时间限制，所以，定时性是实时数据库事务的最根本特征 1 8 - 1 9 ；实时事务具有不同的定时限制，其中重要的有：截止时间、到达时间、期 望执行时间等；实时事务还具有处理优先级的特征，常见的事务优先级分配算法 有以下几种：最早放行最优先( e a r l i e s tr e l e a s ef i r s t ) 、截止期最早最优先( e a r l i e s t d 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 ) 、空余 时间最短最优先( l e a s ts l a c kf i r s t ) 。 三、实时数据库管理系统的功能 一个实时数据库管理系统( r t d b m s ) 的设计目标首先是对事务定时限制的 满足，其基本原则是：宁要部分正确而及时的信息，也不要绝对正确但过时的信 息。除了具有数据管理存储查询、事务管理调度控制以及可靠性恢复等一般数据 库管理系统( d b m s ) 具有的功能外，一个r t d b m s 还具有以下功能特性【2 0 】： 1 数据库状态的最新性即尽可能地保持数据库的状态为不断变化的现实世 界当前最真实状态的映像。 2 数据值的时间一致性即确保事务读取的数据是时间一致的。 3 事务处理的实时性即确保事务的及时处理，使其定时限制尤其使执行的 截止期得到满足。 因此，r t d b m s 是传统d b m s 与实时处理两者功能特性的完善或无缝集成。 它与传统d b m s 的根本区别就在于具有对数据与事务施加和处理“显式 定时 限制的能力，即使用“实时协议 来进行有关数据事务的处理。 四、实时数据库的体系结构 从系统的组成结构来看，r t d b m s 与传统的d b m s 没有什么大的区别。图 1 2 给出了它的主要功能部件及其组成【2 他5 1 。 实时数据库的执行模型描绘数据库管理系统的运作原理，它包括： ( 1 ) 事务模型 传统的a c i d ( 原子、一致、隔离、永久) 性的事务模型对实时数据库已不 再适用，需要具有内部构造或彼此相关性的“复杂”事务模型，即嵌套、合并、 分裂、通信和合作事务模型等。故实时数据库系统必须支持这种复杂事务，处理 事务间的结构、行为和时间相关性。 4 第一章绪论 实时应用程序 牟 买盯侗膳 i 一i 琪阿旱，肴| 一一i 买盯t f 及弹制1 耷 实时资源管理 c p u 管理陈爿缓冲区管理 实时数据管理 数据操作 恢复管理 日志管理 耷 实时i o 调度 耷 数据库 图l - 2 实时数据库的体系结构 f i g 1 - 2t h ea r c h i t e c t u r eo fr e a l - t i m ed a t a b a s e ( 2 ) 资源模型 它确定系统资源的类型机器管理策略，包括分配、使用和回收策略。实时数 据库系统必须采用基于优先级和考虑定时限制尤其是截止期的分配策略：资源适 用的“中断”策略也是优先级式的，即高优先级可抢占( 中断) 低优先级的资源。 具体又可以有多种不同的抢占方式及其各方面的代价，需要r t d b m s 仔细决策。 ( 3 ) 负载模型 它规定各种类型事务的到达( 或在系统中生成) 、执行期限及频率的分步， 包括周期、非周期及零星事务，软或硬事务及其延迟的代价计算等。 ( 4 ) 调度模型 它确定事务的优先级分配策略、调度算法、互相冲突的解决( 并发控制) 策 略及其机制，控制事务正确、有效地执行。r t d b m s 的调度模型还应有一定的 “可调度性预测能力及“应急处理能力。 ( 5 ) 执行的正确性 相对于传统数据库而言，实时数据库系统执行的正确性在概念、内容与准则 上都有根本性的不同，实时数据库系统不但要确保事务执行结果( 包括返回数据 的状态及产生的数据库状态) 的正确性，还要保证其执行在结构、行为、时间上 的正确，即要正确实现事务间的结构、行为、时间相关性及执行依赖性。 北京化工大学硕士学位论文 1 2 选题的意义 在有些过程控制领域，所需求的数据量并不太大，比如过程仿真；有时候过 程控制的硬件条件有限，比如微型机的c p u 速度不够快、内存容量有限、硬盘 容量不大。然而诸如p i 公司等的实时数据库很庞大，也非常复杂，这种大型的 实时数据库主要是针对大量的数据处理的，它们对系统的c p u 、内存以及硬盘 容量的要求比较高，因此不适于小型、硬件条件比较差的过程控制领域。虽然， 现在市场上出现了嵌入式实时数据库系统，但价格很昂贵，而对数据量需求量少、 硬件配备较差的企业往往负担不起太贵的价格。在这种情况下，我们就需要开发 对c p u 、内存以及硬盘要求比较低的，算法效率高的，可靠的轻型的过程实时 数据库。 这种轻型的过程实时数据库不仅能达到实时存储的目的，算法效率要比较 高，而且要兼容性能比较好，最好能用动态链接库形式嵌入到微机中。以便满足 小型过程控制领域实时控制、可靠性好、硬件要求不高的需求。 1 3 本文主要内容 过程控制生产过程中会产生海量数据，如此多的数据不可能瞬时被存储到磁 盘上，只能先实时存储到内存中。过程实时系统具有数据量大、时效性强的特点， 为了达到实时存储，内存库的空间利用率和响应速度成为我们首要解决的问题。 目前，大多数实时数据库采用的是t 树索引算法，尽管它的内存利用率高，但 插入、删除、查询效率较低，不符合轻型过程实时数据库对算法效率要求高的特 点。本文在b 树、t 树的基础上提出并实现了一种新的索引机制_ i ，+ 树索引 机制，l + 树的每个结点上可以有多个元素，并且采用的是分裂结点办法，减少 了t 树的平衡旋转操作，并且结点增加了后继结点指针。这样，它不仅在内存 利用率上与t 树相似，而且较大程度地提高查询( 尤其是范围查询) 和修改操 作的速度。本文将l + 树与传统索引机制t 树进行了详细对比，证明l + 树确实能 提高内存的响应速度。本文还对l + 树进行扩展，提出了扩展改进方法，使其更 具有一般性。 海量数据存储到内存中，方便于查询数据等操作，为了保存数据便于日后查 看、仿真等使用，数据最终要存储到磁盘上。由于工业控制系统应用的大型化， 系统内的信号数量的大幅度增加，其需要记录的历史数据量非常之大，如果将这 些数据直接存储，不仅会浪费大量存储空间，且会使得数据查询、传输变得困难。 6 第一章绪论 因此，需要将数据压缩技术引入实时数据库中。本文研究并实现了美国p i 公司 采用的旋转门压缩算法。为了研究其实际效果，本文做了大量的测试，一方面通 过多次改动压缩偏移量，来观察有一定规律的曲线经压缩后的图形，以及解压缩 后的曲线图形与原图形的对比来观察其失真情况，另一方面通过随机产生在某一 范围波动的海量数据，多次改动压缩偏移量，进行压缩，查看压缩效率的情况来 说明旋转门算法的效果。 本文侧重于研究轻型的过程实时数据库，因此实时数据库不仅要能独立工 作，有时也要配合其他客户端应用程序进行工作，这就需要暴露出接口供其他应 用程序调用。为了使内核模块的通用性更强，本文采用c o m 技术暴露出接口， 这样就不受客户端程序语言的限制，只要符合c o m 标准的面向对象高级语言都 能调用内核模块的接口。本文列出了旋转门压缩与解压缩以及l + 树算法的基本 接口并说明了其用法。 本文最后实现了一个简单的过程实时数据库引擎，对自己实现的l + 树索引 机制和旋转门压缩算法进行了综合测试。通过随机产生数据利用l + 树索引算法 存储到内存中，进行查询、范围查询、插入、删除等操作的测试，最后把数据存 储进行压缩存储到本地磁盘，演示一个简单独立的过程实时数据库的基本流程。 1 4 本文创新点 本文在分析了过程实时数据库轻型化的要求，在内存索引机制和压缩算法上 提出了自己的观点，以及实现方法。 在前人研究的基础上，尤其是在研究t 树的基础上提出并实现了l + 树索引 算法，它不仅保留了t 树高的空间利用率，而且加快了插入、删除时间，最主 要的是改进了范围查询，使其更加快速、可靠。 研究并实现了旋转门压缩与解压缩算法，通过改变压缩偏移量就能控制数据 的压缩精度，压缩偏移量越大压缩精度越低，压缩偏移量越小压缩精度越高。 利用c o m 技术将两个算法模块的接口导出，这样模块不仅能使轻型过程实 时数据库引擎单独运行，而且方便其他支持c o m 标准的面向对象语言实现的应 用程序以及d l l 进行调用，使通用性更高。 7 第二章传统内存索引算法 第二章传统内存索引算法 由于m m d b s 能克服d r d b s 的数据操作延迟时间难以预测的缺点，提供对 实时事务的有效支持，已成为实时数据库的最佳选择。由于m m d b 内存受限的 缺点，需要研究一种合适的索引机制提高存取效率，改善系统性能【2 2 1 。 在d r d b s 中，通常采用b + 树索引结构。因为它既能提供对关键字的随机 存取，又能提供顺序存取，结构宽而浅，并且从根结点到任一叶结点的路径长度 都相同且最短，复合d r d b s 尽量减少磁盘访问次数的设计宗旨。因此，b + 树能 为d r d b s 提供合适的存取方法。 在m m d b s 中，数据库工作版本常驻内存，对磁盘的访问次数不再是关注的 焦点，b + 树索引已不再合适。b + 树的结点覆盖率仅为5 5 ，这对内存空间极为 宝贵的m m d b s 来说存储效率太低，所以必须开发适合于内存直接访问特性的 存取方法，且在处理时空关系时，空间应为第一位【2 6 】。 目前，m m d b s 有多种索引结构，本文在介绍并实现传统的索引结构机制的 基础上提出并实现了一种新型索引结构一i ，+ 树索引结构。 下面介绍几种传统的内存索引机制，并分析其优缺点。 2 1 平衡二叉树树索引机制 2 1 1a v l 树的定义 平衡二叉树【2 7 之8 】的定义为： ( 1 ) 若平衡二叉树中的结点数为零，则该树是一颗空的平衡二叉树； ( 2 ) 根结点的左子树和右子树深度之差的绝对值不超过l ； ( 3 ) 左子树和右子树都是平衡二叉树。 用每个结点的左子树深度减去右子树的深度得到的值称为该结点的平衡因 子。在一棵平衡二叉树上的每个结点的平衡因子的绝对值不超过l 。 2 1 2a v l 树的基本操作 一、a v l 树的插入 插入步骤如下： 1 ) 沿着从根结点开始的路径对具有相同关键值的元素进行搜索，以找到插入 新元素的位置。在此过程中，寻找最近的，平衡因子为1 或l 的结点，令其为彳结 9 北意化i 太学删i ：学位论史 点。如果找到了相同关键值的元素，那么插入失败，以下步骤无需执行。 2 ) 如果没有这样的结点a ，那么从根结点开始再遍历一次，并修改平衡因子， 然后终止。 3 ) 如果b a a ) = 1 并且新结点插入到一的有子树中，或者6 几d ) 一l 并且插入是 在左子树巾进行的，那么一的新平衡因子是0 。这种情况下，修改从爿到新结点 途中的平衡因子，然后终止。 4 1 确定4 的不平衡类型并执行相应的旋转，在从新子树根结点至新插入结 点途中，根据旋转需要修改相应的平衡因子。 插入过程中，平衡的旋转主要有两种l l 与l r 型，具体如图2 1 ，2 - 2 ： 。夸冬：h 灭、。灭、天 + lh 8 lh h 圈2 - 1l l 旋转 曲插入之前b ) 插j k b l 之后c ) l l 旋转z 肝 f i g 2 - il l r o t a t i o n a ) b e f o r e i n s e t t 砷a f t e r i n s 盯t i n b lc ) a f t e r l l r o t a c e b l c lc a l h h 若b 卸，i 则b f ( b ) = b f ( a 产0 若b = 1 ，则b f ( b ) = o , b f ( a y - l 若b = - i ，卿j b f ( b 户1 , b f ( a ) = 0 图2 - 2l r 旋转 a ) 插入之前砷插入b r 之后c ) 晰转之后 f i g 2 - 2l rr o t a t i o n a ) b e f o r e i n s e f lb ) a f t e r i n s c a i n 胁c ) a f t e r l r r o 埘e 硒八 煦 。尺 h 徒文 第= $ # 统自存索引算洁 二、a v l 树的删除 如果删除发生在q 的左子树，那么b f ( q 1 减1 ，而如果删除笈生在q 的右子 树，那么b f ( q 1 加i 。可以看到如下现象： 1 1 如果q 新的平衡因子是0 ，那么它的高度减少了1 ，并且需要改变它的父 结点( 如果有的话) 和其他某些祖先结点的平衡因子。 2 ) 如果q 新的平衡因子是一1 或l ，那么它的高度与删除前相同，并且无需 改变其祖先的平衡斟子值。 3 1 如果q 新的平衡因子是一2 或2 ，那么树在q 结点是不平衡的。 如果删除发生在a 的左子树，那么不平衡是l 型；否则，不平衡就是r 型。 根据不同情况可以把一个r 型不平衡细分为r0 ，rl 和r 一1 类型。具体操作 如图2 3 、2 - 4 、2 5 ： i n 焱“廒咦 b 舛ji “：8 魁、j ! 、8 ；啦? b ，b b b - 口ra r h hh h h h i 毗 h 图2 3 r 0 类型的旋转 曲删除之前b ) 在a t 中删除之后c ) r o 旋转之后 f i g 2 3r 0r o t a t i o n 旬b e f o m d e l e t eb ) a f t e r d e l e t e j a rc ) a r 盯r 0r o t a t e hh l 一ih l 图2 一r l 类型的旋转 a ) 删除之前b ) 在a n 中删除之后c ) r i 旋转之后 f i g2 4r 1r o t a t i o n a ) b e f o nd e l e t e 砷a r 日d e l e t e i n a r o a f t e r r ir o t a t e a 一奈一 h 霞 气 b 北京化i 学删l ：学位论 a 囝 8 蹙0 e 默 c c r b 8 固 若b = 0 ，则b r a ) = b f ) = 0 ：若b - l ，则b h a 户- 1 ，b f ( b ) - o ：若b = - i ，则b f ( a ) = 0 ，b l a b ) = 阿2 - 5r 1 类型的旋转 a ) 删除之前b ) 在a r 巾删除之后c ) r - i 旋转之后 f i g 2 - 5r 一1r o t a t i o n 对b e f o r e d e l e t eb ) a f t e r d e l e t e i na rc ) a f t e * r - lr o t a t e 2 1 3 a v l 总结 在a v l 树中采用的二分搜索法与二叉树型结构相适应，不需要进行任何数 学计算，因此查询速度很高。但由于只在一个结点中存放一个元素，所以空间利 用率很低，这是a v l 树的第一大缺点。a v l 树上的每次插入和删除操作都导致 结点的插入和删除，容易造成树的不平衡从而需要进行平衡旋转操作，频繁的旋 转会使整个数据库的修改性能大大下降。故插入和删除操作开销大是a v l 树的 第一大缺点。因此，a v l 树不是我们的是佳选择。 2 2b + 树索引机制 b + 树索引机制在计算机的数据处理中有着广泛的应用。它既可以用于随机查 找又可以用于顺序查找，是提高存取效率的一种基本方法。b 十树索引结构一 般用于数据库的索引，综合效率非常高，像b e r k e r l y d b ，s q l i t e ，m y s q l 数据 库都使用了这个算法处理索引。 2 2 1b + 辫的定义 b + 树定义如下： ( 1 ) b + 树索引是一个多级索引但是其结构不同于多级顺序索引： ( 2 ) b + 树索引采用平衡树结构即每个叶结点到根的路径长度都相同 0 唧吒 乩一 c 白 。 “ 第二章传统内存索引算法 ( 3 ) 每个非叶结点有i n t ( n 2 ) 至0n 个子女，n 对特定的树是固定的；这至 少保证有b + 树5 0 的覆盖率。 ( 4 ) b + 树的所有结点结构都相同，它最多包含n 1 个搜索码值k i 、k 2 、 k n 1 ，以及n 个指针p 1 、p 2 、p n ，每个结点中的搜索码值按次序存放，即 如果i i ，那么k i k j ，如图2 7 所示。 ( 5 ) 所有的叶子结点在同一层上。 图2 7b + 树的结点结构 f i g 2 - 7b + 慨n o d e s t r u c t u r e 2 2 3b + 树的基本操作 一、b + 树的随机查找 b + 树的随机查找类似于b 树。但在b + 树上进行随机查找时，若非叶子结点的 关键字等于查找的关键字，则查找不能终止，还要继续向下查找，一直查到叶子 结点上的这个关键字。另外b + 树还可以由叶子结点构成的链表进行顺序查找。 b + 树随机查找关键字k 的算法如下： ( 1 ) k = k i ( 1 i j ) ，则判断磁所在的结点是否为叶结点 a 若为叶结点，则查找成功。 b 若为非叶结点，则查找失败。 ( 2 ) k ( k i ( 1 i k i ，则查找失败。 二、b + 树的插入操作 b + 树的插入过程类似于b 树。但是b + 树的插入仅在叶子结点中进行，当结 点中的关键字个数大于m 时要分裂成两个结点，它们所包含的关键字个数分别 为【( m + 1 ) 2 】( 注：向上取整) 和【州2 】( 注：向下取整) b + 树插入操作算法如下： ( 1 ) 插入操作仅在叶子结点上进行。 ( 2 ) 若被插入结点的关键字个数不满时，直接把关键字插入即可。 ( 3 ) 若被插入的结点的关键字个数己满，则进行“分裂 操作。 北京化工大学硕士学位论文 a 把结点分成两半 b 分裂后的左面那个结点中的最大关键字插入它们双亲结点中。 注：应考虑增加一个极大极限值( m a x ) ，否则上面算法在插入比已有最大值 大的关键字时将出错。若不这样做，则要比较麻烦的修改算法，且算法效率会大 幅降低。 图2 培b + 树插入过程图 f i g 2 8b + i n s e r t i o np r o c e s sf i g u m 三、b + 树的删除操作 b + 树的删除也仅在叶子结点中进行，当叶子结点中最大的关键字被删除后， 其在索引部分的值可以作为一个“分界关键字”存在而被保留，无须删除。若应 删除而使结点中关键字的个数少于 m 2 时，则和其同父结点合并。 b + 树删除操作算法如下： ( 1 ) 删除叶结点上的关键字k 。 ( 2 ) 此时被删除结点中关键字的个数小于 m 2 】( 注：向上取整) 个。 a 若相邻的左( 或) 右同父结点中的关键字个数大于 m 2 】个( f l z ：向上取 整) ，则需从左( 或) 右同父结点中借最大( 或最小) 关键字( 即“借键) 。 若从左同父结点借关键字，则需把剩余关键字中最大值替换左同父结点的 父结点的相关关键字。 若从右同父结点借关键字，则需把剩余关键字中最小值替换被删结点的父 结点的相关关键字。 b 否则，若相邻的左右同父结点中的关键字个数都是 m 2 】个( 注：向上取 整) ，就借不到关键字，此时，就要进行与“分裂”相反的处理过程“合并 ， 即把被删除结点和左( 或) 右同父结点合并在一起组成一个新结点。 若与左同父结点合并，则要删除左同父结点的相关关键字。 若与右同父结点合并，则要删除被删结点的父相关关键字。 1 4 第二章传统内存索引算法 2 2 4b + 树总结 常规的d r d b 普遍采用b + 树索引结构，因为它既提供对关键字的随机存取 又提供顺序存取，结构宽而浅，并且从根结点到任一叶结点都具有相同的也是最 短路径长度，正符合d r d b 的尽量减少磁盘访问次数的设计宗旨。b + 树的缺点 是每个结点的数据覆盖率仅为5 5 ，这对内存空间极为宝贵的m m d b 来说存储 效率太低。因此也不是我们的理想选择。 2 3t 树索引机制以及实现 2 3 1t 树的定义 t 树的定义如下： ( 1 ) 每个t 树结点可存放多个数据项( 通常是记录指针) ，且这些数据项按 键值从小到大有序排列，用m i n k e y 和m a x k e y 域存放最大键值和最小键值： ( 2 ) 每个t 树结点至多有两棵子树。