（计算机系统结构专业论文）嵌入式内存数据库存储与索引算法研究.pdf

i i iii ii i i iiiu l li ju i y 17 3 9 0 3 0 广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得 的成果和相关知识产权属广西大学所有。除已注明部分外，论文中不包含其 他人已经发表过的研究成果，也不包含本人为获得其它学位而使用过的内 容。对本文的研究工作提供过重要帮助的个人和集体，均已在论文中明确说 明并致谢。 论文作者签名： 马兰沙加年6 月叫日 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 酌口时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 做作者签名马呈 导师签名批冲年石月 7 日 的分析和研究。首先，根据传统的区段式、散列、t 树和b 树算法，实现 数据存储和索引的各功能模块，将其应用在模拟l i n u x 嵌入式系统开发平台 的环境上测试并分析其性能。其次，针对e m m d b 系统的性能要求，分别 提出存储与索引的改进算法。一是在传统区段式存储算法的基础上，结合 类可扩散列思想提出的类可扩散列区段式算法( e h a s ) 。该算法在段实存 数据页内采用类可扩散列方法进行记录数据的定位，以记录的一个主键字 段值取模得到定位关键值和三元组。二是在传统t 树索引算法的基础上， 结合b 树非叶子节点作多路分支目录的思想，提出具有优先匹配目录的t 树算法( p m c t - t r e e ) 。该算法将t 树划分为若干有父亲孩子关系的块，再 提取各t 树块阈值构造优先匹配目录( p m c ) ，进而创建t 树与p m c 目录 的关联关系构造索引。通过索引查询时先在p m c 中定位到块再在该t 树块 中查找。 通过在w i n d o w sx ps p 3 上应用n e t b e a n s6 0 、c y g w i n 的模拟l i n u x 嵌 入式系统开发平台环境进行性能测试和分析，实验结果表明e h a s 算法能 够保持原算法较好的空间利用率，提高平均存储响应时间，且提供在一定 条件下的常数级查询功能。p m c t - t r e e 算法虽然由于增加了p m c 目录而略 多的占用了主存空间资源，但有效地加快了平均查询响应时间，且能保持 较好的稳定性。研究表明，e h a s 和p m c t - t r e e 算法均是能较好的符合 e m m d b 性能要求的方法。 关键词：嵌入式内存数据库；索引；存储；t 树；区段式；类可扩散y o ；b 树 h a sm o r e i n c o m p a r a b l ea d v a n t a g e s a n dv a s t a p p l i c a t i o np r o s p e c t s t h a n t r a d i t i o n a ld a t a b a s e s d a t as t o r a g ea n di n d e x i n ga r eo n eo ft h ec o r et e c h n o l o g i e so fe m m d b s y s t e m ，w h i c hp l a y sad e c i s i v er o l ei np e r f o r m a n c e i nt h i sp a p e r , w ew i l ld oa f u r t h e r a n a l y s i s a n dr e s e a r c hf o r t h ep r i n c i p l ea n dt r e n d so ft h e s et w o t e c h n o l o g i e s f i r s t l y , a c c o r d i n gt ot h et r a d i t i o n a la r e a - s e g m e n t s ，h a s h i n g ，t - t r e e a n db t r e ea l g o r i t h m s ，w ea c h i e v ee a c hf u n c t i o n a lm o d u l e so fd a t as t o r a g ea n d i n d e x i n g ，a n da p p l yt h e mt od e v e l o p m e n tp l a t f o r mo fl i n u xe m b e d d e ds y s t e m f o re n v i r o n m e n t a lt e s ta n dp e r f o r m a n c ea n a l y s i s s e c o n d l y , w ep r o p o s et w o i m p r o v e da l g o r i t h m s o ft h e s t o r a g ea n di n d e x i n g ，b a s e do nt h es y s t e m p e r f o r m a n c er e q u i r e m e n t so fe m m d b o n eo ft h e mi s a ne h a ss t o r a g e a l g o r i t h mc o m b i n i n gw i t hq u a s i e x t e n d i b l eh a s h i n g ，b a s e do n t r a d i t i o n a l a r e a s e g m e n tm e t h o d i tl o c a t e sr e c o r d sb yq u a s i e x t e n d i b l eh a s h i n gm e t h o d i n t od a t ap a g e s ，a n dc o m p u t e sap r i m a r yf i e l dk e yi n t oam o d u l u sa n dat r i p l e t h e n ，b a s e do nt r a d i t i o n a lt - t r e ei n d e xm e t h o da n dc o m b i n e dw i t ht h ei d e ao f m u l t i b r a n c ho fb - t r e en o n l e a fn o d e ，a n o t h e ra l g o r i t h mt h a ti sap r i o r i t ym a t c h c a t a l o gt - t r e ei n d e xa l g o r i t h mc a l l e dp m c t - t r e ei sp r o p o s e d t h i sa l g o r i t h m i i i d i v i d e st - t r e ei n t oan u m b e ro ft - t r e eb l o c k sw i t ht h ef a t h e r - c h i l dr e l a t i o n s h i p ， a n de x t r a c t st h r e s h o l dt oc r e a t ep r i o r i t ym a t c h i n gc a t a l o g s t r u c t u r e ( p m c ) w h e ns e a r c h i n gr e c o r d s ，i ts h o u l dq u e r yp m ci nt h ef i r s ta n dt h e nn a v i g a t et o t h eb l o c ki nt h et - t r e e a p p l yt h e mt od e v e l o p m e n t p l a t f o r mo fl i n u xe m b e d d e d s y s t e mf o re n v i r o n m e n t a lt e s ta n dp e r f o r m a n c ea n a l y s i s i nw i n d o w sx ps p 3 ，w i t he m b e d d e ds y s t e m d e v e l o p m e n tp l a t f o r mo f s i m u l a t i o nl i n u xb yt h ea p p l i c a t i o n so f n e t b e a n s6 0a n d c y g w i n ，c a r r y i n go n p e r f o r m a n c e t e s ta n da n a l y s i s e x p e r i m e n t a lr e s u l t si n d i c a t et h a te h a s a l g o r i t h mh a sg o o ds p a c eu t i l i z a t i o nr a t e ，i m p r o v e st h ea v e r a g es t o r a g er e s p o n s e t i m e ，a n dp r o v i d e sac o n s t a n tt i m eq u e r yf u n c t i o nu n d e rc e r t a i nc o n d i t i o n s r e s u l t sa l s oi n d i c a t et h a ta l t h o u g hp m c t - t r e ea l g o r i t h mo c c u p i e sal i t t l em o r e m a i n - m e m o r ys p a c ef o rp m c ，a c c e l e r a t e st h ea v e r a g eq u e r yr e s p o n s et i m ea n d m a i n t a i n sa g o o ds t a b i l i t y r e s e a r c hs h o w st h a te h a sa n dp m c t - t r e e a l g o r i t h m sa l lc a nw e l la c c o r dw i t he m m d bp e r f o r m a n c er e q u i r e m e n t s k e yw o r d s ： e m m d b ；t - t r e e ；i n d e x ； s t o r a g e ；a r e a s e g m e n t ； q u a s i - - e x t e n d i b l eh a s h i n g ；b - - t r e e i v 目录 摘要i a b s t r a c t 1ii 第一章绪论。1 1 1 课题研究的背景及意义1 1 1 1 课题研究背景l 1 1 2 论文选题的目的和意义l 1 2 研究内容和主要创新点2 1 2 1 研究内容。2 1 2 2 论文的主要创新点2 1 3 论文的组织结构3 第二章m m d b 、e b d b 与e m m d b 概述。5 2 1m m d b 简介5 2 1 1m m d b 背景及技术发展5 2 1 2f a s t d b 特点7 2 2e b d b 简介7 2 2 1 嵌入式系统与e b d b 背景7 2 2 2s q l i t e 特点8 2 3e m m d b 简介9 2 4 本章小结1 0 第三章e m m d b 的类可扩散列区一段式算法一12 3 1e h a s 算法描述12 3 1 1e m m d b 的数据存储问题描述1 2 3 1 2e h a s 算法描述1 4 3 1 3e h a s 算法存储步骤l7 3 1 4e h a s 算法以存储主键字段值的查询描述18 3 1 5e h a s 算法特点2 0 3 2 实验结果分析2 0 3 2 1 实验环境概述2 0 3 2 2e h a s 算法分析与评价2 0 3 3 本章小结2 3 第四章e m m d b 的具有优先匹配目录的t 树算法2 4 4 1p m c t - 仃e e 算法描述2 4 4 1 1e m m d b 数据索引问题描述2 4 4 1 2 创建索引2 6 4 1 3 利用索引进行查询的步骤3 0 4 1 4 更新p m c 目录策略3 3 4 1 5p m c t t l 船算法特点3 4 4 2 实验结果分析3 5 4 2 1 实验环境概述3 5 4 2 2p m c t 仃优算法分析与评价3 5 v 4 3 本章小结。3 7 第五章总结与展望3 9 5 1 工作总结。3 9 5 2 工作展望3 9 参考文献。4 1 致谢4 5 攻读硕士期间参加的科研项目4 7 攻读硕士期间公开发表录用的学术论文4 7 v i 广西大掌硕士掌位论文嵌入式内存数据库存储与索引算法研究 1 1 课题研究的背景及意义 第一章绪论 1 1 1 课题研究背景 随着计算机与电子行业硬件的发展，内存的容量逐渐增大而价格逐渐下降，使将数 据库部分或者完全地置于主存中的设想能够变为现实【l 】。现代的工业智能设备应用范围 越来越广，已经在工作、生活上逐步替代人们的手工劳动，并且能更快、更好、更标准 的进行作业。由于传统的磁盘数据库( d i b ) 的主体数据库驻于磁盘，事务处理往往 涉及频繁的i o 操作，越来越难满足未来数据库系统对高性能数据处理的需求。而应用 于工业控制的嵌入式系统( e m b e d d e ds y s t e m ) 受硬件条件的限制，为了达到高速运作 的同时进行高速的数据处理和存储要求，多采用内存数据库( m a i n m e m o r yd a t a b a s e ， m m d b ) 的方式口j 。m m d b 的数据库主体常驻内存，只进行很少的与磁盘间i o 用于备 份或者恢复数据库，它能够很好的满足实时数据的处型蛐】。除此之外，还要通过针对 性开发，使实现适合工业智能控制应用的嵌入式内存数据库( e m b e d d e dm a i n m e m o r y d a t a b a s e ，e m m d b ) 。这是一种非常有价值和广阔前景的数据库，是近年来研究的热点。 嵌入式应用通常有实时性要求，即系统相当一部分功能有时间上的限制。对于实时 系统来说，如果逻辑和时序出现偏差将会引起系统的严重后果，可以看出稳定性、可靠 性与高效性是其必须具备的特剧7 1 。以性能很高的内存实时数据库e x t r e m e d b 为例，其 数据读写操作均在微秒一级，其他m m d b 一般是毫秒级。e x t r e m e d b 在使用的时候， 基本开销只有5 0 k - - 1 0 0 k 尺寸，管理数据的效率高达7 0 - 8 0 ，而o r a c l e 等商业数 据库效率在1 0 - 2 0 左右。 1 1 2 论文选题的目的和意义 e m m d b 后台支持技术模块中，包括了数据存储组织和索引算法的研究。为保证数 据库体积小，数据处理的高效性、准确性和一定程度上的实时性，这两种技术机制设计 的好坏直接影响整个数据库的性能【8 】。m m d b 系统的存储算法主要采用区段式及多事 务内存分配主要应用的影子内存方法，索引算法主要采用b 树及b + 树等演化树、t 树 及p 树等演化树、r - 树及其变形树、缓存c s s 树及c s a t r e e 等、散列算法等【9 。1 2 1 。虽 然e m m d b 采用m m d b 方式，但它更要满足具有特殊性和多样性的嵌入式系统应用的 要求，而大多m m d b 系统整体上仍沿用有传统d r d b 的技术特点，不能简单移植到嵌 入式系统环境中使用，因此e m m d b 可以说只是结合m m d b 与e b d b 的优点但是需要 改进甚至重新开发的一种小型数据库系统【1 3 d5 1 。由于m m d b 的区段式存储算法、t 树 索引算法、散列技术等灵活性强且效率相对较高，因此可以根据嵌入式系统的特点将上 嵌入式内存数据库存储与索3 l 算法研究 述两种技术机制进行改进扩展使之成为体积较小，形成组件化的结构模块，满足工业智 能设备控制应用的上数据处理的实时性、高效性等性能要求，进而实现并提高整个 e m m d b 的性能。 本选题的独创性在于研究以m m d b 区段式存储及t 树、b 树索引技术为基础的， 适合应用于e m m d b 系统数据处理后台支持架构的存储与索引算法。根据m m d b 技术 和嵌入式系统应用环境要求，提出改进的存储算法是类可扩散列区段式存储算法 ( e h a s ) ，改进的索引算法是具有优先匹配目录的t 树算法( p m c t - t r e e ) 。在模拟l i n u x 嵌入式系统开发平台环境中实验表明，两算法均具有较优的空间利用率和较快速的响应 时间，能够较好的满足e m m d b 应用的性能要求。 1 2 研究内容和主要创新点 1 2 1 研究内容 ( 1 ) 对m m d b 的存储算法进行研究，结合e b d b 的应用特点进行改进和优化， 以满足e m m d b 对主存空间利用率较高的性能要求，同时考虑弥补区段式方法未对记 录数据进行初步整理分类的不足。重点研究区段式数据组织策略，并结合类可扩散列 的数据定位方法进行改进和优化； ( 2 ) 对t 树和b 树及其演化树索引算法进行研究，将这两种方法相结合进行改进 和优化，设计新的索引结构及查询策略，重点研究t 树节点结构及节点间关系、b 树非 叶子节点结构和目录分支间的关联性的改进和优化，以在对主存空间损失较少的前提下 较有效地提高数据索引查询的响应时间； ( 3 ) 存储和索引机制的有效性和性能分析：采用w i n d o w sx ps p 3 、n e t b e a n si d e 6 0 1 及c y g w i n 架构的模拟l i n u x 嵌入式系统开发平台环境，采用l i n u x 2 4 内核，用c 语言【1 6 - 1 1 7 】实现e h a s 存储及p m c t - t r e e 算法，做性能分析及评估。重点分析存储机制的 实存空间利用率，平均存储响应时间，以存储主键字段值为关键字的查询平均响应时间， 索引机制以查询操作为代表分析其平均查询响应时间、内存空间利用率并给出时间复杂 度等算法性能，得出结论。 1 2 2 论文的主要创新点 ( 1 ) 改进区段式的存储方式，并结合类可扩散列的数据分类定位思想，提出了类 可扩散列区段式算法( e h a s ) 。该算法保证了区、段、实存数据页适合的内存空间大 小的良好分配，通过设置类可扩散列策略的较佳的根键值的比特位数，降低数据间的聚 合度和散列冲突程度，通过冲突链表页能够有效地解决冲突记录存储问题，使e h a s 算 法在性能上有较快速的平均存储响应时间、较好的内存空间利用率，并且提供一种由采 用散列定位而能够实现的常数级的依主键为关键字的查询功能，即使该算法能够在时间 和空间上达到一个良好的平衡。 2 广西大掌硕士学位论文嵌入式内存数据库存储与索3 i 算法研究 ( 2 ) 改进t 树算法，在分析其节点结构及树形关系的基础上，结合b 树非叶子节 点多路分支目录的思想，提出查询响应时间更快速的改进的索引算法具有优先匹配 目录的t 树算法( p m c t 仃e e ) 。该算法包括三部分，分别是创建索引，利用索引进行查 询和更新维护目录。首先是在创建的t 树索引基础上，将整个t 树分为适当数量的块， 块内节点数取决于t 树的规模，由各t 树块中抽取边界阈值构造优先匹配目录( p m c ) ， p m c 目录整体上也是一种多路分支树形结构，由t 树和p m c 目录相结合构成索引结构。 利用索引查询时先在p m c 中定位到t 树块，再在该块内查找。通过较好的维护及更新 目录的策略，能够使p m c 节点结构简洁并且目录整体的规模也不会过于庞大，从而能 够保证p m c t - 仃e e 算法有有效合理的内存空间利用率和快速的平均查询响应时间，具有 良好的时间复杂度和查询的稳定性。 1 3 论文的组织结构 本文的研究工作主要是围绕e m m d b 系统的数据存储及索引算法改进来展开的。组 织结构安排如下： 第一章，作为全文的绪论，主要介绍了m m d b 及e m m d b 的发展情况和主要应用 领域，嵌入式系统的特性及应用要求，e m m d b 的总体架构及其后台支持模块的主要技 术数据存储及索引普遍采用的算法。阐述了论文的主要研究内容及创新点，最后概 要说明全文的总体组织结构。 第二章，对m m d b 、e b d b 与e m m d b 三种类型的数据库及其与本论文研究相关 的部分技术做一个系统地介绍。主要从这三类数据库的产生背景、技术特性、体系结构 和普遍被认可采用的存储及索引算法几个方面阐述。另外还例举了两个小型数据库 f a s t d b 和s q l i t e ，用来说明存储与索引算法在实际产品中的应用情况。 第三章，基于广泛适用于m m d b 的区段式存储算法，结合类可扩散列由根键值分 类定位数据的思想，提出了一种新的适用于e m m d b 的类可扩散列区段式存储算法 ( e h a s ) 。详细描述了e h a s 算法并阐述了数据组织结构的实现策略及存储步骤，分析 了散列冲突的解决方案及装填因子的影响因素。在模拟l i i 嗽嵌入式系统开发平台环境 中实现算法，该环境采用l m u x 2 4 内核，在空间利用率与平均存储响应时间两大方面对 e h a s 算法和典型的区段式算法做性能上的分析和比较。 第四章，针对目前普遍被认可的适用于m m d b 的t 树索引算法和较适用于e b d b 的b 树索引算法做分析、总结，提出了一种改进的适用于e m m d b 的索引算法一具 有优先匹配目录的t 树算法( p m c e e ) 。详细描述了p m c t - t r e e 的数据索引结构的建 立并阐述了它的查询操作的详细步骤，另外也给出了维护和更新p m c 目录的总体概括 性的实现步骤。采用与第三章同样的模拟“n u x 嵌入式系统开发平台环境实现算法，在 内存空间利用率、平均查询响应时间两大方面对p m c t - 仃e e 算法和典型的t 树算法做性 能上的分析和比较，同时也给出了p m c t 慨算法的查询时间复杂度。 3 广西大掌硕士掌位论文 嵌入式内存数据库存储与索弓i 算法研究 第五章，对论文全篇研究工作的总结，综述在适用e m m d b 系统数据处理模块的存 储和索引算法研究领域获得的成果，同时指出了现有工作的局限性及可能的进一步的深 入和扩展的研究方向。 4 嵌入式内存数据库存储与索3 i 算法研究 第二章m m d b 、e b d b 与e m m d b 概述 2 1m m d b 简介 2 1 1m m d b 背景及技术发展 m m d b 与传统数据库d r d b 的主要区别在于其被承载的硬件载体非磁盘而是有较 高速处理能力且地址线性的内存【l 引。m m d b 在应用上是数据库主体或部分常驻内存， 相对传统d r d b 来说，省去大量与外存的i o ，所以其运行速度要快很多【1 9 】。m m d b 也是在硬件发展的前提下，顺应了越来越高的数据处理速度的需求发展而出现的【2 0 】。目 前国外已有几种商业化的m m d b 产品，如o r a c l e 甲骨文公司的t i m e s t e n ；韩国 a l t i b a s e 公司中国总代理南大通用数据技术有限公司的产品a l t i b a s e ；美国 m c o b j e c t 公司的功能强大的实时数据库e x t r e m e d b ，它同时也是e b d b ，价格非常昂贵。 上述产品在国内m m d b 的应用主要在通信等行业，这表明m m d b 在国内的应用只是 起步阶段。另外，从成本及技术上考虑，更适合于工业控制、小型智能设备等的紧凑型 数据库主要有：b e r k e l e y d b ，s q l i t e ，f a s t d b 等。 索引技术一直是数据库技术领域研究中的重要课题之一。在现有的成熟的数据库管 理系统产品中，e x t r e m e d b 提供多种数据库a p i 包括h a s h 索引、树索引等；b e r k e l e y d b 提供了b 树、h a s h 文件组织、定长队列和变长记录四种文件存储方法，查找数据可以 直接进行哈希或b 树索引：f a s t d b 采用t 树及h a s h 的索引方式，目前普遍认为最适用 于m m d b 的索引结构主要是t 树，其演化树代表有t 宰树等【2 1 。2 3 1 。t 树的查找时间复杂 度为o ( 1 0 9n ) 级别。t 树节点结构及节点之间组织结构如图2 1 和图2 2 所示。 c o n t r o li n f o 术p p a r e n t k 0k 1k 2k m 木p l c h i l d宰p r c h i l d 图2 - 1t 树节点结构图 f i g 2 - 1t - t r e en o d es t r u c t u r ed h a r t 5 广西大掌硕士掌位论文 嵌入式内存数据库存储与索3 i 算法研究 c o n t o li n f 0 幸p p a r e n t k d k ik 2虹 p l c h i l d事p r c h i l d c o n t o ii n f o p p a r e n t k dk ik 2k m 宰p l c h i l dp r c h i l d c o n 仃o li n f 0 幸p p a r e n t l k d k ik 2虫m 木p l c h i l d宰p r c h i l d 图2 - 2 t 树节点之间组织结构图 f i g 2 - 2t - 仃n o d e so 唱a n i z a t i o n a lc h i n 由于t 树是a v l 树的变种，又综合了b 树节点容纳多关键字的优点，t 树可看作 是一种在一个节点内包含多关键字的平衡二叉树。但它也继承了a v l 树因节点间需要 平衡调整而导致系统开销较大的缺点，因此针对减少平衡调整次数对t 树节点的改进已 研究有几种方法：在t 树节点结构中增加一个尾指针域，改进后称为t - t f i l 树；在多维 索引情况下结合t 树与网格降维的索引方法；t 树节点结构中增加两个指针域，指向该 节点在中序遍历顺序上的前驱节点和后继节点，改进后称为t 宰宰树【2 1 t2 2 2 4 】等。今后对t 树的改进仍会体现在节点结构变化、t 树整体组织形式的改进及减少平衡调整频率上【2 习 和与其他索引方法相结合的改进等方面。 另外，散列索引也是被重点研究及应用的方法，由于其定位过程不用进行关键字比 较，数据存储位置与关键值有一个确定的对应关系，因此有较高的查找效率，其查找成 6 广西大掌硕士掌位论文嵌入式内存数据库存储与索3 l 算法研究 功时间复杂度为o ( 1 ) 【2 6 1 。目前对其已有多种改进：针对电信网管数据库系统，表采 用一次性静态连续分配空间来保证稳定性的h a s h 索引；适用于f l a s h 存储设备，数据插 入和删除操作根据地址空间的增大或减小动态改变哈希函数的动态哈希索引；增加缓存 桶于内存，减少数据桶数量及分裂次数，有效降低空间浪费的改进的可扩展h a s h 缓存 算法【1 4 一。7 】等。h a s h 索引应用范围较广，选择适合的哈希函数和有效的冲突处理方法是 关键。另外，散列技术不仅用于快速索引也是用于存储的方法之一【1 2 引。 2 1 2f a s t d b 特点 f a s t d b 是一款高效率的m m d b ，实时性好，有较快速的数据查询性能。它是以c + + 语言设计的数据库系统，采用类s q l 语句访问的方式。数据查询操作执行在应用程序 的任务中，以类为结构构建数据库中的表。f a s t d b 采用t 树索引和散列索引算法，以 可嵌套定义而非多维定义的动态数组保存表记录，有效地利用了内存空间，此时表记录 是作为类的对象的实例的意义存在的。f a s t d b 算法能允许相当准确地计算出查询一个 表内记录的查询响应时间的平均值和最大值，f a s t d b 采用的查询算法种类及其查询最 优时间复杂度及查询最差时间复杂度如表2 1 所示。 2 2e b d b 简介 表2 - 1f 嬲t d b 索引性能 t a b l e2 - 1f a s t d bi n d e x m gp e r f o r n l = c e t y p eo fs e a r c ha v e r a g e m a x i m a l s e q u e n t i a ls e a r c ho ( n )o ( n ) s e q u e m i a ls e a r c h 奶t l ls o r t m go ( n 奉l o g ( n ) ) o ( n 奉l o g ( n ) ) s e a r c hu s i n gh a s hr u b l e o ( 1 )o ( n ) s e 鲫c hu s i n gt _ t r e c o ( 1 0 9 ( n ) )o ( 1 0 9 ( n ) ) a c c e s sb yr e f e r 饥c e o ( 1 )o o ) 2 2 1 嵌入式系统与e b d b 背景 嵌入式系统是与通用计算机系统有很大差别的。使用为特定用户群设计的功能特定 且单一的处理器，将计算机、半导体、电子技术与特定行业的应用技术相融合，整个系 统要求功耗低、运行效率高且体积小巧【2 9 1 。因是为实际应用而生，所以其功能面向的市 场需求必须要明确，并且要保证有较长的使用周期性。以往的嵌入式系统被设计完成大 多都以一个整体体系存在，对程序的修改一般是不能做到的而是需要重新开发。随着嵌 入式系统变得越来越复杂化，对其进行结构化设计，即模块化的分别开发再组合为一个 整体系统的形式的发展已是必然趋势，同时系统程序的更新升级也将变得更容易。 根据i e e e ( 国际电气和电子工程师协会) 的定义，嵌入式系统是“控制、监视或 者辅助设备、机器和车间运行的装置 【2 9 】。可以看出嵌入式系统是软硬件的综合体，还 7 嵌入式内存数据库存储与索3 i 算法研究 可以包括机械及自动化等装置，但是上面定义的描述有些偏向表面化。目前国内普遍认 同的定义是：嵌入式系统是以应用为中心，以计算机技术为基础，软硬件可裁剪，适应 应用系统对功能、可靠性、成本、体积、功耗严格要求的专用计算机系统，且一般由高 性能微处理器、外围硬件设备、嵌入式操作系统以及用户的应用程序四个部分组成【3 0 1 。 嵌入式系统在工业控制、消费电子、通信、军事、智能机器人等领域都有非常广泛的应 用，可以说它早已渗透到大众普遍的生活中。 通常的嵌入式系统与通用计算机系统相比具有以下特点【2 9 】： ( 1 ) 面向特定应用的嵌入式c p u ，工作在为特定用户群设计的o s 中，具有低功 耗、体积小、集成度高等特点； ( 2 ) 融合先进的计算机、半导体和电子技术到各行各业中，真正整合于硬件之上 的软件系统，涉及到的知识领域极为广阔，有特定优势的性能和适用对象； ( 3 ) 硬件和软件都是精简的，力求以较低的成本实现最大化的实用价值； ( 4 ) 系统软件是依托在实际的产品硬件设备之上，不同产品之间的系统差别较大， 升级缓慢，生命周期长； ( 5 ) 系统软件大多固化在硬件设备中，而不是存储在磁盘等载体中： ( 6 ) 嵌入式系统本身采用交叉编译的平台环境开发，交付使用后一般不可更改。 e b d b 发展至今已有三十多年的历史，应用领域包括军事、消费类电子、通讯、医 疗设备、工业智能控制等十分广泛。由于e b d b 应用环境与硬件设备关系紧密，在早期 的e b d b 系统开发中主要考虑的是应用对象的特殊性，因此e b d b 多以整体数据库形 式存在，并且仅适用于所开发应用的设备，几乎不可能在原有数据库上做升级更别3 l 】。 随着嵌入式应用中需求增多，数据库系统也更加庞大，以整体e b d b 的开发也变得复杂 化，周期也会拉长。因此e m d b 的组件化发展是降低成本、缩短开发周期的有效方法。 并且随着嵌入式系统发展逐渐成熟和标准化，移植性和跨平台性增强，将e b d b 在结合 嵌入式系统的基础上应用是必然的发展趋势，目前尤其在消费类电子和工业控制领域的 应用已十分广泛。e b d b 的应用在我们的生活中随处可见，它在实时性、稳定性、移动 性和可裁剪性等性能要求上比传统d r d b 和m m d b 都更高，是一类十分有价值和广阔 前景的数据库，目前对它的研究也是数据库系统领域研究的热点之一。 2 2 2s q l i t e 特点 s q l i t e 是一款开放源码的轻量级关联式e b d b ，系统虽小但其毫秒级的数据处理速 度及多平台适用性，出众于许多同类型的数据库。经过多年来几个大版本的升级，功能 也更加健壮和稳定，目前已有越来越多的企业在使用它。s q l i t e 采用b + 树索引方式， 它默认主数据库是存于磁盘的，运行开始时将数据库主体或全部载入到内存中，如使用 非易失性内存，它也设定为可跳过该步骤。s q l i t e 装载数据时，把内存空间按设定的大 小分成页面，把不同的数据库划分为不同的区域，将数据库中的建表信息、表索引信息、 表记录值信息各自对应存入不同的页面中，各页面以其序号为关键字组织成一棵b + 树。 8 嵌入式内存数据库存储与索引算法研究 当建有多个数据库，即有多棵b + 树时，对不同数据库的索引也以各数据库根页序号为 b + 树的节点关键字进行查找。s q l i t e 支持部分标准s q l 9 2 语句，也支持用户自行变更 对表的索引【2 。 s q l i t e 的四大功能模块关联结构如图2 3 所示。c o r e 表示内核部分，s q lc o m p i l e r 表示s q l 语句的解析器，a c c e s s o r i e s 表示附属部分，b a c k e n d 是数据库后端【3 2 】。在 b a c k e n d 这个数据处理的核心模块中，包括了数据库的存储与索引技术和与操作系统的 接口，s q l i t e 采用的是b + 树索引和分页缓存存储的方式。 图2 - 3s q l i t e 结构图 f i g 2 - 3s q l i t es t r u c t u r ec h a r t b 树及b + 树索引以往主要应用于传统的d r d b ，因其叶子节点的大信息量与磁盘 扇区划分空间大小对应关系紧密，对数据按分区存取操作十分方便。以b 树及b + 树为 原型，目前研究有针对多媒体数据库系统的改进的高维数据c s a t r e e 索引树；基于 n a n df l a s h 存储设备，结合b + 树动态调整结构索引机制的改进；节点分裂及合并时机 和范围不同的改进的b + 树索引机制【1 2 3 3 , 3 钔等。 2 3e m m d b 简介 e m m d b 可看作是将m m d b 改进应用于嵌入式操作系统上或嵌入式设备环境中的 产物。近年来计算机与电子硬件的快速发展，实现了满足数据高效、快速响应要求的 m m d b 的兴起。而随着智能设备、通信、工业控制、航空航天等领域的技术进步，m m d b 向嵌入式方向的发展应用也成为必然。e m m d b 的核心数据处理组织结构是依据m m d b 的设计，由于嵌入式系统工作环境的特定性和限制性，在核心技术、体系结构及性能要 9 嵌入式内存数据库存储与索3 l 算法研究 求上与m m d b 又有所不同，性能上要求更高，因此改进m m d b 的传统算法使适用于 e m m d b 是十分必要的 3 5 - 3 6 】。e m m d b 将是更适合应用于消费电子、工业智能控制、军 事等领域的小型微型数据库。它的产生和发展，推动了数据库技术的进步。对e m m d b 的研究是十分有价值和意义的，目前也是国内外研究的热尉3 7 舶】。 过去的许多小型m m d b 和e b d b 系统大多以一个整体研究开发，各功能实现之间 并无明显定界，以致系统一经交付使用，更新升级和增删功能都十分困难，甚至不得不 抛弃旧版而重新开发，造成资源和人力的浪费。随着软硬件行业的标准化发展，许多大 型系统都采用模块化开发的技术，主流的硬件开发平台在兼容性上也逐渐增强，因此 e m m d b 的研究开发也应该避免初期更新困难的尴尬局面，顺应模块化的发展趋势，在 支持跨平台、易于维护升级系统、剪裁容易等方面体现出灵活性和优势。多结构组件化 的系统结构即指系统设计采用模块化的方式，整个系统由多个处理层次组成，每个层次 内又由多个组件构成，每个组件为单个具有完整功能的组成模块，每一个层次结构内的 模块( 同一类型) 可以互相更换，系统的结构由不同组件组成，系统同一层次内的组件 既可单独使用，也能多模块并联使用。系统层次结构和组件间都是采用功能接口的方式 传输系统使用的数据。接口具有标准化特点，每一个系统组件都实现了对应接口的功能。 e m m d b 的设计除了体积小巧，要求高速的数据处理性能之外，在数据库系统稳定 性、准确性、实时性、跨平台、硬件兼容性等也有着更高的或者特殊的要求，主要面向 工业控制、消费类电子、军事等领域【2 们。其中e m m d b 的后台支撑模块的数据处理算 法中，包括的数据存储和索引也是影响到整体数据库性能的关键技术之一。在后续的章 节中详细阐述了对m m d b 的传统区段式和t 树算法进行改进和扩展的策略，分别提出 和描述了类可扩散列区段式存储算法( e l i a s ) 和具有优先匹配目录的t 树( p r i o r i t y m a t c h c a t a l o gt - t r e e ，p m c t - 仃e e ) 算法的思想，在模拟l i n u x 嵌入式系统开发平台环境 中实现结果表明，所提出的算法在内存空间利用率、数据存储及查询响应时间、索引时 间复杂度及查询准确性等方面都有较好的性能，能够满足于现代e m m