（计算机系统结构专业论文）一种传输产品中实时嵌入式数据库的研究.pdf

独创性 或创新性 声明 本人声明所旱交的沦文是我个人在导师指导下进行的研究r 作及取得的研究 成果 尽我所知除了文中特别加以标沣和致谢中所列的内奔以外 呛文 p 不包 含矮1 n 人已经发表或撰7 与过的研究成果 也1 i 包含为获得西安电子眷 技大学或其 它教育机构的学位或证书而使用过的栩料 与我一同工作的同志剥本研究所他的 任何贞i 谳均在论文巾做 叫确的说咧升表币j 7 谢意 本人签名趣逸勤r 嘲2 0 0 2 t 旷 关丁论义使用授权的说明 本人完全j 7 觯幽安电子科技大学有关保留和使用学位论文的规定 叩 学校有 权保留送交论文的复印件 允许查淘和借阅沦义 学校可以公布论文的全部或部 分内容 n j 以允许采取影印 缩印或其他复制于段保存论文 傩密的论文在解密 后遵守此规定 术凡签名 熟泻勤 导师签名 璺蕉 硅 b 瓤 一 i t f f 日划趔 捅要 这篇论文主要刘 实时嵌入式数据库进行了研究 本文不仅从理论上对实时嵌 入式数据库进行了详细的讨论 研究 而且从实践上完成了一种传输产品使用的 实时嵌入式数据库的实现 文章从下面四个方面对实时嵌入式数据库进行了讨论 首先 本文讨论了实时嵌入式数据库的发展和前景 作为数据库领域的一个 分枝 实时嵌入式数据库有其丰富的历史背景和客观的用户需求 在数据库领域 日益发展 完善的今天 实时嵌入式数据库以其自身的特点 越来越受到人们的 重视 其次 本文讨论了实时嵌入式数据库基本功能实现的理论基础和实现方法 这一部分研究了嵌入式数据库实现的几种关键技术 较为成功的将数据结构 面 向对象思想和数据库技术有机的结合起来 并且这一部分对数据库领域的关键技 术安全问题进行了深刻的研究 实现 r 数据库的事务管理技术 锁技术和多用户 访问的数据安全问题 再次 本文研究了实时嵌入式数据库的另一个核心关键技术 高效的s q l 编 译器 从理论上讨论和解释了s q l 编译器的核心技术 然后从实际上采用了u n i x 的一个工具l e x 和y a c c 实现了一个功能齐全的s q l 编译器 最后 本文从实时嵌入式数据库内在特点出发 从理论上提出了一个提高数 据库执行效率的重要思想 下推思想 关键词 实时嵌入式数据库结构化查询语言事务日志 a b s t r a c t t i ms t u d yo f t h er e a l t i m ee m b e d d e dd a t a b a s ei sd e s c r i b e di nt h ep a p e rt h e r e a l t i m ee m b e d d e dd a t a b a s ei sc a r e f u l l yd i s c u s s e da n ds t u d i e da l s ow i t ht h ed a t a b a s e r e a l i z a t i o no f t h et r a n s m i s s i o np r o d u c t si nt h i sp a p e rt h ed a t a b a s ei sd i s c u s s e di nt h e f o l l o w i n gf o u ra s p e c t s f i r s t l y t h ed e v e l o p m e n ta n dp r o s p e c t o ft h er e a l t i m ee m b e d d e dd a t a b a s ei s d e s c r i b e di nt h ep a p e r a sad a t a b a s es u b s i d i a r y r e a l t i m ee m b e d d e dd a t a b a s eh a si t s s t r o n gh i s t o r i c a lb a c k g r o u n da n dc u s t o m e rd e m a n dn o w a d a y sw i t h d a t a b a s eb e i n g m o r ea n dm o r ec o m p l e t ea n ds o p h i s t i c a t e d t h er e a l t i m ee m b e d d e dd a t a b a s eb e c o m e s m o r ea n dm o r ep o p u l a r s e c o n d l y t h eb a s i ct h e o r ya n dr e a l i z a t i o nm e t h o d so f t h e r e a l t i m ee m b e d d e d d a t a b a s e sf u n d a m e n t a lf u n c t i o n sa r ed i s c u s s e di nt h ep a p e rt h ef i r s tp a r td e s c r i b e st h e k e yt e c h n o l o g i e so fe m b e d d e dd a t a b a s e a n di n t e g r a t e st h ed a t as t r u c t u r e o b j e c t o r i e n t e dp h i l o s o p h ya n dd a t a b a s et e c h n o l o g ys u c c e s s f u l l ya n da l s oi nt h i sp a r t d e e pr e s e a r c hi sc o n d u c t e di n t ot h ek e yt e c h n o l o g ys e c u r i t yi nt h ed a t a b a s ef i e l d a n d e v e n tm a n a g e m e n t l a t c ht e c h n o l o g ya n dm u l t i p l ea c c e s s e st ou s e r sh a v eb e e nr e a l i z e d i n t h i sp a r t t h i r d l y t h ep a p e rs t u d i e sa n o t h e rk e yt e c h n o l o g yo f t h er e a l t i m ee m b e d d e d d a t a b a s e h i g he f f i c i e n ts q lc o m p i l e rt h ec o r et e c h n o l o g yo f t h es q l c o m p i l e rh a s b e e nd i s c u s s e da n de x p l a i n e dt h e o r e t i c a l l ya n das q lc o m p i l e rw i t hc o m p r e h e n s i v e f u n c t i o n sh a sb e e nr e a l i z e db ya d o p t i n gt h et w ot o o l s l e xa n dy a c ci nt i l eu n i x a tl a s t t h ep a p e rp r o v i d e sa l li m p o r t a n ti n n o v a t i o nt h e o r e t i c a l l y f o r w a r d i n g i n n o v a t i o nt oi m p r o v et h ed a t a b a s ee x e c u t i o ne f f i c i e n c ys t e m m i n gf r o mt h e c h a r a c t e r i s t i c so ft h er e a l t i m ee m b e d d e dd a t a b a s e k e 3 7 w o r d r e a l t i m ee m b e d d e dd a t a b a s e s t r u c t u r e dq u e r yl a n g u a g e t r a n s a c t i o n l o g 第一章绪论 第一章绪论 1 1 论文工作 在任何一个网管系统中 a g e n t 程序的作用都是非常重要的 它总是起着承 上启下的作用 一方面 它要直接和下面的单板交互 另一方面 它又直接和上 层的网管交互 a g e n t 是整个网管的桥梁 一个稳定而高效的a g e n t 是一个 网管成功与否的基础 但是 a g e n t 是运行于p s o s 或v x w o r k s 等嵌入式操作系统上 其数据存取 的基础是文件操作 众所周知 文件操作有其特有的优点 但是 和一个数据库 系统比较起来 其操作的效率 方便性和安全性等方面是无法比较的 所以 公 司多年来一直在寻求一个高效的基于文件系统的实时嵌入式数据库系统 当然 市场上有一些比较优秀的实时嵌入式数据库系统 比较著名的有 s y b a s e 公司的s y b a s es q l a n y w h e r e k a i m a 的r d m 等等 但是 这样的系统在使用时 有两个不利的因素 首先 价格非常高 比如s y b a s e 的产品在每个终端都要l i c e n s e 这样无疑要大大提高产品的价格 这对于产品的市场竞争非常不利 其次 不能 最佳满足不同系统的需求 比如在传输产品的开发中 对于嵌入式数据的要求是 快速 尽量节约f l a s h 的空间 对r a m 空问的使用基本不做要求 这样我们可以 在打开数据库时将表的所有记录一次读到内存中 磁盘u o 操作非常少 这对于 提高系统的速度非常重要 但是 大部分嵌入式数据库为了提高系统性能 减少 磁盘u o 升销 在缓冲算法上非常复杂 这样反而降低了实际系统n j 性能 另外 自主开发一个实时嵌入式数据库有很多好处 首先 量体定做 对于系 统性能的提高是肯定有好处的 其次 使用自己开发的嵌入式数据库 对于故障 定位可以相对容易 最后 可啦降低产品价格 增强产品的市场竞争力等等 公司在综合考虑后 决定尝试开发一个自主的实时嵌入式数据库 并让我参于 这个工作 我在考虑到这个项目的难度系数和其广泛的应用性 决定将我的论文 题目定为 一种传输产品中嵌入式数据库的研究 实现一个高效实时嵌入式数据库系统是一 个复杂的工程 涉及到的知识领域 非常广 泛 这是我的工作所丽对的斟难 我先用了半年多的时间分析整个系统的 需求分析 写 也r 个完整的详细设计义档 给出了系统框架 功能流程 数据 流程和采 h 的各种关键技术等 剩下的半年多时间里 我通过不断地尝试和分析 我掌握了实现一个实时嵌入式数据的各种关键技术 主要有 不同平台系统的兼 容性 数据库系统的安全内核以及高效s q l 编译器的实现等等 论文的主要工作是解决实时嵌入式数据库系统的关键技术 数据库基本功能 实现 优化的查询执行 数据库系统的安全机制和高效的s q l 编译器等 论文 2 一种传输产品中实刚嵌入式数据库的研究 分析比较了当前的一些数据库系统 借鉴了当前实时嵌入式数据库中的许多先进 算法思想 并根据实际的应用 论文给出了一种传输产品中实时嵌入式数据库的 设计思想和实现方法 论文的主要创新之处有 整个系统较为成功地将软件需求 现代软件工程 面向对象思想 数据结构 数据库技术有机的结合起来 较为成功地将引用1 r 儿 个关键技术 1 预编译选项技术 通过这个技术可以实现系统在不同文件操作 系统中的兼容运行 2 h a s h 表技术 通过这个技术可以高效的对内存中的数 据进行有效存取 3 信号量技术 这个技术是数据库安全机制实现的基础 4 l e x 和y a c c 这是s q l 编译器实现的基础 论文各章的安排如下 第一章 绪论 第二章 系统的体系结构 描述了系统的总体结构框架 并给出了系统常用 的儿个基础类的封装 第二章 实时嵌入式数据库系统基本功能设计 描述了数据库系统基本功能 的设计思想和实现方法 第四章 高效的查询执彳亍 在实现了数据库管理的基本功能之后 我们在数 据库系统中常用的一种扩展关系代数基础上 讨论了各种优化查询执行的算 法 第五章 实时嵌入式数据库系统的安全机制 主要结合信号量技术 加锁技 术和数据库事务 日志的理论 描述了数据库系统的安全机制的设计思想和 实现方法 第六章 s q l 编译器 主要讨论了关键技术 l e x 和y a c c 并描述如何利用 这个关键技术设计和实现一个高效的s q l 编译器 同时从理论上探讨了语法 树的优化思想 1 2 数据库系统的的发展及动态 汁算机工业的发展过程是一个不断创新发展的过程 没有任何一个工业领域 的发展能够象计算机工业的发展一样 其创新总是让人们应接不暇 其发展总是 让人们不得有歇息的机会 但伴随着每一个创新发现 就会为整个计算机工业的 发展增加新的动力和开拓出新的领域 从而获得新的能力或功能 数据库技术正 是计算机技术中创新发明的 积极分子 为了更好的满足已有的应用需求 为了 不断地迎合新的应用需求 也为了不断发展和开拓新的应用领域 旧的数据库技 术不断得到完善 新的数据库技术的研究和应用也十分迅猛 在这样 个日新月 异的领域中 了解数据库技术的发展动向 分析各种新型数据库的特点 对数据 库f 勾研究和应用具有重大意义 各大数据库产品厂商也是对此倍加关注 第一章绪论 把握数据库技术的发展情况及动向并不是一件很容易的事 可以从f 面三个 方面来看数据库的发展i l l 1 数据库体系结构的三种发展形式 集中式的主机 终端结构 两层的客户 服务器结构 三层 或多层 的体系结构 2 数据处理环境的变化 由于数据分析应用要求日盛而原来的联机事务处理环境不能适合分析应用的 要求 而引起数据处理环境向多层体系化环境发展 3 实时嵌入式数据库的发展 虽然功能强大的大型数据库和通用的个人数据库得到很大发展 但对效率要 求很高和通用性不是很强的实时嵌入式数据库一直没有得到很大的发展 现在许 多著名数据库厂商开始注意嵌入式数据库的开发 出现了许多比较优秀的产品 如s y b a s e 的s y b a g es q l a n y w h e r e r a i m a 的r d m 等等 实时嵌入式数据库的一般特点 大小 使用最小的r a m 和磁盘空间 性能 高性能对一个实时操作系统尤为重要 i l l 可靠性 系统要能在无人监控f 健 l 上运行 可预见性 系统大小和性能可预见 低级控制 能控制何时和多少次i o 交互 13 嵌入式数据库系统实现的用户需求分析 131 j 户需求分折 1 e e e 软件工程标准词汇表中定义需求为1 3 1 朋户解决问题或达到目标所需的条件或权能 c a p a b j l i t v 2 系统或系统部件要满足合同 标准 规范或其它正式规定文档所需具备的条 件或权能 l3 种反映i 面 1 或 2 7 7 7r t i j t 述的条川或权能的文档说明 有关需求分析的重要性和如何分析 口j 参考参考文献3 132 单需求分析结果 具体需求分析的结果 鉴 二篇幅有限 这里不再罗列 通过需求分析 可以 发现整个项目l f i i 临的需要解决的重大问题宵 1 完成一个能实现数据库管理基本功能的数据库系统 主要的工作内容有 结合一些高效算法 实现数据库管理基本功能 保证系 4 一种传输产品中实时嵌入式数据库的研究 统能在大部分支持文件系统的操作系统中运行 目前支持的操作系统有 u n i x v x l l o r k s p s o s w i n d o w s 数据以文件的方式在磁盘中的有效存取 数据在内 存中的有效存取 数据以表 字段形式存取的所有数据库基本功能的实现 2 两效的查询执行 主要的工作内容有 将当前数据库系统的一 些成熟的算法应用到我们的实时 嵌入式数据库系统中 优化用户的查询执行 3 完成嵌入式数据库系统的安全机制 主要的工作内容有 支持多用户对同一表中数据的访问 系统崩溃后 采用 日志对数据库进行安全恢复 支持符合a c i d 特征的事务处理 支持多种锁机制等 4 s q l 编译器的实现 主要的工作内容有 结合己实现的数据库系统 完成一个能识别大部分s q l 语句的数据库系统 主要的工作内容有 利用l e x 和y a c c 工具实现一个8 q l 编译 器 结合已实现的数据库操作的基本功能 提供可执行s q l 语句的接口函数 第二章系统的体系结构 第二章系统的体系结构 在讨论整个系统的开始 我们首先从系统设计的角度出发 讨论一下整个系统 的体系结构设计 在从整体上把握了系统的体系结构后 然后将系统中经常使剧 的操作进行类封装 2 1 一个典型的数据库管理系统成分 211 数据库管理系统成分结构图 图2i数据库管理系统成分结构图 212 数据库管理系统成分分析 对 整个数据库管理系统有两个不同的命令来源 1 普通用户和应用程序 他们要求对数掘进行访问或修改 2 数据库管理员 负责建立数据库的结构或模式的一个人或 组人 f 面我们从四个方面肘数据库管理系统成分进行描述 l1 数据定义语言命令 d d l d a t a d e f i n i t i o nl a n g u a g e 这些命令由数据 库管理员输入 以执行模式修改命令 这些进行模式修改的d d l 命令 由d d l 处理程序进行分析 然后传给执行引擎 由执行引擎经过索引 文 i g 录管理器 去改变元数据 即数据库的模式信息 2 缓冲区管理器 数据库中的数据通常驻留在第二级存储器中 在当今的 6 一种传输产品c p 实州暖入式数据库的研究 计算机系统中 第二二级存储器 通常是磁盘 然而 数据必须在主存 储器中 才能对数据进行有效的操作 于是 数据库管理系统中有一个 称为缓冲区管理器的成分 它负责将可利用的主存空间分割成缓冲区 缓冲区是在页面同等大小的区域 磁盘块的内容可以传送到缓冲区中 这样 所有需要从磁盘得到信息的数据库管理成分都与缓冲区和缓冲区 管理器打交道 或直接地通过执行引擎 3 事务管理器 为了保证数据操作的原子性 持久性等特征 需要引入事 务管理器 事务管理器执行下面任务 目志记录 并发控蒂g 和死锁解决 4 查询处理器 可以分为两个部分 一是 查淘编译器 它将用户的查询 翻译成 乖l 内部形式 称作查询计划 查询计划是要在数据上执行的一 系列操作 查询编译器包括三个主要部分 查询分析器 它对用户的输 入字符串分析 通常为s q l 语句分析 形成一个树结构 查询预处理 器 它对奄询进行语法检查 并进行某些树结构转换 形成最初的查询 计划的代数操作符 和查询优化器 它将最初的查询计划转化为刺于实 际数据的最有效的操作序列 22 实时嵌入式数据库系统的体系结构 在上面一一节我们主要讨论了一个数据库管理系统的系统成分 通过上面的讨论 我们刘数据库系统的各个成分有了比较清楚的认识 这一节我们主要结合需求分 析 讨论实现一个实时嵌入式数据库系统的体系结构 2 21 实时嵌入式数据库系统的体系结构图 二二二二 垂堕匝二二二 漏 二亟口 二二亘夏王 内核 用户界面 图2 2数据库系统的体系结构图 第 章系统的体系结构 222 实时嵌入式数据库系统的体系结构分析 从卜图我们可以将实时嵌入式数据库系统分为三大模块 1 外壳 这部分主要是一个查询处理器 用户可以直接调用内部的b d t l 接口函数和s q l 接口函数 也可以通过面向对象的接i s 函数来进行数 据库管理 f2 内核 这部分是整个系统的核心 包含了实时嵌入式数据库的所有核心 功能 主要有 系统管理成分 事务管理器 缓冲区管理器 3 用户界面 这是系统的附加功能 主要让用户能够通过t c p l p 协议来 进行远程数据管理 23 几个基础类的封装 通过系统体系结构的分析 我们可以看到系统中对于文件操作 队列操作 信 号量操作和i 哈希表操作是比较频繁的 按照面向对象的设计方法 有必要对其进 行类封装 2 31 文件操作的封装设计思路 嵌入式数据库的实现是在文件系统的基础之上 整个数据库的是由大量的文件 组成 嵌入式数据库就是为这些文件提供一个合理方便的存储 读取操作的方法 所以 有必要对文件操作封装 考虑到文件系统对打开文件数量的限制 现规定 一个最人扣开的文件个数变量 同叫提供一个计数信号量来控制最火打开的文件 个数 为了便于管理 系统中所有的文件形成 个文件链表 同时要提供 个保 证链表互斥操作的二进制信号量 为厂系统司以在不同文件操作系统中兼容使用 这里需要采用预编译技术 232 队列操作的封装设计思路 队列是以表形式存放元素 但只允许在表的两端访问元素的数据结构 队列中 的兀素在表尾插入 在表头删除 应用巾 使 目队列按出现顺序存放元素 队列删 除元素的懒序和元素到达队列的顺序相同 可称为先进先山或先到先服务顺序i l 嵌入一弋数据库系统巾大量使 j 到队列的操作 比如不同任务刘表锁的巾请 空刚记录空州的申请等等 所以需盟提供列队列操作的封装 系统 p 对一个表的 锁订最大常量限制 所以使 h 数组实现的单队列 在队列满的时候 返也 清失 败n j 然 如粜扩展需要 可以改为链表式i j 这样的修改对于系统整f 4 l l q 影q 日 足很小的 8 种传输产品中实时嵌入式数据库的研究 2 33h a s h 表操作封装设计思路 在系统的缓冲管理器中 需要高效的对内存操作 为了提高速度 我们将虚拟 文件分成许多页 缓冲管理器的操作单位是存放一些记录的页面 为了有效地对 内存页面的管理 需要对哈希表操作封装 哈希表中的一个突出 u j 题就是冲突解决 这里我们采用 独立表链地址法 将所有的页面放到每个桶对应的链表中 2 34 信号量操作的封装设计思路 1 9 6 5 年e w d i j k s t r a 提出了高层进程互斥和同步管理的信号量的概念 信号 量是 个整数变量 具有两个原子操作 w a i t 和s i g n a l w a i t 也被称作d o w n p 和l o c k s i g n a l 电被称为up v t l r l l o k c 和p o s g 在信号量变量s 上执行w a i t 操作的进程将不能继续执行 除非s 值为正数 进程将s 值减一 而s i g n a l 操作将信号量值加1 实时嵌入式数据库中使用的许多资源 如打开的表链表 任务链表 不同用户 对同 表的互斥访问 这样的资源在任何时候只能有一个用户或一个任务在使用 而不同用户或任务对同 个表申请读权限时 系统可以规定最多的用户或任务 为了实现这样的功能 我们使用二进 0 t g 号量和计数信号量 为厂在系统可在不同的操作系统中中方便跨平台的使用 需要对信号量的操作 做一个封装 封装后的类需要提供二进制信号量和计数信号量的基本操作功能 2 4 小结 通过这 章的讨论 我们已经对整个系统的体系结构有了整体把握 总的来说 我们的工作主要是在已有基础类的基础之上 实现下面三个实时嵌入式数据库的 部件 缓冲区管理器 事务管理器和查询处理器 但是 这三个部件的联系是非常紧密的 我们不能简单地按这三个部件单独分 开实现 在下面的四章中我们按这样的分类来讨论实时嵌入式数据库系统的实现 思想和实现方法 1 实时嵌入式数据库系统基水管理功能的发计 主要讨论缓冲区管理器和 一些数据库系统的基本功能实现方法 2 高效的查询执行 主要讨论查询处理器中查询优化器 3 实时嵌入式数据库系统的安全机制 主要讨论事务管理器 4 s q l 编译器 主要讨论查询处理器中的查询编译器和查询预处理器 第三章实时嵌入式数据库系统基本功能设计 第三章实时嵌入式数据库系统基本功能设计 本章讨论一个数据库系统基本功能的设讨思路和实现方法 数据的存取有两 个方面的内容 一是数据在磁盘 或如f l a s hd i s k 类的存储介质 上的有效存 取 我们采用文件操作系统提供的文件管理功能对数据进行有效管理 二是数据 在内存中的有效存取 我们采用虚拟文件的方式来存取数据 并使用哈希表来对 虚拟文件进行有效管理 本章主要从下面三个方面来对具体的设计思路和实现方 法进行讨论 1 数据库中数据如何在磁盘上进行有效的存取 2 数据库中数据如何在内存中进行有效的存取 3 在数据得到有效存取的基础之上 讨论如何实现数据库管理的基本功能 3 1 数据在磁盘上的存取 3ll 数据库中数据传统的存储层次 第三级存储器 工 l 虚拟存储害 磁盘 文件系统 主存储器 0 高级缓冲存储器 幽31传统的数据存储层次 312 填时嵌入成数据库典型存储层次 l 二图是传统的大型数据库系统的存储模型 但实时嵌入式数据库自身的特征 小 高敛 i e 人刷对一种叫主存数据库系统的兴趣增加 主存数据库系统真正 是通过虚存来管理它们的数据 依靠操作系统 通过页面机制把所需要的数折矧 到土存 与大多数应用系统一样 主存数据库系统在数据量小到主存足以保存下 这些数据的情况卜最有用 这时不需要由操作系统来换出数据 在传输系统的嵌入式数据库开发需求中 由于f l a s h 空间有限 但r a m 是 相当大的 所以采用主存数据库系统的存储模型 j 一种传输产品c 1 实时嵌入式数据库的研究 3l3 实时嵌入式数据库的数据存储 数据库表的数据以以一定的组织规则 用文件的形式存放于第二级存储器上 所有的数据利用文件操作系统提供的文件操作函数来存取 利用文件系统的读写 功能对数据库中所有数据进行有效管理 314 实时嵌入式数据库系统的文件组成 一个数据库由一些系统文件和数据文件组成 存放在文件系统同一个目录f d b n a m ed a t 数据库字典文件 d b n a m e l o g 曰忐文件 s y s t a b l e st a b系统表s y s t a b l e s 的数据文件 s y s c o l u m n st a b 系统表s y s c o l u m n s 的数据文件 u s e rt a b l e lt a b 用户表t a b l e l 的数据文件 h s e rt a b l e li n x用户表t a b l e l 的索引文件 u s e rt a b l e 2t a b 用户表t a b l e 2 的数据文件 u s e rt a b l e li n x 用 1 1 表t a b l e 2 的索引文件 h s e ft a b i ent a b 用户表t a b l e 1 的数据文件 u s e rt a b l e n i n x 用户表t a b l e n 的索引文件 315 实时嵌入式数据库系统的使用文件解释 d b n a m ed a t 数据字典文件 存储了数据库定义信息 包括d b m s 版本号 系统表的页面大小等配置信息 d b n a m e 1 0 9 数据库目志文件 一个数据库目前只有一个日志文件 多个任务 提交事务时 顺序使用日志文件 s y s t a b l e s t a b 系统表s y s t a b l e s 的数据文件 表s y s t a b l e s 存储数据库表的定义 用户表定义 该表的每一一行是一个表的定义 包括表名 表 字段个数 文件名等等 当创建一个表时 相应表中增加一条记录 当删除一个表时 必须 在表中删除相应记录 s y s c o l u m n s t a b 系统表s y s c o l u m n s 的数据文件 表s y s c o l u m n s 存储用户表字 段的定义 表的每一行是一个字段的定义 包括字段名 表 字段索引 字段 类型 氏度等等 当创建一个表时 对每一个字段 都在表s y s c e l u m n s 中增加一 条记录 删除表时 在s y s c o l u m n s 中删除该表所有字段的记录 t a b l et a b 用户表的数据文件 对每一个用户表 都存在唯一的文件存储表数 据 一个数据文件也只能存储一个表的数据 文件名可以为表名 t a b l ei n x 用户表的索引文件 只有定义了索引 才有该文件 当前只支持一 第三章实时嵌入式数据库系统基本功能设汁 1 1 维稠密索0 i 316 d b m s 与文件系统比较 传统的文件系统无法与数据库系统相比 因为它们不能支持高效的查找 对 于少量数据的高效更新 复杂查询 有用的数据在主存储器中受控制地缓冲存储 以及事务的原子的和独立的执行 通过文件操作的方式及文件的相互关系 我们可以有效的对数据库中所有的 数据得到有效的存取 但是 数据在磁盘上的i o 是非常耗时的 对于数据量较 小的环境 特别是在内存较大时 一般采用主存数据库系统采用的存储方法 主 存数据库系统真正是通过虚存来管理它们的数据 依靠操作系统 通过页面机制 把所需要的数据带到主存 与大多数应用系统一样 主存数据库系统在数据量小 到主存足以保存下这些数据的情况下最有用 这时不需要由操作系统来换出数据 当我们采用1 了主存数据库系统的存储方法后 在数据全部放到内存后 我们 的1 作就转向如何存储和管理这些数据 下面两节主要介绍改进的虚拟文件和哈 希表两个关键技术 来达到对所有内存数据的高效存储管理 3 2 数据在内存中的存取 在数据库中数据在磁盘上有效存储的基础之上 我们接下来考虑数据如何在 内存t 1 有效的存储 最常见的方法就是采用虚拟文件的方法 但是虚拟文件本身 有很大的缺点 我们采用改进后的虚拟文件来存储内存中的数据 32l 虚拟文件 一个数据j 荦包含有许多表 每个表住磁盘l 采用文件的方法来存储 在内存 中采川虚拟文件来存储 所谓虚拟文件就是一块连续的存储空f 司 通过记录存储 空间的开始地址 结束地址及维护空闲链表 可以对一个表的存储空问进行有效 管理 但是 这样 来管理表空间会带来很大问题 首先 对表的小的改动 也要 对整个虚拟文件进行修改 这样必然导致 效率低下以及频繁写f l a s h 严重影 响f l a s h 的寿命 其次 所有的虚拟文什存储住f l a s h 中 读1 缓慢 3 22 改进的虚拟文件 1 二级存储结陶 将虚拟文件的连续存储空问划分为多个页面 一条页面可以存储多个记录 贝面大小的选择 可以根据记录的大小及记录数来取 这样 当修改 条记录时 只需要将这条记录所在的页面修改到虚拟文件中即可 种传输产品中实时嵌入式数据库的研究 2 全缓冲方式 考虑到相对于f l a s h 中数据库的大小 r a m 空问是非常大的 所以采用全 缓冲的方式 当用户使用数据库时 将数据库所有的数据全部读到内存中 当用 户提交事务时 将修改的页面更新到f l a s h 中 32 3 数据在内存中的存储示意图 p a g e n 1 1 记录 l f 记录i d2 i 记录i dm l 剩余空间 l 记录i di n 1 l 记录i dm 2 记录i d2 m 剩余空间 l 记录i d n 1 m l i g 录1 1 9 n 1 m 2 i 记录i dn m i 剩余空间 图32存储空间可i 葸图 33 嵌入式数据库的内存管理 数据库中数据在磁盘上用文件的方式存储 在内存中用改进的虚拟文件方法 存储 这一节 1 三要介绍如何对内存中的数据进行有效的管理 331 数据在内存中的管理思路 系统采用了全缓冲方式 即所有数据文件的全部数据在内存中都存在缓冲 困 匈 第三章实时嵌入式数据库系统基本功能设计 并且一个文件的所有页面缓冲即为一块连续内存 当为文件分配新的空间时 文 件的缓冲也要动态增长 在内存中将所有表的数据页面用哈希表组织起来 这样 内存中的数据就可以以页为单位来读写 其效率和对f a l a h 的损害都是非常令 人满意的 在我们的系统中 将哈希函数定义为 d e f i n e h a s hf u n c k e y s e e d lk e y s e e d 具体哈希表的数据组织图 参阅图33 哈希表图 臣互 舡互习 臣三 1 亟习 3 32 缓冲的数据有效组织 图3 3 哈希表图 系统中 我们采用 独立表链地址法 来解决哈希表中的冲突问题 所以哈 希表的节点是用链表的方式来组织 每个节点表示一个缓冲页面 并同时记录下 页面是否修改过 为了提高系统的处理速度 我们将一个表的所有脏页面单独表示出来 同时 需要记录页面大小 整个哈希表的大小和整个n 台希链表 具体的数据结构参阅下 面的数据结构表h 哈稀表的节点表示 t y p e d e fs t m c tp a g e e n t r y p a g e n 0 p a g e n o c h a r m o d i f i e d s t r u c tp a g e e n t r y 4 n e x t h a s h s t r u c tp a g ee n t r y n e x td i r t y c h a r b u r p a g e e n t r y 数据表的哈稀表表示 t y p e d e fs t m c tc a c h e i n f o p a g ee n t r y p gh a s h t a b l e s h o r t p g h a s h s i z e p a g e e n t r y p gd i r t y 数据存放的页面号 页面是否为脏页面 下一个哈希页面 下一个脏页面 存放的具体数据 整个哈希链表 哈希表的大小 哈希表中的所有脏页面链表 4一种传输产品中实时嵌入式数据库的研究 s h o r t p g s i z e 加匿面的大小 p a g e n op g d i r t y n u m 脏页面的个数 c a c h e i n f o 3 33 接口提供的函数 缓冲初始化 c a c h e i n i t d b t a s k t a s k t a b l e e n t r y t a b l e p 将为表分配全部页面 并加到该表的h a s h 缓冲表中 同时初始化h a s h 节点 缓冲清空 c a c h e f r e e d b t a s k t a s k t a b l e n t r y t a b l e 释放h a s h 表的所有页面 然后释放h a s h 表的空间 装载文件 c a c h el o a d d b j a s k t a s k t a b l e e n t r y t a b l e p a g en op g l a s t 从磁盘中将表对应的文件数据全部读到h a s h 表的相应页面 节点 写文件 c a c h e 一丑u s h d b t a s k t a s k t a b i ee n t r y 4t a b l e j 等h a s h 表中的脏节点链表中数据写到磁盘对应的文件 扩展页面 c a c h ea d d p g d b t a s k t a s k t a b l e e n t r y t a b l e p a g e n 0 p a g e n o f 按h a s h 表空间管理算法 生成一个新的节点 删除页面 c a c h e f r e e p g d b t a s k t a s k t a b l e e n t r y t a b l e p a g e n op a g e n o f d l j 除h a s h 表中对应的页面 并对脏节点链表处理 读一页 c a c h eg e t p g d b t a s k t a s k t a b l e e n t r y 8t a b l e p a g e n o p a g e n o p a g ee n t r y p a g e 读取指定一页的内容 写一页 c a c h e p g o u t d b 1 a s k t a s k t a b l ee n t r y 4 t a b l e p a g ee n t r y p a g e 将指定一页的数据写到文件中 34 嵌入式数据库系统基本功能实现 在数据在磁盘和内存得到有效存储和管理之后 数据库的基本功能就是对这 第三章实时嵌入式数据库系统基本功能设计 15 些数据采用一些方法进行有效的读写和其它操作 在这里主要讨论嵌入式数据系 统满足的基本功能 字段 记录 表 数据库的有效存取功能的实现 为了更有效的在数据库中存取数据 我们引入数据库地址的概念 数据库地址d ba d d r 在系统中表的分配编号从0 开始 表中的每一条记录从l 开始编号 所以任 一条记录可以存在一个唯一标识 又因为存储表文件的页面大小是确定的 从而 可以根据一个数据库地址得到一条记录所在的页面和偏移量 数据库地址可以用 一个整数表示 前8 个字节表示表i d 后2 4 个字节表示记录i d 当然不同系统可 以调整 l 表t d 8 b j 记录 d 2 4 b 数据库地址相关的计算公式 每一个页面存储的记录数r o w s p e r p a g e 页面大d i g 录人小 记录号为j 所在页面 j 1 1 r o w s p e r p a g e 在页面中偏移 j 1 m o dr o w s p e r p a g e 记录人小 341 字段的表示及存取 1 字段表示和存取的设计思想 侄数据库系统中 所有的字段数据最终被表示成一个字节序列 例如 一个 类 弘为i n t e g e r 的属性通常表示成四个字节 一个类型为f l o a t 的属性通常表 j 成 八个字节 整数和实数表刁i 成字节串 由机器的硬件对字节串进行特定解释 从 而在其上可执行通常的算术操作 但在不同的操作系统中 列于不同数据类型定 义的字节数可能4 i 同 为j 7 能在4 i 同的系统间保证兼容性 采取对字段类型重定 义 并对字段定义使用有长度的数据结构 稿 定义好字段的数据结构后 刘 f 字段的存取就是根据偏移量和字段长度来 取字段的值 比如可用如下的方法来存取字段 m e m c p y f i e l d v a l u e n 1 一r e c o r d mo f f s e t f i e l d n o ml e n g t h f i e l d n o 2 宁段的数据结构表 剥j j j j 户提供简单的定义结4 12 j j 体 然后转化为复杂的利于使用的结构体 其 定义分别如 i t 3p e d e fs t r u c t s h 0 1 1 s h o r t 1f i e l dd e f s n a m e f i e l d n a m el e n i 宁 段名 6 t 3 1 p e i c n n d 字段类型 字段长度 一种传输产品中实时嵌入式数据库的研究 t y p e d e fs t r u c tf i e l da r t r c h a r n a m e f i e l d n a m e l e n 字段名称 t a b l en o i d i 表i d s h o r tcolid liyfj弓 s h o r t t p e 字段类型 s h o r t l e n g t h 字段长度 s h o r t o f l s c t 字段在记录中的偏移量 f i e l d a t t r 34 2 记录的表示及管理 1 将字段组织成记录的两个问题 首先是4 地址问题 有些机器可以对主存中地址为4 的倍数 或8 的倍数 6 4 位的c p u 的字节处开始的数据进行更有效的读写 某些数据类型 如整数 也许要求必须从4 的倍数的地址处开始 而其它的数据类型 如双精度实数 可 能需要从8 的倍数处开始 所以在将字段定义组织成字段时 必须将这些字段在 记录内的偏移地址具有4 或8 的倍数 其次是变长记录的组织问题 如果记录的一个或多个字段是变眭的 则记录 必须包含足够多的信息以便我们能找到记录的任何字段 一个简单而有效的模式 是将所有定长字段放在变长字段之前 然后在记录首部记录记下记录长度和变长 记录开始处 偏移量 的指针 2 记录首部的设计思想 我们的数据库系统要实现多种数据表 不同的数据表有其自身的特征 从而 不同表的记录表示也要不同 大致可以有两种记录头表示方法 对于覆盖表 由于要记住记录的生成先后 所以对于每条记录头要有维护记 录生成先后的双向链表的8 字节指针开销 另外 要有表示记录是否空闲的一个 字节 对于非覆盖表和动态表 没有必要保存记录生成先后的次序 所以只需要 有表示记录是否空闲的一个字节开销 3 标志位的设计思想 系统维护一个文件列表来维护数据库中所有的表 每个表在内存中有许多页 面组成 这些页面由表的缓冲h a s h 表来维护 每个页面有许多条记录组成 所 以 当我们修改 条记录时 只须这条记录所在的页面修改到对应的文件中就行 了 而不需要修改整个文件 大大节约了磁盘i o 对于提高系统速度很有好处 为了记录表文件状态 页面使用状态及记录的使 状态 要引入标志位 分 别为一 个字节 表文件标志位表明该表处于打开还是关闭状态 页面标志位表明 该页是否为脏页及是否修改过 记录标志位表明这条记录空间是否已使用 对于 第三章实时嵌入式数据库系统基本功能设计 1 7 覆盖表还要添加维护记录生成先后链表的标志位 8 位 4 记录的有效管理队列 每个表维护 个系统记录空问管理结构体 同时这个结构体中维护了个队 列 达到对表的空闲记录空间有效管理 表空间管理队列结构体 t y p e d e fs t r u c tr e c o r d a l l o c i n f o d b a q u e u ef l e e 空闲队列 d ba d d r n e x t 下一条空闲记录开始搜索的数据库地址 p a g e n o p g n u m 表的页面数 r e c o r d j 山l o c i n f o 覆盖表记录使用的结构体 t y p e d e f s t r u c tr e c o r dh e a d e r c h a r f l a g 1 使用标志 d ba d d rn e x t 下一条记录的位置 d b a d d rp r e y 上一条记录的位置 r e c o r dh e a d