（计算机应用技术专业论文）微型数据库引擎的研究.pdf

武汉理工大学硕士学位论文 摘要 在任何仿真环境冲都有大量的数据需要存储和读取，数据库作为信息的来 源和存储地，有着至关重要的作用。现有数据库管理系统( d a t a b 船em a n a g e m e n t s y s t e m ，简称d b m s ) 像o r a c l e 、s q ls e r v e r 等都提供了很好的编程接口，但由 于这些数据库管理系统都比较庞大，将一套已经开发好的数据库应用系统进行 封装和发布，会出现维护困难的局面。而且，一个d b m s 往往与系统平台结合 较为密切，这就限制了仿真系统的应用面。因此，为了满足仿真平台的应用需 求，开发出一套与平台无关的数据库引擎具有很重要的意义。 本课题属于2 0 0 0 年国家自然科学基金项目“分布交互三维视景行为特征建模 方法研究。此基金项目包括：三维建模技术、三维碰撞检测、人体运动仿真、分布 式网络通讯模型、三维寻径算法和数据库引擎技术等的研究开发。其中数据库引擎 技术的研究目的是开发出一套微型、高效的能满足仿真平台特定需求的数据库系统。 仿真系统的开发者能够将基本的数据库功能直接集成到其应用系统中去，这样就 完全摆脱了商业d b m s 的束缚，使得技术人员能够开发出应用面更广的仿真系 统来。 本文就国家自然基金项目中数据库引擎技术的研究展开讨论。从数据库系统实 现的数据存储、索引结构、查询编译、查询执行几个方面，讨论了物理存储、文件 磁盘操作、b + 树、i a 【r ( 1 ) 分析、关系代数的物理实现算法、虚拟机等技术。 第1 章绪论介绍此课题的背景及意义、数据库研究国内外发展动态及论 文研究的主要内容。 第2 章微型数据库引擎实现概述介绍数据库实现的基本内容和实现机 制。基本内容包括存储管理、查询处理和事务管理。 第3 章数据存储主要讨论了数据库的物理组织和索引结构。讨论如何存 储和管理大量的数据，采用何种结构能快速的定位到相应的记录信息，这里重 点讨论了b + 树结构。 第4 章查询处理器主要讨论如何将用户的查询和数据修改命令转变为 数据库上的操作序列。重点讨论了语法分析、语义分析、物理查询执行算法、 虚拟机代码的生成和执行。 第5 章研究工作总结主要对所开发的系统作出总结，指出不足之处，并 展望未来各项技术的发展。 关键字：数据库系统实现，语法分析，语义分析，虚拟机技术 武汉理工大学硕士学位论文 a b s 仃a c t i na n ys 曲【u l a t i o ne n v i r o 脚e i l t ，t h e r ei sal a r g ed a t at os a v ea i l dr e a d a sap l a c e o fs o l l r c ea i l ds t o r eo fd a 氓d 撕b a s em a n a g e m e n ts y s t e 】mp l a y sa ni r n p o r t a tr o l e e x i s t i n gd 撕b a s em a n a g e m e n ts y s t e m ( d a t a b a s em a n a g e m e n ts y s t e m ，f o rs h o r t d b m s ) l 讧r eo r l e ，s q ls e r v e r h a v ep r o v i d e de x c e l l e n tp r o 乒a n l i n i n gi n t e r f a c e b u t b e c a u s em e s ea r er e l a t i v e l y1 a r g ed a t 曲硒em a n a g e m e n ts y s t e l n s ，w h e nw eh a v e d e v e l o p e dad a t a ：b a s ea p p l i c 撕o ns y s t e mf o fp a c k a g i l l g 趾dp u b l i s h i n g ，w eo f t e nh a v e d i 伍c u l t i e st om a i l l t a i ni t m o r e o v e r ，o r d i n a r i l yad b m sm o r ec l o s e l yi n t e f a t e dw i t h t l l ep l a t f o m ，w m c h1 i i i 血s 也ea p p l i c a t i o n 啪g eo fs 证n d a t i o ns 粥t c m s t h e r c f o r c ，1 e d e v e l o p m e mo fa l i c m - d a ：c a _ b 雒e 吼g i i l et om e e ts p e c i 矗ca p p l i c a t i o n so fs 曲m l a t i o n p l a t 南皿b e c o m e ss i g l l i f i c 撕v e t h es y s t e mb e l o n g st ot h en a t i o ns c i e n c ef 咖d a t i o np r o j e c t “r e s e a r c ho f 也e m o d e l i i 玛 m e m o df 研d i s 倒b u t e di n t c r 剃、砖t h r e e d i i n 叽s i o n a lv i s l l a l b e h a v i o r c h a r a c 删s t i c ”i n 2 0 0 0 m s 妇dp r o j e c t s k i 删n g ： r e s e a r c h e si n t h r e e d i m e n s i o i l a lm o d e l i i 培t e c h n 0 1 0 9 y ，t h r e e d i m e n s i o n a lc o l l i s i o nt e s t i n g ，h l l m a n m o t i o ns i r n m a t i o n ，d i 鲥b 恤dn e t w o r kc o m m u m c a 虹0 nm o d e l ，t h r e e - d i m e n s i o n a l r o u t i n ga l g o r i m ma n d 出出出嚣ee n 画n et e c h o l o g yd 缸b 勰ee n g i i l et e c h n o l o g ya i m s t od e v e l 叩a ne 伍c i c n ti n i c r o 也t 曲硒es y s t e mt om e e tt l l es p e c m cn e e d so fs 证m l a t i o n p l a t f o m l d e v e l o p e r sw i l lb ea b l et oi n t e g r a t et h eb a s i cf i l i l c t i o i l so fd a t a b a s et 0t l l e i r a p p l i c a t i o n sd i r e c t ly ，趿d 也e n 也e yc 肌c 船to f rt h es h a c k l e so ft h ec o m m e r c i a l d b m sc o m p l e t e l y8 n dd e v e l o pab a d e ra p p l i c a t i o no f s i m u l a t i o ns y s 七e m s t h et h e s i sd i s c u s s e s 出出出鹪e e n 垂n et e c h n o l o g y i nt l l en a t i o ns c i e n c e f o u n d a 土i o np r o j e c t f r o ms e v e r a ls i d e so f 血ed a t a ：b a s es y s t e m ：d a 协s t o r a g e ，i i l d e x s t m c 眦，e i l q u i r i e sc o m p i l e r ，t 1 1 ei i i l p l e m e n t a t i o no fe r l q u i r i e s ，t h et l i e s i sd i s c u s s e sm e p h y s i c a ls t o r a 唱e ，丘l e d i s ko p e r a t i o n ，b + t r e e ，l a l r ( 1 ) a n a l y s i s ，a l g o r i t h m so f r e l 撕o n a la l g e b r a ，、，i r t i l a lm a c n i l l et e c h o l o 百e s c h a p t e rl ：p r e 】e t 1 1 i sc h a p t e ri n 乜o ( h j c e s 也eb 髓k 孽d 吼d 肌ds i g n j f i c a n c eo f t l l i st l l e s i s ，d o m e s t i c 趿df o r e i g nr e s e 盯c h 仃e r 证i nm er e l a 把d 矗e i d sa sw e l la sc o n t e n t i i 武汉理工大学硕士学位论文 o t m es y s t e m c h a p 搬2 ：a no v e r v i e wo nt h eb 船i ce l e m e n t so f 出l 协b a s ea i l dt h ei i h p l e m e n t m e c h a n i s mo fm em i c r o d a 协b a s ee n 百n e t h eb a s i cc o m e n t si i l c l u d e s t o r a g e m a n a g e m e n t ，e n q l l i r i e sp m c e s s i n ga n d 打 m s a c t i o nm 锄a g e m e m c h a p 忙r3 ：d a t as t o r a g e t h i sc h 印t c rf o c u s e so nm ep h y s i c a lo 唱a n i z a t i o no f t h e d a 船l b a s ea n di n d e xs t r i l c t u r e ，d i s c u s s e sh o wt os t o r ea n d 蚴a g eal a 唱e 锄o u n to f d a t ae f r e c t i v e l y ，w h a ts 由j c t l i r ei sm o r em p i d l yt op o s i t i o ni n f o r n l a t i o no fm e c o r r e s p o n d i n gr e c o r d ，h e r e 也ec t l l p l 斌f o c u s e so nb + t r e es t n l c 机r c c h 印t e r4 ：e n q u 证e sp r o c e s s 0 r t 面sc h a p t e rd i s c u s s e sh o wt 0c h a n g et h el l sc r i s c o r l m l a n do fq u e r ya 1 1 dm o d i f i c a t i o nt oo p e 枷o ns e q u e n c e nf o c u s e so n 野删a r a n a l y s i s ， s e m 枷1 t i ca n a l y s i s ，p h y s i c a le n q l d r i e si m p l e m a l t a t i o na l g o r i t h l 工l s ，t h e g e n e m n o na n di m p l e e 玎t a t i a no f v i n i l a lm a c h i i l ec o d 鼠 c h a p t e r5 ：c o n c l u s i o no fm er e s e a r c h t h i sc h a p t e rc o m e st o 廿l ec o n c l u s i o no f t i l ed e v e i o p e ds y s t e m ，p o i t so u ti 璐u 筋c i e n c i e sa n dp r e d i c t sm ep r o s p e c to fv a r i o u s t e c h n o l o 画e si nt h ef l l t l l r e k e y w o r d s ：d a 诅b 髂es y s t e mi m p l e m e n t a t i o n ，g 础m a r 删y s i s ，s e m a n t i ca n a l y s i s ， v i r n l a l 加丑c h i n et e c h n o l o g y 武汉理工大学硕士学位论文 1 1 课题的背景及意义 第1 章绪论 仿真系统中数据量很大，如何对海量仿真数据进行有效的存储和读取是仿 真系统中一个重要的方面，它直接影响到仿真系统的性能和应用面。因此数据 库在仿真系统中起着至关重要的作用。 现有数据库管理系统( d a 讪a s em a l l a g 咖e ms y s t e m ，简称d b m s ) 已经能 够为各种商业用途提供强大的支持。它具有以下几个特点： ( 1 ) 持久存储。与文件系统类似，d b m s 支持对大量的数据进行存储。相比 文件系统而言，d b m s 的数据独立性高，它们独立于使用数据的任何处理程序而 存在。数据面向整个系统，共享性高，冗余度低。 ( 2 ) 编程接口。d b m s 提供了灵活的查询使得用户能够通过强有力的查询语言 访问和修改数据。d b m s 在数据操纵的灵活性方面也比文件系统强。 ( 3 ) 数据控制功能强。为了适应共享数据的环境，d b m s 提供了四个方面的数 据控制功能：数据库的并发控制、数据库的恢复、数据安全性和数据完整性。 其中并发控制是指多个不同的进程( 称作“事务”) 同时对数据进行存取。事务具 有原子性，即要求事务或者完全执行，或者完全不执行。 由以上几点可以看出，d b m s 与文件系统相比有着明显的优势。如今像 o r a c l e 、s o ls e r v e r 等这样一些d b m s 已经渗入到各个领域中。然而可以发现虽 然d b m s 提供了很好的编程接口，如o d b c ，a d o ，r d o 等。但由于这些数据 库管理系统都比较庞大，将一套已经开发好的数据库应用系统进行封装和发布， 会出现维护困难的局面。而且，往往一个d b m s 与系统平台结合较为密切，这 就限制了仿真系统的应用面。开发出一套简单高效且与平台无关的数据库引擎 来适应仿真平台的特定应用就很有必要了。开发者能够将基本的数据库功能直 接集成到其应用系统中去，这样完全摆脱了商业d b m s 的束缚，使得技术人员 能够开发出应用面更广的仿真系统来。 所选课题是国家自然基金项目“分布交互三维视景行为一特征建模方法研 究”的一部分，即微型数据库引擎的研究。本课题得到国家自然科学基金和中国 科学院计算机研究所智能信息处理开放研究实验室项目资助。 武汉理工大学硕士学位论文 1 - 2 国内外发展动态 常见的数据库管理系统有o r a c l e 、s y b a s e 、m i c r o s o f cs o ls e r v e r 、m i c r o s o f c a c c e s s 等，下面简要介绍几种常用的数据库管理系统。 o r a c l e 是一个最早商品化的关系型数据库管理系统，也是应用广泛、功能强 大的数据库管理系统。o r a c l e 作为一个通用的数据库管理系统，不仅具有完整的 数据管理功能，还是一个分布式数据库系统，支持各种分布式功能，特别是支 持h l t e m e t 应用。作为一个应用开发环境，o r a c l e 提供了一套界面友好、功能齐 全的数据库开发工具。0 r a c l e 使用p l s q l 语言执行各种操作，具有可开放性、 可移植性、可伸缩性等功能。特别是在o f a c l e8 i 中，支持面向对象功能，如支 持类、方法、属性等，使得0 r a c l e 产品成为一种对象关系型数据库管理系统。 m i c r o s o f 【s q ls e e r 是种典型的关系型数据库管理系统，可以在许多操 作系统上运行，它使用t r 姐s a c t s q l 语言完成数据操作。由于m i c r o s o f ts o l s e r v e r 是开放式的系统，其它系统可以与它进行完好的交互操作。 作为m i c r o s o f co 伍c e 组件之一的m i c r o s o ra c c e s s 是在w i n d o w s 环境下非 常流行的桌面型数据库管理系统。使用m i c m s o f ta c c e s s 无需编写任何代码，只 需通过直观的可视化操作就可以完成大部分数据管理任务。在m i c r o s o f ta c c 船s 数据库中，包括许多组成数据库的基本要素。这些要素是存储信息的表、显示 人机交互界面的窗体、有效检索数据的查询、信息输出载体的报表、提高应用 效率的宏、功能强大的模块工具等。它不仅可以通过0 d b c 与其它数据库相连， 实现数据交换和共享，还可以与w o r d 、e x c e l 等办公软件进行数据交换和共享， 并且通过对象链接与嵌入技术在数据库中嵌入和链接声音、图像等多媒体数据。 1 - 3 论文的主要研究内容 本课题是国家自然科学基金项目分布交互三维视景行为特征建模方法 研究的一个组成部分。 本文研究了实现微型数据库引擎所需要的相关技术，它们包括数据存储算 法、索引技术和虚拟机工作原理等。在实验室已有设计的基础上，继续完善微 型数据库引擎中对标准s q l 语句的解析和执行。微型数据库引擎的实现为仿真 过程中出现的数据提供了灵活的存储、检索和更新机制。 武汉理工大学硕士学位论文 第2 章数据库系统实现简述 下图2 一i 展现了一个完整的d b m s 的轮廓。单线框表示系统成分，双线框 表示内存数据结构。实线代表控制和数据流，虚线代表仅是数据流。 瑚出，应用 数撩球管理员 冠囊i 据 图2 1 数据厍管理系统成分 对于d b m s 有两个不同的命令来源： ( 1 ) 普通用户和应用程序，他们要求对数据进行访问或修改。 ( 2 ) 数据库管理员，他们负责建立数据库的结构或模式。 第一类命令一般都沿着图2 1 中左边的路径进行。用户或应用程序启动某个 活动，该活动不影响数据库模式，但是可能影响数据库内容( 如果该活动是一 武汉理工大学硕士学位论文 个修改命令) ，或者会从数据库中抽取数据( 如果该活动是一个查询) 。用户活 动可能沿着两条路径影响数据库：查询更新和事务命令。查询更新命令执行的 流程比较长，要经过查询编译器、执行引擎、索引和记录文件管理器、存储管 理器等阶段，其中查询编译器和执行引擎是其中最重要的两个阶段。查询编译 器的主要功能是将查询翻译成一种内部形式，即查询计划。查询计划是根据查 询语句所形成的对数据的一系列操作。通常，查询计划中的操作是“关系代数” 的实现。执行引擎主要负责执行选中的查询计划中的每一步。它几乎与d b m s 的其他部分都有交互。事务命令的处理是为了保证d b m s 的持久性( 已完成事 务所作的工作决不会丢失) 。从图2 1 可以看出，事务管理器从应用系统中接收 命令，从而得知什么时候事务开始，什么时候事务结束，以及应用系统的期望 信息。事务处理主要任务为：日志记录、并发控制和死锁的解决。 第二类命令处理起来相对比较简单，我们以图2 1 中右上部分为起始点给出 它的踪迹。当需要建立一个表时，由数据库管理员输入表的基本信息，由图2 1 中d d l 处理程序进行分析，然后传给执行引擎。由执行引擎经过索引、文件和 记录管理器去改变数据。 数据库系统实现大体上分为三个部分【l j ： ( 1 ) 存储管理：负责存储数据、元数据( 表、记录和字段等信息) 、索引( 加 速对数据的存取的数据结构) 和日志( 数据库变化的记录) ，这些数据保存在磁 盘上。一个重要的存储管理部件是缓冲区管理器，它将磁盘内容的一部分保存 在主存储器中，从而减少磁盘的i ，o 操作。这一部分的设计需解决的问题是：如 何高效地利用辅助存储器来存放数据，并使得数据能够被快速存取。 ( 2 ) 查询处理：它对查询进行分析，通过选定一个查询计划对查询进行优化， 并且在存储的数据上执行查询计划。这一部分的设计需解决的问题是：如何高 效地执行s o l 语言表达的查询。 ( 3 ) 事务管理：负责对数据库的改变记日志，以支持系统崩溃后的恢复。它还 执行事务的并发执行，保证原子性。总的说来，事务管理主要功能为：支持事 务具有“原子性”、“一致性”、“隔离”、“持久性”。( “原子性”：事务完全执行或完 全不执行；“一致性”：所有的数据库都有一致性约束，或关于数据之间联系的预 期状况；“隔离”：表面上看起来每个事务都是在没有其他事务同时执行的情况下 执行的；“持久性”：一旦事务完成了，则事务对数据库的影响就不会丢失。) 4 武汉理工大学硕士学位论文 第3 章数据库文件结构设计 3 1 数据的基本存储单位 数据库是大量数据的有结构的综合性集合。为了方便管理数据，我们按一 定大小的数据块来存储和读取数据。系统中称该数据块为一个( p a g e ) 。数据库 实现的基础是文件，对数据库的任何操作最终要转化为对文件的操作，也就是 说数据库系统中存在大量的磁盘操作。磁盘被分成5 1 2 个字节大小的扇区，扇 区是磁盘的物理单元。但是读写单个扇区的效率很低，所以将几个扇区合起来 作为一个块，磁盘控制器每次读写是以块为单位。这个块的大小一般为5 1 2 8 1 9 2 字节( 扇区大小的整数倍) 。系统中我们将数据库的存储和读取数据的逻 辑单元( 数据块) 设计为4 0 9 6 个字节1 2 】o 数据块是数据库文件组成的基本单位。系统中数据库文件的总体结构如表 3 1 所示。 表3 1 文件头 数据库表信息存放块 p a g e l ( 数据块) p a g e 2 ( 数据块) p a g e n ( 数据块) 数据库数据的存储结构不同于一般文件系统的存储结构。数据库数据的特 点是各种数据之间彼此有联系，数据是结构化的。数据的存储结构不仅涉及每 种数据如何存储，而且还要使数据的存储能够反映各种数据之间的联系。本系 统是在实验室已有的前期设计的基础上进行的，有关数据库中文件结构以及数 据块的详细设计请参考实验室资料【拍。 武汉理工大学硕士学位论文 3 2 记录i 0 3 2 ，1 记录的保存 关系数据库中属性用定长或变长的字节序列表示，称作“字段”：字段被组装 成定长或变长的集合，称作“记录”，记录对应于元组或对象，记录需要存储在物 理块中。记录是文件中的个逻辑单位，在具体实现时记录必须被分配存储到 具体磁盘块中去，从而构成一条物理记录。构成一个关系的记录集合存储为数 据块的集合。 数据块中如何存放记录信息昵? 图3 1 展示了系统中数据块中记录存放的 方法。 一叁叶 未使用的 + _首部- h 卜- 空间 图3 1 ：一个有偏移量袁的块，偏移量指明块内每一条记录的位置 为了实现快速、灵活的定位记录，我们在每个数据块的首部创建一个“偏移 量表”，其中“偏移量”的指针指向数据块中每一记录的位置。 如图3 1 所示，系统中我们所采用的存储记录的方法是：记录从数据块的后 端开始放置，数据块的首部信息向后增长。为何采用这种方式? 从数据块头部 开始顺序存放可能是一个显而易见的办法，但是这样设计的话，我们就得为“偏 移量表”预留一定的空间，这个空间与将要插入的记录数有关，是无法确定的。 而从数据块尾部插入记录使得未使用的空间在数据块的中部，避免了为数据库 表分配固定大小的数据块的首部【j j 。 3 2 2 记录的修改 下面参照图3 1 简述系统中记录的插入和删除操作。 ( 1 ) 插入 武汉理工大学硕士学位论文 如果能在当前数据块中为待插入记录找到空间，则新记录被插入到数据块 中，相应地在数据块的偏移量表中添加指向此记录的指针。但是，数据块中可 能没有空间用于新记录的存储，在这种情况下，就不得不在此块之外寻找到空 间。解决这个问题主要有两种方法，这两种方法也可以结合使用。即在“邻近块， 中找空间和创建一个溢出数据块【4 j 。 ( 2 ) 删除 删除记录可以考虑采用将后面的记录都向前移动一个单位的方式来进行， 但这种方式的缺点是磁盘i o 操作太多，同时不便于索引的维护。也可以考虑 采用设置删除标志位的方式，但这种方法的缺点是会产生一些死空间。系统中 我们引入删除记录链的思想。它的整体设想是：构造一个链栈来保存被删除记 录的位置。在数据库文件头设置一字段存储第一个被删除记录的位置，被删除 的记录本身包含下一个被删除记录的地址( 最后一个就用n u l l 来标记) 。这样当 我们要插入新的记录时，可以先检索存储删除记录的链表，看是否存在被删除 的记录，如存在则用新记录覆盖被删除的记录。删除记录也很简单，把删除记 录的地址加入删除链表即可。 有关记录存储和操作的详细设计请参考实验室资料【2 j 。 3 3 索引结构 索引是这样一种数据结构：它以记录的特征( 通常是一个或多个字段的值) 为输入，并能“快速地”找出具有该特征的记录【3 】 4 】。具体来说，索引使我们只需 查看所有可能记录中的一小部分就能找到所需记录。建立索引的字段称为查找 键。由于索引文件只含有特征字段( 即索引属性) 上的值和记录指针，即关键 码和物理存储地址指针的二元组，因此索引文件的大小一般都大大小于数据文 件的大小。同时索引文件采用便于查找的特殊组织结构( 如b 或b + 树) ，这使得 通过建立索引文件大大提高了在数据文件上的记录查找定位速度。 一个基本s q l 查询如图3 2 所示。 键值 图3 2 ：基本s 札查询步骤 7 对应的记录 武汉理工大学硕士学位论文 系统中所采用的索引方案是一种称为b + 树( 可以称为平衡树或浓密树等) 的 数据结构。它是大型文件的组织方法。对于需要支持插入、删除和范围查询的 应用，它是标准的文件组织形式【1 3 。具有以下几方面的优势： ( 1 ) b + 树能自动地保持与数据文件大小相适应的索引层次。 ( 2 ) 对所使用的存储块空间进行管理，使每个块的充满程度在半满与全满之 间。这样的索引不再需要溢出块。 ( 3 ) 支持范围查询。 下面简要介绍系统采用的b + 树结构。详细设计参见实验室资料【2 】o 3 - 3 1 b + 树 b + 树把它的存储块组织成一棵树。这棵树是平衡的，即从树根到树叶的所 有路径都一样长。通常b + 树有三层：根、中间层和叶，但也可以是任意多层。 对应于每个b + 树索引都有一个参数n ，它决定了b + 树的所有存储块的布局。b + 树中的每个结点占用一个磁盘块，每个存储块存放n 个查找键值和n + 1 个指针。 在存储块能容纳n 个键和n + 1 个指针的前提下，把n 取得尽可能大，以便在一 个磁盘块中存放更多的索引项。一个典型的b + 树结构如图禾2 所示，图中n 取 的是3 。 图3 3 ：典型的b + 树结构 n 阶的b + 树的结点的结构如下： 其中：k 1 ，k 2 ，k m 是索引关键字值，且k l k 2 k 。 对于根结点，则有2 纽n ，即根节点至少有两个指针被使用。指针指向位 于b + 树下一层的存储块。 对于叶子结点，则有l ( n + 1 ) 2 j s m 茎n ，p 。，p 2 ，p 。是指向数据记录的 武汉理工大学硕士学位论文 指针，p 一- 是指向其右边的下一个叶子结点的指针。其中，p i 是指向关键字值为 琏的数据记录( 忙l ，2 ，m ) 。未使用的指针可看作空指针且不指向任何地方。 对于内部结点，则有i ( n + 1 ) ，2 1 m n ，而p 1 ，p 2 ，p 。，p m + 1 则是分别 指向另一棵子树的根结点。 对p 1 所指向的子树中的任意一个索引关键字k ，都有k k ，。 对p 所指向的子树中的任意一个索引关键字k ，都有k 2 k 。 对p j 所指向的子树中的任意一个索引关键字k ，都有k 一】兰k k 。 b + 树的特点： 1 ，叶结点都在同一层中，叶节点包含了全部关键字的信息，及指向含这些 关键字记录的指针，且叶节点本身依关键字的大小自小而大顺序链接。可以把 每个叶结点看成是一个基本索引块( 直接指向数据文件中的记录1 。 2 所有非终端节点可以看成索引部分，结点中仅包含它的各个子结点中最 大( 或最小) 关键码的分界值及指向子结点的指针。 3 3 2 b + 树的效率 b + 树索引结构能使实现有效的记录查找、插入和删除操作，即这些操作只 需要很少的磁盘i 0 操作。那么b + 树重组的i o 开销如何呢? 这里我们基本上 可以忽略这些开销，因为当每个块容纳的键数n 相当大时，比如1o 或更大，分 裂或合并块的情况将会很少，而且绝大多数时候分裂或合并操作都被局限在叶 结点，因此只有两个叶结点和它们的父结点受到影响【i i 】。这些开销相对于其他i o 操作要小得多，可以忽略不计【1 6 。 然而，根据b + 树结构的特点，对于给定查找键值查找记录的操作，实际需 要从根结点一直访问到叶结点才能找到指向记录的指针。这样磁盘i o 数将是 b + 树的层数加上次( 对查找而言) 或两次( 对插入或删除而言) 处理记录本 身的磁盘i o 。那么b + 树的层数也就决定了磁盘i o 次数。b + 树到底有多少 层? 对于典型的键、指针和块大小来说，三层就足够了，除非数据库极大。因 此，一般取3 作为b + 树的层数。 3 3 3 索引文件存储形式 前面一节介绍了索引结构的基本理论知识，这节简要介绍本系统中设计的 武汉理工大学硕士学位论文 索引物理存储结构。详细设计说明请参考实验室资料【2 1 。 为了方便管理，我们在生成数据库文件的同时，生成相应的同名称的索引 文件( 默认文件扩展名+ i d ) 【) 。索引文件的结构采用上述的b + 树结构，数据库中每 个表的索引以b + 树结构形式存储在索引文件中。索引文件中最基本的结构是节 点，为了充分提高磁盘的读写效率，默认的节点大小为一个数据块的大小即： 4 0 9 6 个字节；每个节点所存放的键的数量n 必须满足的条件为： 4 4 ( n + 1 ) + x + n + s i z e o f ( n o d 眦a d ) 璺0 9 6 ( 其中x 为每个键占用的空间大小) 。 表3 2 节点结构 为了更好的发挥b + 树索引结构检索记录的优势，减少磁盘存取次数，本系 统采用了缓冲区来管理b + 树中的根结点，使用一种标准的方法u t u ( 最近最少 使用的先淘汰算法) 缓冲管理策略来更新缓冲区中b + 树根结点。如果被检索的 索引的根结点在缓冲区内，那么通过读出缓冲区中该索引根节点信息，我们能 得到索引所在磁盘的位置，从而能快速在磁盘中找到相应的记录位置。 只存放b + t r e e 的根节点 咖c tn o d e ir i m u ff 1 1 1 d e x h e a d 诅g m d e x h e a d ； 索引的信息头 w o r d d w a c c e s s t i m e s ；该节点当前被访问的次数 n o d e n o d e d a t a ；是否存在d i s t i n c t 终结符的标识 d w o r d c d a t a u p d a 旭：8 ，标志位，表示该缓冲区中的数据是否 需要重新写回磁盘上 w r e s e r v e ：2 4 ；保留位 ； 从以上设计的结构可以看出：每当通过访问索引文件来检索记录时，首先 查看此索引的根结点是否在缓冲区中，如果在缓冲区中，则直接读出此索引的 信息头和该索引的根节点信息，同时更新该索引的访问次数，如果不在缓冲区 中，则需在索引文件中检索该索引，同时根据缓冲区中各个索引的访问次数， 利用l r u 策略来更新缓冲区结构的内容。 武汉理工大学硕士学位论文 第4 章数据库查询处理器设计 前面几节讨论数据库的物理存储，包括记录的存储和索引的存储。然而这 只是整个数据库引擎的数据来源。用户一般是4 i 会涉及到这样底层的东西，他 们一般是通过执行s q l 语句来获得他们想要的信息。这里就需要利用编译原理 中的一些知识来完成对s o l 语句的解析和执彳亍，也就是我们这里所说的查询处 理器。 查询处理器是d b m s 中的一个部件集合，它能够将用户的查询和数据修改 命令转变为数据库上的操作序列，并且执行这些操作。下图5 1 表明了处理器的 主要部分，以及处理器各部分与编译原理中各相关阶段的关系 。 ls q l 语句 i诃洁分析 语法分析 + 语义分析 f虚拟机代码生成 l虚拟机 i底层碰盘操作 图4 i 查询处理器的主要部分、解析和执行s q 语句的框架以及对应关系 从数据库实现角度来讲，查询处理器分为以下两部分。 查询编译：对输 的s o l 语句进行词法分析、语法分析、语义分析。利用 作用在包上的关系代数把语法分析得到的语法树转换成代数表达式树，从而生 成逻辑查询计划。为逻辑查询计划的每一个操作符选择实现的算法，并选择这 些操作符的执行顺序，逻辑计划被转化为物理查询计划。 查询执行：考虑如何执行查询编译s q l 语句后所生成的物理查蜘计划。主 查询执行：考虑如何执行查询编译s q l 语句后所生成的物理查询计划。主 武汉理工大学硕士学位论文 要讨论与这些物理查询计划相关的算法和物理查询所生成的虚拟机代码。 从编译原理角度来讲，s q l 语句在开发者的眼里就是一段源语言程序，而 执行s q l 查询的程序则是一个编译程序。当一个包含s q l 语句的字符串将要被 执行的时候，首先它被传送给词法分析程序。词法分析程序的任务就是将原始 的字符串分割成一个个标识符并把它们传递给语法分析程序。语法分析程序是 根据标识符的上下文来决定它们具体的含义。当语法分析程序将标识符组装成 一条完熬的s q l 语句后，接着进行相关的语义分析，最后调用代码生成器产生 虚拟机代码，而这些代码用来完成s q l 语句所指定的工作。系统中所产生的虚 拟机代码是运行在虚拟机之上的，虚拟机通过游标操作磁盘上的数据，最后将 查询的数据提交给用户。 下面结合编译原理知识和s o l 语法，从查询处理器的两个部分( 查询编译、 查询执行) 出发来阐述如何处理s q l 语句，得到s q l 语句执行的结果。 4 1 查询编译模块 4 1 1 语法分析 词法分析阶段是编译过程的第一阶段。词法分析的主要任务是读入输入字 符流，进行扫描和分解，过滤掉字符流中出现的空格字符以及其它非实质性字 符，从而识别出各个基本语法单位( 也称单词或语法符号) ，同时产生单词的记 号序列，提供给语法分析使用。所识别出的字符是逻辑上紧密相连的一组字符， 具有集合含义。比如标识符是一个字符后跟随零个或多个字母或数字组成的字 符串。保留字( 关键字或基本字) 是一种单词，此外还有算符，界符等等。这里词 法分析采用构造状态转换图的方式来识别单词。 语法分析是编译过程的第二阶段。语法分析的任务在词法分析的基础上， 分析源程序的结构，判别它是否为相应语言中的一个合法表达。如“程序”，“语 句”，“表达式”等等。语法分析所采用的一般途径是由语法分析程序为源程序构 造一棵完整的语法树。语法分析所依据的是语言的语法规则，即描述程序结构 的规则。通过语法分析我们可以确定整个输入串是否构成一个语法上正确的程 序 1 8 1 。 由于本系统的重点在于对输入的s q l 语句进行语义分析，因此语法分析采 武汉理工大学硕士学位论文 用语法分析自动产生器来完成。目前主要的语法分析器有。y a c c ”、“b i s o n 和 “l e m o n 噬窨。其中l e m o n 是一个产生c 或c 抖代码的l a l r ( 1 ) 文法产生器。本 系统采用l e m o n 文法生成器来进行语法分析。 比较“y a c c ”和“b i s o n ”语法分析器而言，l e m o n 文法生成器的优势在于：它 通过使用更加成熟的分析引擎，使得运行速度比两者更快，同时它是线程级安 全的；另外“l e m o n ，采用非终结符析构器的机制，有效消除了资源泄漏的问题 口”。即使在编译过程中发现语法错误，也不会产生内存泄漏。因此它更加适合 于长时间不间断工作的环境。“l 锄o n ”在整个s o l 执行过程中的位置如图4 2 。 h r n o n 源程序 4 1 2 语义分析过程 图4 2l o n 示意图 输出 语义分析阶段分为三个部分 1 7 】 1 8 】： ( 1 ) 检测s q l 语句的语义错误。例如检测输入的s q l 语句所涉及的表名、列 名是否存在、表达式和语句中的操作符和操作数的类型是否匹配等等。 ( 2 ) 把语法分析生成的语法分析树转化为关系代数表达式树( 或某种类似的 标记) ，这一过程称之为逻辑查询计划。 ( 3 ) 为了方便查询执行阶段的工作，这里需要把逻辑查询计划进一步转换为 物理查询计划。 由于l e m o n 文法生成器采用自底向上归约的方法进行语法分析，因此语义 分析在文法归约的同时进行。 系统中我们定义了如下的结构体来保存所解释出来的语义。这个结构是进 行语义分析阶段和虚拟机代码生成阶段( 后面一节将进行详细讲述) 的重要数 据结构，它主要存放s 0 l 语句相关信息的结构体。而且作为全局变量携带信息， 此结构贯穿s o l 语句解析的整个过程。 武汉理工大学硕士学位论文 s 仃u c tp a r s e s q l + 曲；存储数据库的总体结构 i n tr c ； s o l 语句执行的返回值 s q lc a l l b a c kx c a l l b a c k ；回调函数 c h a rt z e 玎l 订s g ； 错误信息 t o k e ns e r r t b k e n ； 错误发生时对应的t o k e n t 0 k e ns f i r s t t 0 k e n ： 解析的第一个t o 圈b n t 0 k e ns l a s t t o k e n ； 解析的最后一个t o i ( i n t a b l e + p n e w t a b l e ：由c r e a t e 吖国l e 子旬创建的表的信息 v d b e p v d b e ； 执行该语句的虚拟机 u 8e x p l a i n ； 在s q l 查询中发现e x p l a n 标志 u 8i i l i t f l a g ； 如果编译的是c r e a t e1 纰l e 语句，则为真 u 8u s e a g g ； 如果把集合表达式的值定义为新的字段，则为真 u 8u s e c a l l b a c k ：是否采用回调函数显示结果 n 1 1 e r r ：发现的错误数量 血n 1 曲；虚拟机游标的数量 血n a g g ； 集合表达式的数量 i 1 1 tn 、缸； s q l 语句中”? ”字符的数量 a g 班x p r a a g g ； 集合表达式的数组 ； 在上述结构中，指向s o l 结构的指针变量d b 、指向v d b e 结构的指针变量 p v d b e 是p a r s e 结构的核心部分。s q l 结构用来存储所有语义分析过程中所涉及 的数据库的逻辑结构，如数据库表、字段等信息。v d b e 结构用来存储语义分析 完成后所生成的虚拟机代码。 4 1 3 检测s q l 语句的语义错误 这一阶段的主要工作是检测s q l 语句中所涉及的表名、表的字段名是否存 在等等。为了更好的说明整个语义分析的过程，这里以具体的语法树来进行说 明。 ( 1 ) s q l 的一个简单子集的语法 通过给出可用于s q l 子集的语言的某些规则，借此简要说明语法