（计算机应用技术专业论文）嵌入式主存数据库索引机制的研究与改进.pdf

摘要 当今，嵌入式数据库系统作为移动计算，信息电器，电子商务 的核心技术在社会各领域得到广泛的应用，具有公共信息服务，实 时数据采集，位置相关查询等功能。它以成熟的数据库技术为基 础，针对嵌入式设备的具体特点，实现对数据的存储，操作和管 理。 嵌入式数据库所处理的事务通常是实时事务，事务调度的正确 性依赖于高效的处理和预测能力。由于磁盘t 0 速度慢且延迟的时 间难以预测，嵌入式数据库系统常常采用主存数据库技术。 数据库的操作性能在很大程度卜取决于它所采用的索引机制， 而嵌入式系统具有内存资源极为有限和处理器速度不高等特点，因 此适用于嵌入式数据库的索引机制应在尽量减少内存占用鼍的同时 进一步提高数据操作的速度。 现有的主存数据库索引机制如t 树，p 树，t t a i l 树，h y b r i d t h ，哈希机制等都不能兼顾嵌入式系统对时空双方面的要求，因此 研究一种具有优良时空性能的索引机制就显得至关重要。 本文针对嵌入式数据库的具体特点，在传统混合索引机制 h v b r i d t h 的基础上提出了一种新索引机制_ h t + 一t a i l ，它不仅具 有内存耗用量小的优点，而且较大程度地提高了查询和修改操作的 速度。 本文首先对嵌入式数据库和主存数据库技术进行j ，总体介绍； 然后较为详细地阐述了传统索引机制t 树，t 丰树，t t a i l 树及 h y b r i ( 1 _ 1 h 上的基本操作算法，并对h y b r i d - t h 索引机制的时空性能 进行理论分析，指出其存在的缺点；接下来重点探讨新索引机制h t + - 诅- l 和它所采用的新树型结构p _ t a i l 树，并从理论上分析了h t + 诅i l 索引机制的时空性能。最后通过h y b r i d t h 和h t + t a i l 两种 混合索引机制的一系列对比实验验证了h _ t * 一t a 订索引机制的优良时 空性能。 该新索引机制具有如下特点： 夺每个元素仅存储一次，减少了内存耗用量； 夺将具有相同哈希地址的元素组织成t t a i l 原子树； 夺通过哈希表将元素分散存储在各棵原子树中，数据操作在原子树 上进行，大大缩小了操作范围； 夺将哈希表的查询负担转移到p - 协i l 原子树中并采用改进的查询 算法执行查询操作，提高了查询性能； 夺当t + ，t a l 原予树中被涮内缩点出现下溢时，根据萁平衡因子判 断从前驱还是后继结点移动元素，大大减少了平衡旋转次数； 晗希表并不窦舔存放记录键毽，仅越爨定缀蔗子树的功麓； 夺不需要建立哈希结构至树结构的映象，从而节省了维护开销，提 意了穆改性链。 关键字：嵌入式数据库，主存数据库系统，索弓l 机制，记录指针 l l a b s t r a c t n o w a d a v s ，e m b e d d e dd a t a b a s es y s t e mh a sb e e nw i d e l ya p p l i e di 1 1a u s o c i a la r e a sa sak e m a lt e c h n 0 1 0 霉r yo fm o b i l ec o m p u t a t i o n ，i l l f o n n a t i o n a l ，p l i a n c ea n de l e c t r o n i cc o m m e r c e i th a sm a l l ym c t i o n s ，f b re x a m p l e ， p u b l i ci n f o 眦a t i o ns e r v i c e ，r e a lt i m ed a t ac o l l e c t i o n ，p o s i t i o nr e l a t e d s e a r c ha l l ds oo n b a s e do nn l em a t u r ed a t a b a s et e c h n o l o g y ，t h ee m b e d d e d 出妇b a s es y s t e mi m p l e m e n t st h es t o r a g e ，o p e r a t i o na n dm a n a g e m e n to f d a t ai na c c o r d a n c ew i t ht h es d e c i a lf e a t u r e so fe m b e d d e dd e v i c e s t h et r a n s a c t i o n sd r o c e s s e di nt h ee m b e d d e dd a t a b a s ea r eu s u a l l v r e a lt i m e 仃a n s a c t i o n sa i l dt h ec o r r e c m e s so ft r m s a c t i o nd i s p a t c hd e p e n d s o nm ec a p a c i t yo fh i g h l ye m c i e mp r o c e s sa 1 1 dp r e d i c t b e c a u s et l l ei n p u t a r l do u t d u ts d e e do fd i s ki sv e r yl o wa n dt h ed i s kd e f e h n e n ti su n p r e d i c t a b l e ，m a i nm e m o r yd a l t a b a s et e c h n o l o g yi so f t e nu s e di i lt l l ee m b e d d e d d a t a b a s es y s t e m t h ee f f i c i e n c yo fo p 硎o no nd a t a b a s ed e p e n d sd e e p l yo nt h ei i l d e x m e c h a n i s mw h i c ht h ed a t a b a s ea d o p t s b e c a u s el i m i t e ds t o r a g es p a c eo f m a i nm e m o 巧a n d1 0 wp m c e s sc 印a c i t ) ra r et h e u n i q u e f b a t u r e so f e m b e d d e ds y s t e m ，t h ei n d e xm e c h a n i s mw h i c ha d a p t st om ee m b e d d e d d a t a b a s es h o u l dc o m s u m es t o r a g es p a c ea sl i t t l ea sp o s s i b l ea n dm n h e r p m m o t et h es p e e do fd a t ao p e r a t i o na tt h es 锄et i m e t h ee x i s t i n gi 1 1 d e xm e c h a n i s mo fm a i nm e m o r yd a t a b a s es u c ha st - t r e e ，p t r e e ，t t a i l 慨e ，h v b r i d t h h a s hc a r u l o tm e e tt h et i m ea 1 1 ds p a c e d e m a n do fe m b e d d e ds v s t e ms i m u l t a n e o u s l y ，s oi ta p p e a r si m p o r t a n tt o w o r ko u tan e wi n d e xm e c h a n i s mt l l a th a sb e t t e rt i m ea n ds p a c ep e o r _ n l a n c e b a s e do nt l l et r a d i t i o n a lh y b r i di n d e xm e c h a l l i s m h y b r i d _ t h ，an e w m e c h a n i s mi na c c o r d a n c ew i mm es d e c i a lf - e a c u r e so fe m b e d d e dd a t a b a s e i sb r o u 蛳u pb y “sp a p e r t h en e wm e c h a i l i s mc a l l e dh - p t a i ln o t0 1 1 1 y h a st h ea d v a i l t a g eo f u s i n gl m l es t o r a g es p a c eb u ta l s op r o m o t e st h es p e e d o fs e a r c ha n dm o d i f i c a t i o ni nn os m a um e a s u r e t h i st 1 1 e s i sf i r s t l vi n t r o d u c e sm ee m b e d d e dc l a t a b a s ea n dt h em a i n m e m o n ，d a t a b a s et e c l l l l 0 1 0 9 yi nt o t a l i 田i tt b e ne l a b o r a t e si nd e 诅i l 山e a l g o r i t l l m so fb a s i co p e r a t i o n so nt r a d i t i o n a li n d e xm e c h a n i s m ，i n c l u d i n g t _ t r e e ，t 木t r e e ，t t a i lt r e ea i l dh v b r i d - 讯a 晚n ) l ，a r d s ，i ta n a l y z e st l l et i m e a n ds p a c ep m p e n i e so fh y b r i d t hm e c h 叭i s mi nm em e o r e t i c a ld e g r e e a 1 1 dp o i n t so u tt h ed m w b a c k so fi t n e x ti tf o c u s e so nd i s c u s s i n gt l l en e w i n d e xm e c h a n i s m h t 赤t a i la n dt 1 1 er l e wn es t m c t u r ea d o p t e db yh _ t 木一 t a j _ 1 t 半t a i l i tt h e na 1 1 a l v z e sm et i m ea n ds p a c ep e r f o 珊a n c eo ft h en e w i n d e xm e c h a n i s mi nm em e o r e t i c a ll e v e l l a s t l v ，i th a sv e r i f i e dm e e x c e u e n tt i m ea n ds p a c ep e r f o h n a i l c eo fh t 木t a i lt h r o u g has e r i e so f i i l e x p e r i m e l l t sw h i c hm a k ec o m p a r i s i o n sb e t w e e nt h et w oh y b r i d 洫d e x m e c h a n i s m - h v b r i d - t ha n dh - t 一t a i l t h en e wi n d e xm e c h a n i s mh a ss u b s e q u e n tc h a r a c t e r i s t i c s ： e a c he l e m e n ti ss t o r e do n l yo n c e ，s or e d u c e st h ec o n s u m p t i o no f s t o r a g es p a c e ； t h ee l e m e n t sw h i c hh a v et i l es 锄eh a s ha d d r e s sa r ea r r a n g e di na t 半一 t a i la t o mt r e e ： 夺s c a t t e r sa l le l e m e n t st om a l l ya t o mt r e e st h m u 曲h a s ht a b l ea n dd a t a o p e r a t i o n sa r ec a r r e d e do u to na t o mt r e e s 。s oh a ss h r i n k e d 廿1 es c o p eo f o p e r a t l o n ； 夺h a ss h i f 【e dt h eb u r d e no fs e a r c h 丘o mh a s ht a b l et ot 4 一t a i la t o mt r e e s a n da d o p t st h ei m p r o v e ds e a r c ha l g o r i t l l m ，s oh a si m p r o v e dt h es e a r c h p e r f b r r n a j l c e ； 令w h e nt h ei m e m a ln o d e si nt 丰t a i la t o mt r e e sh a v eu n d e r f l o w e da f t e r b e i i l gt a l ( e ne l e m e n ta w a y ，i ti s d e c i d e db yi t sb a l a n c ef a c t o rt h a t w h i c hn o d et om o v ee l e m e n t 丘o m ，p r e c u r s o ro rs u c c e s s o r t h i ss t a t e g y h a s 盯e a t l vd e c r e a s e dm et i m e so fr o 诅t i o nt h a ti sn e e d e dt ok e e p b a l a n c e ： 夺 h a s ht a b l ed o e s n ts t o r el y so fr e c o r d sa c t u a l l y ，i to n l yh a st h e f u n c t i o no fl o c a t i l l gt h ep o s m o no f t h ec o r r e s p o n d i n ga t o mn e e ； 夺d o n tn e e dt os e tu pt h er e l a t i o n s h i pb e t w e e nt h eh a s hs t n 】c t u r ea n d t h et r e es t m c t u r e ，s oh a ss a v e dt 1 1 e e x p e n s e s o np r e s e r v i n ga n d p r o m o t e dt h ep e r f o m a n c eo fm o d i f i c a t i o n k e yw o r d s ：e m b e d d e dd a t a b a s e ，m a i nm e m o r yd a t a b a s es y s t e m ，i n d e x m e c h a n i s m ，r e c o r dp o i n t e r 嵌入式主存数据库索引机制的研究与改进 第一章嵌入式主存数据库的概述 1 1 嵌入式数据库的概述 1 1 1 嵌入式数据库的定义 数据库技术是应数据管理任务的需要而产生的。6 0 年代后期， 随着计算机技术从科学计算向数据处理的扩展，数据库系统应运而 生。数据库系统的出现使信息系统的重心发生了转移，从以加工数 据的程序为中心转向以数据共享为核心。而当今的数据库系统向两 极化的方向发展，高端的超大型数据库系统( v l d b ) 解决复杂数 据如视频音频数据，多媒体数据，军事领域的数据的处理问题，满 足海量数据的存储和访问，它们将运行在下一代巨型主机服务器 上，特点是大，强，快；而低端的精小型数据库系统将解决个性化 数据的存储和处理问题，它们将嵌入各种电子设备和移动设备中， 特点是小，灵，易。后者亦称为嵌入式数据库系统1 2 。 一般来说，嵌入式数据库系统可以从体系结构方面来定义：嵌 入式数据库系统是指支持移动计算或某种特定计算模式的数据库管 理系统，它通常与操作系统和具体应用集成在一起，运行在智能型 嵌入式设备或移动设备上【l 】【2 1 。嵌入式数据库技术涉及数据库，分布 式计算以及移动通讯等多个学科领域，已成为当今数据库技术的一 个新的研究方向【1 1 。 1 1 2 嵌入式数据库的特点 夺微小内核，占用磁盘空间小，占用系统资源少 嵌入式数据库必然受到嵌入式系统速度，资源以及应用等各方 面因素的制约【3 l 。嵌入式系统的内存空问一般为几百k 到几m 问， 故嵌入式数据库必须能在有限的内存空间中运行【4 j 。可通过限制嵌 入式数据库所完成的功能和数据结构的数量及大小来减少占用的磁 盘空间州。 夺具有可靠性，可管理性和安全性 由于嵌入式数据库无法得到信息技术支持人员的现场技术支 持，故其自身必须具备可靠性和可管理性 4 】。许多应用领域的嵌入 式设备是系统中数据管理或处理的关键设备，因此嵌入式数据库对 存取权限的控制较严格，又由于某些数据的个人隐私性高，因此嵌 入式数据库在防止碰撞，磁场干扰，遗失，盗窃等对个人数据安全 的威协上需提供充分的安全保证【2 】。 夺具有互操作性和可移植性 硕士学位论文 为保证能与具有其它开发平台和操作系统的嵌入式数据库或大 型企业数据库进行通信，嵌入式数据库必须实现互操作。同时为适 应不同的硬件平台和操作系统，嵌入式数据库必须具备可移植性 【4 1 。 夺硬件速度慢 嵌入式系统比起通用计算机系统来，具有较慢的c p u 和总线速 度，为提高系统的运行速度，嵌入式数据库必须对系统耗时多的操 作所使用的算法进行精心的设计，尽量消除系统的性能瓶颈【3 j 。 夺具有白调节和自适应能力 嵌入式数据库系统中没有数据库管理员，它的用户一般都具有 很少的数据库知识，因此嵌入式数据库系统必须具有自我调节能 力，具有较高的预见性和自适应能力。它不能具有需要用户来设置 的系统参数，而且当应用环境发生改变时，系统必须能自我调整以 适应新环境【5 j 。嵌入式数据库不像完整规模的企业级数据库那样需 要很强的支持力量，它未提供除基本存储和检索外的其它功能，所 以可以采用零管理或近零管理 6 】，普遍使用自管理的模式，能自动 完成启动初始化，日志管理，数据压缩，备份，数据恢复等功能 【2 0 1 。 夺易配置 嵌入式数据库可被配置为面向具体的行业应用，可定制性强。 令具有健壮性 嵌入式设备经常有不可预料的硬复位，这就需要数据库有高度 的健壮性【2 。 夺与应用软件相结合 嵌入式数据库一般采用的体系结构便于集成到软件内部共同发 布，通常与操作系统和具体应用集成在一起，使得在应用系统的外 部，嵌入式数据库系统对用户是透明削引。 程序驱动式 嵌入式数据库系统无须独立运行的数据库引擎，由程序直接调 用相应的a p i 去实现对数据的存取操作。网此与大型数据库系统的 引擎响应式不同，嵌入式数据库系统是程序驱动式【7 】。 令随时与w e b 连接 w e b 上具有遍及世界的大量数据库。嵌入式数据库需要有发现 w e b 信息源的能力，即能快速准确地发现所要存取的数据库并与之 相连接。这种w e b 信息源的发现过程要求数据库系统提供丰富的源 数据【5 1 。 令具有实时性 嵌入式主存数据库索引机制的研究与改进 嵌入式数据库的很多应用如实时数据采集，工业控制，股票交 易对数据库和实时处理两者的功能均有需求，既需要数据库来支持 大量数据的共享，维护数据的一致性，又需要实时处理来支持起事 务与数据的定时限制。应用中的事务具有定时特性或对其有明显定 时限制的数据库系统称为实时数据库系统。嵌入式数据库系统是实 时系统，这种系统的正确性不仅依赖于事务的逻辑结果，还依赖于 该逻辑结果所产生的时间【1 9 1 。因此要求系统能高准确地预计事务的 运行时间，尽量提高系统的数据操作速度。 1 1 3 嵌入式数据库的应用 随着经济的发展，嵌入式数据库技术已得到学术界，工业界，军 事领域，民用部门等各方面的重视【2 2 】。总的来说，嵌入式数据库的 应用可分为水平应用和垂直应用。所谓水平应用是指应用方案能用 于多种不同行业，只需极少的定制工作；而垂直应用则针对特定行 业的应用，数据处理具有独特性【2 】。 ( 1 ) 水平应用口1 进行水平应用时，应用核心不需修改，只需较少的定制就可用 于多种不同行业，通用性较强。 数据库信息存取 移动用户通过前端嵌入式数据库应用的工具，直接向网络数据 库服务器提交查询，将检索到的结果缓存或复制到嵌入式数据库 中，进行本地管理。 场地内或场地问的移动应用 移动用户在场地内或场地间移动，保持与基地服务器的联系。 基于g p s 和g i s 的应用 通过地球同步通讯卫星( g p s 类) 传送地图信息或位置信息，或 通过发射器的信号广播( g i s 类) 来发送位置信息，各种位置信 息，环境信息以及其它的辅助资料可以保留在嵌入式数据库中。 现场审计和检查 移动用户在处理过程中要连接到受检查者的信息数据库进行检 查，同时更新被检查者的嵌入式数据库。 ( 2 ) 垂直应用1 2 j 垂直型应用具有明显的行业特殊性，数据处理具有独特的事务 处理特性，需要根据行业应用的特征进行客户端软件的开发工作。 金融行业的应用 主要涉及保险业，银行业，股票交易等。 零售业和分销行业的应用 硕士学位论文 移动设备上的应用软件通过无线网络与中央数据库联系并完成 现场处理。 卫生保健应用 包括远程会诊，紧急医疗服务，现场医疗数据收集等。 法律和公共安全 警务人员可在嵌入式数据库中记录和检索疑犯信息。 运输业 如可使用嵌入式数据库保存交通信息以指导司机驾驶。 信息家电领域的应用 信息家电是指所有能提供信息服务或通过网络系统交互信息的 消费类电子产品，它具有如网络浏览，视频点播，文字处理，电子 邮件，个人事物管理等信息服务功能【2 】。信息家电广泛地应用在生 产生活的各个领域，它们具有一个共同的特点：其内部必然存储和 管理数据，并且要与其它数据存储进行交互。显然，只有在信息家 电中融入数据库管理技术，才能满足信息家电管理数据，提供信息 的需求【2 】。现今人们对家电的灵活性和可控性提出了更高要求，家 庭控制中心为实现对联网家电及登录用户相关信息的管理，也需要 依靠嵌入式数据库技术。 1 1 4 国内外主要的嵌入式数据库产品 目前国内外市场上有很多种嵌入式数据库系统，而每种数据库 系统在技术与性能上都有不同的侧重点。只有通过分析比较各种嵌 入式数据库的特点，才能找到最能满足应用要求的嵌入式数据库。 1 1 4 1 国际主流产品 ( 1 )s y b a s es q la n y w h e r es t u d i o s y b a s e 为移动和嵌入计算提供了业界领先的完整解决方案 s y b a s es q la n y w h e r es t u d i 0 7 0 ，它的重要特性之一是实现了多种客 户端系统( 包括p c ，便携机，手持和智能设备) 到标准的后台企业 数据库系统的数据双向同步。它通过u l t r a l i t e 利用提交选项和 m o b i l i i l l ( 同步技术把企业数据扩展到p o s 终端，手持设备，智能应 用和嵌入系统中。根据u l t r a l i t e 提交选项为客户端系统定制数据库 应用，使得最小应用可小至5 0 k 【1 】【2 】【3 】【4 】。 ( 2 ) i b md b 2s a t e n i t ea n de v e r y p l a c ee d i t i o n i b m 公司在d b 2 通用数据库中推出了i b md b 2s a t e l l i t e 和 e v e r y p l a c e 版本。它支持移动计算功能，并提供移动办公用户与企 嵌入式主存数据库索引机制的研究与改进 业中心数据源保持同步的能力，很好地满足了企业移动办公的需求 【1 】【2 】 3 】【4 】。 ( 3 ) o r a c l el i t ee d i t i o n o m c l e 公司针对移动及嵌入式计算推出了o r a c l el i t e ，该产品 包括：0 r a c l el i t ed b m s ，o r a c l ei c o 皿e c t ，0 r a c l ew e b t o g o 。o r a c l e l i t ed b m s 可在w i 心汀，w i i l 2 0 0 0 ，w i n c e 和e p o cp a l m 平台上运 行，并支持j a v a 的存储过程和触发器。o r a c l ei c o 衄e c t 实现移动设 备和中央数据库的数据同步，支持各种网络传输协议包括n e t 8 ， h t t p 和文件系统传输。o m c l ew e b 。t o g o 是分布应用程序，可以将 w e b 内容分布到移动设备【2 j 3 1 4 】。 ( 4 ) s q ls e e r7 0 m i c r o s o r 的s q ls e r v e r7 0 可为用户提供包括业务运营，移动 计算，电子商务在内的可伸缩的商业解决方案1 】 2 】【3 】【4 1 。 ( 5 ) c 1 叫d s c a p e 3 o i n f o m i x 公司也由旗下的c l o u d s c a p e 公司推出了其移动解决方 案的最新版本c l o u d s c a p e 3 0 ，可以对包括从服务器到笔记本电脑， 甚至到轻型信息设备进行数据管理 1 j f 2 】f 3 】 4 j 。 ( 6 ) b e r k e l e yd b b e d 1 e yd b 是由美国的s 1 e e p c a ts o 腑a r e 公司开发的一套开放 源码的嵌入式数据库的程序库，它为应用程序提供可伸缩的，高性 能的，有事务保护功能的数据管理服务。b e r k e l e yd b 为数据的存取 和管理提供了一组简洁的函数调用a p i 接口【1 】 2 】 3 1 4 1 。 ( 7 ) s q l i t e s o l i t e 是一个简单易用，完全开放源码的嵌入式数据库管理系 统，它具有以下特性：支持a c i d 事务；零配置，无需安装和管理 配置；存储在单一磁盘文件中；数据库文件可在不同机器间自由共 享；内核精小；数据操作速度快；提供对事务功能和并发处理的支 持；独立，没有额外依赖2 】【3 】【4 1 。 1 1 4 2 国内主流产品 ( 1 ) k i n 曲a s e l i t e 小金灵嵌入式移动数据库系统k i n 曲a s el i t e 是人大金仓研发的 拥有自主知识产权的软件产品，具有适应多平台，微小内核，可定 制，支持s o l 查询等特点【1 】【2 】【3 【4 】。 ( 2 ) 东软o p e n b a s e m i n i o d e l l b a s em i n i 嵌入式数据库管理系统是东软集团研制开发的 o p e 出a s e 系列产品之一，具有微小内核，支持多种连接协议，提 供完善的数据同步功能等特点【l 】【2 】【3 】【4 1 。 硕士学位论文 1 2 主存数据库技术 1 2 1 嵌入式数据库采用的传统数据存储技术 当前，许多嵌入式数据库产品普遍采用的数据存储结构类似于 大型数据库中的基于磁盘的存储结构( d r d b s ) ，即将数据库以页 面为单位完全存放在磁盘上，当进行数据访问时，从磁盘调入包含 所需数据的页面，当提交事务对数据库的修改时再写入某磁盘页 面。嵌入式系统不具备像硬盘那样大容量的存储介质，大多使用闪 存作为外存设备，并且内存资源极为有限，这样在n a s h 和r a m 问 就会有频繁的数据调入调出操作，而嵌入式微处理器受体积和价格 的限制速度不高，从而导致数据操作的性能较为低下。 图1 1嵌入式数据库中的数据流向 嵌入式数据库通常用于实时数据采集，军事领域，航天系统等 对事务的执行时间有严格要求的环境中，事务调度的正确性依赖于 高效的处理和预测能力。基于f l a s h 的数据存储技术导致延迟时间 无法预测，不能满足对数据快速存取的要求，因此在嵌入式实时系 统中采用基于主存的存储策略是一种明智的选择。 1 2 2 基于主存的数据库的两种实现策略 当前，对于如何使用数据库系统中的主存空间提出了两种策 略：第一种是使用充分大的缓冲池，使得每个事务所需要的大部分 甚至全部数据都可以存放在缓冲池中，并根据任务的运行需要及缓 冲池中数据的状态来决定内外存数据交换的时机与对象。d e w me t a 1 ，s h a p i r o 和e l h a r d te ta l 在他们的工作中使用了这种方法。当使用 这种策略时，由于数据库的磁盘版本仍是主版本，因此尽量减少对 磁盘的访问次数仍是算法设计的主要目标【2 。部分人支持使用这种 策略，因为它具有以下优点【2 l 】： _ 只要对现有系统的缓冲池扩大即可，而改变缓冲池大小只需改变 d b m s 中的一个常量，所需的工作量很小； 一由于减少了对磁盘的访问次数，所以整个系统的性能有所提高。 嵌入式主存数据库索引机制的研究与改进 但它存在下列缺点：每次对数据库的访问都要通过缓冲池管理 器，由该管理器检查所需访问的页面是否位于主存中并进行地址计 算，在主存命中失败时要进行页面的调入，因此降低了数据访问速 度。 图1 2 第一种主存数据库实现策略。 另一种策略是由k r i s h n 锄u n h ye t a l 提出的完全使用主存存放数 据库( 即主存数据库系统m 砌) b sm a i nm e m o r yr e s i d e md a 协b a s e s y s t e m s ) 的策略阻j 。该策略需要对数据库管理系统进行重设计，例 如数据组织，查询优化，并发控制，恢复策略的算法和数据结构必 须重构建以提高内存和c p u 利用率。这种策略由于不用与磁盘和缓 冲池管理器打交道，大大提高了系统性能，是当前的研究焦点【2 。 图l 一3 第二种主存数据库实现策略 在这种策略下，磁盘仅存放数据库的备份，用于在主存数据库 发生故障时进行数据装入。 由于第一种策略每次数据访问都要判断缓冲池是否命中，且在 没有命中的情况下仍需与外存交互，所以虽然较基于磁盘的数据库 系统操作速度有所提高，但仍不能满足严格的时间限制和支持实时 数据，仅适用于软实时环境或非实时环境。第二种策略由于将数据 库存放在内存，仅在备份恢复时访问磁盘，大大减少了内外存i o 的次数，使数据操作性能大为提高。但这种策略假设内存可以容纳 整个数据库，对于内存资源极为有限的嵌入式系统是不可行的。下 面我们讨论在内存受限的数据库系统中的数据装入策略。 。图中的m d b 指主数据库，p d b 指与事务相关的部分数据库 硕士学位论文 1 2 3 内存受限的内存数据库的数据存取策略 1 - 2 3 1 内存受限的内存数据库的定义 设有数据库系统d b s ，d b 为d b s 中的数据库，d b m n ) 为在时 刻t d b 在内存中的数据集，d b m ( t ) d b 。t s 为d b s 中所有可能 的事务的集合，a t ( t ) 为在时刻t 处于活动状态的事务集，a t ( t ) t s 。d t ( t ) 是事务t 在时刻t 所操作的数据集，d t ( t ) d b 。若在 任一时刻t ，均有： v t a t ( t )d t ( t ) d b m ( t ) 成立，则称d b s 为一个内存数据库系统，简写为m m d b s ；d b 为 一个内存数据库，简写为m m d b 【8 】【9 】 1 0 】。 直观地说，内存数据库系统就是数据库的工作版本常驻内存的 数据库系统【19 ，但它并不要求任何时刻整个数据库都能存放在内 存，所以还是要使用外存来存储内存放不下的那部分数据及用于恢 复的备份，即m m d b s 还是要处理i 0 。 1 2 3 2 内存受限的内存数据库的数据装入策略 由于嵌入式系统中的内存并不能容纳全部的外存数据，因此内 存数据库在初始化的时候，需要选择装入最应该被装入的数据以提 高内存的命中率【9 】。 通常采用对事务进行静态预分析的初始化装入策略，将分析好 的事务排成一个队列，从队列的头部开始进行事务数据的装入，直 到内存容量不够。队列的形成策吲9 】如下： 队列的开始是随机发生的硬实时事务； 周期事务： 内存数据库初始化时就应该把数据调入内存，否则会超过截止期 的硬实时事务； 在内存初始化时就应该装入的软实时事务； 随机发生的软实时事务： 如果在前三类事务数据的装入过程中，内存耗尽，则内存数据 库初始化失败。如果在后两类事务数据的装入中内存耗尽，则内存 数据库虽初始化成功但性能不高【9 j 。 内存数据库初始化成功后，系统开始运行。如果接纳一个事务 后发现其数据不在主存，仍然要进行数据装入。为了让系统能正常 运行，应尽量减少因数据装入而超过截止期的事务数目【9 】。在运行 期维护一个己被装入主存的事务队列，每当主存命中失败需装入新 事务时，将队列头部的事务数据换出主存，使用腾出的空间装入新 嵌入式主存数据库索引机制的研究与改进 事务，并将新事务链接至队列的尾部。这就保证先换出存取频率低 的数据，节省了系统的维护代价，提高了主存的命中率。 1 2 4 主存数据库的特点 主存数据库系统以传统的基于磁盘的数据库系统为基础，并且 与磁盘数据库系统一样都要满足一些基本要求：要求数据库系统提 供数据的独立性，使应用程序尽可能从数据表示和存储的细节中独 立出来，即逻辑独立性与物理独立性；要求对数据的快速有效访 问；要求数据的完整性，通过d b m s 实施完整性约束；要求提供对 数据的管理，并发访问，恢复功制1 8 】。 在嵌入式数据库中采用基于主存的新存储策略，应完全打破基 于外存的传统策略的设计宗旨，对于物理数据结构，存取方法，查 询处理及优化，并发控制和数据库恢复都应根据主存数据库的特点 进行重设计【l6 。基于主存的数据库和基于磁盘的数据库的主要区别 体现在以下几个方面： 存储介质 在d r 工) b s 中，数据库的工作版本存放在外存中，每次数据操 作都涉及内外存的数据交换。而在m 仍b s 中，数据库的工作版本 存放在内存中，事务可以直接在内存存取数据，消除了执行过程中 的i 0 瓶颈问题，从而极大提高了系统的性能和吞吐量。 算法设计目标【l 6 j 在d r i ) b s 中，i o 是系统的瓶颈，系统的算法设计目标是在减 少对磁盘的访问次数的同时尽量减少对磁盘空间的占用量，而在 m 仍b s 中，外存的i o 不再是瓶颈，系统的算法设计目标是在减 少内存空间耗用量的同时尽量提高c p u 的利用率。 系统特性【3 3 】 内存和外存系统具有不同的特性，主要体现在： 夺主存是易失性的，而外存是永久性的，当系统断电时，主存所存 信息马上丢失，通电后也不会恢复。而外存所存信息不会丢失通 电后仍可使用： 令内存和磁盘在存取时间上存在若干数量级的差别； 令主存的随机访问速度很快，而外存仅适于顺序访问。 夺存储格式不同： 令存取方式不同，内存可由处理器直接存取而磁盘则不能。 主存的随机访问速度与外存存在数量级的差异，这就对 m 旧b s 的索引结构设计带来重大影响。在d r d b s 中，通常在索 引中直接存放关键字或数据，并且相关数据对象以聚集的形式存放 在一起以适应磁盘的块存取【13 1 。由于主存是随机存取设备，故可将 硕士学位论文 记录分散存储在主存的不同位置并且面向页的数据结构不再重要 u 引。又因主存的指针操作速度相当快，所以只需在索引中存放指向 记录的指针即可。这样带来了以下好处 2 1 ： 单个记录指针既可以提供对记录整体的访问，也可以提供对记录 某个属性域的访问。由于不需要在索引中存储键或数据，只需存 储指针，所以大大节约了索引所占用的内存空间【l l 】； 消除了在索引结点中处理记录中较长长度的属性域，可变长度的 属性域，空属性域，与地域相关的属性域，键或数据的压缩技术 带来的复杂度【1 i j ； v ，在结点中移动指针的开销要比移动键或数据小很多【l l 】； 当允许存放重复记录时，只需在内存中存储一个记录，在结点中 使用多个指针指向该记录即可，这样节省了内存空间； 由于单个记录指针可以提供对所指向记录中任何域的访问，因此 大大减少了多域记录的访问开销。 并发控制【1 6 j 在d i b s 中，数据的加锁开销远小于它的处理开销，因此为 提高并发度通常采用细粒度锁策略( 如属性级) 。而在m 恸s 中，数据的加锁开销与处理开销相当，一般采用较大粒度锁( 如元 组级或关系级) ，从而并发性下降，但减轻了并发机构的负担，使 系统的总体性能得到提高。 查询处理 1 6 】 由于d i m b s 的瓶颈是外存i o ，故查询处理的优化策略以减少 对外存的访问次数为主要目标，而在已调入内存的页面中的查询开 销无关紧要。而在m 佃b s 中，数据比较开销在各种开销中所占比 例较大，因此查询处理算法应尽量减少比较次数。 在d m b s 中尽量存储查询临时结果，以空间换时间。而在 m m d b s 中尽量不存储临时结果，以时间换空间。 数据组织 由于磁盘等外存的顺序存取远快于随机存取，因此d r d b s 的 性能受数据组织的影响很大。d ) b 通常使用“记录群集”技术，而 在主存中，顺序存取和随机存取是同一个速度，因此m m d b s 的性 能对数据组织相对不敏感【1 8 】。 数据库恢复【1 6 1 b s 的致命问题是内存的易失性，又由于内存由c p u 直接 存取，使得m h b 比d ) b 更易受到操作系统或应用软件的直接 伤害u 川。所以对m m d b s 来说，数据库恢复比d r d b s 更重要，恢 复的频度也高得多。 对实时事务的支持 嵌入式主存数据库索引机制的研究与改进 实时应用中的事务及其数据都有定时限制，要求系统能高准确 地预计事务的运行时间。但在d r d b s 中，存在许多不可预计的因 素，如外存存取，内外存的传递，缓冲区管理，排队等待及锁的延 迟使得事务的实际平均执行时间和最坏情况下的执行时间估算相差 很大。而在m h 仍b s 中，工作数据库存放在内存，可以较准确地估 算和安排事务的运行时间，具有较好的动态可预报性。 1 3 适应于嵌入式主存数据库的索引机制 由于m m d b s 能克服d r d b s 的数据操作延迟时间难以预测的 缺点，提供对实时事务的有效支持，已成为嵌入式实时数据库的最 佳选择。由于m m d b 自身的特点和嵌入式系统内存受限，研究一种 适合的索引机制有利于提高存取效率，改善系统性能。 在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 来说存储效率太低，所以 必须开发适合于内存直接访问特性的存取方法，且在处理时空关系 时，空间应为第一位u 川。 目前，m 佃b s 使用的索引结构有多种形式的h a s h i n g 技术和 a v l 树结构。h a s h i n g 技术可提供极快的直接存取，但它对空间的 利用率较低，易造成数据在内存空间中分布不均及算法复杂等问 题。a v l 树是一种使用二叉搜索方式的索引结构，其检索操作的时 间复杂度仅为0 ( 1 0 9 2 n ) ( 其中n 为树的深度) ，而且无需进行算术 运算，对树的修改操作通常仅影响叶结点。因此，它具有较高的存 取性能。a v l 树的缺点是其存储效率较低，每个结点只存储一个元 素，而且每个元素都带有控制信息及两个指针的附加信息【l 。 考虑内存存取特性，综合a v l 树和b 树的优点，提出了t 树 索引结构。t 树是一棵在一个结点中存放多个元素的平衡二叉树。 它既保留有a v l 树上的二又搜索特性，又具有b 树的优良存储和 修改性能【2