嵌入式数据库的设计与实现

太原科技大学硕士学位论文嵌入式数据库的设计与实现姓名：解辉申请学位级别：硕士专业：计算机应用技术指导教师：徐玉斌;李建伟20080701嵌入式数据库的设计与实现中文摘要嵌入式数据库是近些年才兴起的一项新的数据库技术，它以目前成熟的数据库技术为基础，针对嵌入式设备的具体特点，实现对移动设备和嵌入式设备上数据的存储、组织和管理。传统的数据库系统一般都是运行在大型的计算机设备上，包括主机系统和各种各样的服务器，随着计算设备的日益小型化，数据库的小型化也日益迫切。与大型计算机设备相比，这些小型的计算设备内存较小，硬盘也较少，因此简单地将原来的大型数据库移植到小型设备上效果并不好，必须依据这些设备的特点专门设计相应的数据库系统。针对嵌入式系统的需求，文章主要在两个方面进行了研究。首先，本文在综合分析当前嵌入式数据库系统的主要功能和发展现状的基础上，以实用、体积小、便于嵌入式应用为主要追求目标，针对嵌入式设备的具体特点，完成了词法分析器、语法分析器以及索引机制优化等方面的研究与设计，并在Ｌｉｎｕｘ下用Ｃ语言设计了一款能有效存储、操作和管理实时数据信息的嵌入式数据库，用以实现对嵌入式设备数据的统一管理。此数据库具有微小内核、系统尺寸可剪裁、良好的跨平台性以及灵活的应用编程接口等特点，支持ＡＣＩＤ事务，支持ＳＱＬ９２标准子集，无须独立运行的数据库引擎，由程序直接调用相应的ＡＰＩ函数就可以实现对数据的存取操作。通过与ＳＱＬＩＴＥ的测试比较可以看出，本文设计的数据库在操作涉及的数据量较小的情况下，插入、查找和删除性能均有较大提高，比较适合于应用到数据操作较少的嵌入式设备。其次，基于ＡＲＭ硬件平台，采用Ｌｉｎｕｘ操作系统，在已开发完成的嵌入式数据库进行数据管理的基础上，设计了一个嵌入式实时数据采集系统。此系统很好的解决传统数据采集系统存在的数据管理混乱、存储效率低下等不足，在复杂环境下能够对多种数据信息进行实时采集、高效存储管理和快速传输。关键词：嵌入式系统；嵌入式数据库；ＡＲＭ；ＬＩＮＵＸＴｈｅＲｅｓｅａｒｃｈａｎｄＤｅｓｉｇｎｏｆＥｍｂｅｄｄｅｄＤａｔａｂａｓｅＧｒａｄｕａｔｅＮａｍｅ：ＸｉｅＨｕｉＭａｊｏｒ：ＣｏｍｐｕｔｅｒＡｐｐｌｉｅｄＴｅｃｈｎｏｌｏｇｙＬｉＪｉａｎ－ｗｅｉＤｉｒｅｃｔｅｄｂｙ：ＸｕＹｕ—ｂｉｎＡＢＳＴＲＡＣＴＥｍｂｅｄｄｅｄＤａｔａｂａｓｅｉｓｒｅｃｅｎｔｙｅａｒｓ．Ｂａｓｅｄｏｎａｎｅｗｔｅｃｈｎｏｌｏｇｙｏｆｄａｔａｍａｎａｇｅｍｅｎｔｒｉｓｉｎｇｉｎｍａｔｕｒｅｄａｔａｂａｓｅｔｅｃｈｎｏｌｏｇｙａｎｄｓｐｅｃｉａｌｅｍｂｅｄｄｅｄｏｎｄｅｖｉｃｅ，ｉｔｉｍｐｌｅｍｅｎｔｓｔｈｅｄａｔａ’Ｓｓｔｏｒａｇｅ，ｏｒｇａｎｉｚａｔｉｏｎａｎｄｍａｎａｇｅｍｅｎｔｍｏｂｉｌｅｄｅｖｉｃｅｓａｎｄｅｍｂｅｄｄｅｄｄｅｖｉｃｅｓ．Ｔｒａｄｉｔｉｏｎａｌｌｙ，ｄａｔａｂａｓｅｓｙｓｔｅｍｓｒｕｎｏｎｌａｒｇｅ—ｓｃａｌｅｃｏｍｐｕｔｅｒｅｑｕｉｐｍｅｎｔｔｈｅｃｏｍｐｕｔｅｒｉｎｃｌｕｄｉｎｇｈｏｓｔｃｏｍｐｕｔｅｒｓｙｓｔｅｍｓａｎｄａｌｌｋｉｎｄｓｏｆｓｅｒｖｅｒｓ．Ａｓｅｑｕｉｐｍｅｎｔｇｏｓｍａｌｌｅｒａｎｄｓｍａｌｌｅｒ，ｔｈｅｄａｔａｂａｓｅ’ＳｍｉｎｉａｔｕｒｉｚａｔｉｏｎｉＳｕｒｇｅｎｔｌｙ．Ｃｏｍｐａｒｅｄｗｉｔｈｌａｒｇｅ．ｓｃａｌｅｃｏｍｐｕｔｅｒｓ，ｔｈｅｓｅｓｍａｌｌ—ｓｃａｌｅｃｏｍｐｕｔａｔｉｏｎａｌｕｎｉｔｓａｒｅｃｈａｒａｃｔｅｒｉｚｅｄｂｙｓｍａｃｋａｓｍｅｍｏ巧ａｎｄｍｉｎｏｒｈａｒｄｗａｒｅｅｖｅｎｔｈｅｙｈａｖｅｎｏｈａｒｄｗａｒｅｓｕｃｈｈａｎｄ．ｈｅｌｄｄｅｖｉｃｅｓａｎｄｉｎｔｅｌｌｉｇｅｎｔｈｏｕｓｅｈｏｌｄｅｌｅｃｔｒｏｎｉｃｓ．Ｓｏ，ｉｔｉＳｎｏｔｆｅａｓｉｂｌｅｔｏｉｕｓｔｔｒａｎｓｐｌａｎｔｌａｒｇｅ．ｓｃａｌｅｄａｔａｂａｓｅｔｏｓｍａｌｌ－ｓｃａｌｅｄｅｖｉｃｅｓ．ｄａｔａｂａｓｅＷｅｍｕｓｔｃｈａｒａｃｔｅｒｓ．ｓｐｅｃｉａｌｌｙｄｅｓｉｇｎｅｄｓｙｓｔｅｍｓｔｏｆｉｔｆｏｒｔｈｅｄｅｖｉｃｅｓ’Ｃｏｎｓｉｄｅｒｉｎｇｔｈｅｄｅｍａｎｄｏｆｔｈｅｅｍｂｅｄｄｅｄｓｙｓｔｅｍｓ，ｔｈｅｐａｐｅｒｗｉｌｌｓｈｏｗｆｕｎｃｔｉｏｎａｎｄｔｈｅｔｈｅｐｒｏｊｅｃｔｉｎｓｔａｔｅｔｗｏｐａｒｔｓ．Ｆｉｒｓｔｌｙ，ｔｈｒｏｕｇｈｏｆａｎａｌｙｚｉｎｇｔｈｅｍａｉｎｓｙｓｔｅｍａｃｔｕａｌｃｕｒｒｅｎｔｅｍｂｅｄｄｅｄｄａｔａｂａｓｅｓｙｎｔｈｅｔｉｃａｌｌｙ，ｔｈｅｅｍｂｅｄｄｅｄｄａｔａｂａｓｅ，ｔｈｅｇｏａｌｏｆｗｈｉｃｈｉｓａｖａｉｌａｂｉｌｉｔｙ，ｓｍａｌｌｓｉｚｅａｎｄｃｏｎｖｅｎｉｅｎｃｅｆｏｒｅｍｂｅｄｄｅｄａｐｐｌｉｃａｔｉｏｎｓｉｓ，ｄｅｓｉｇｎｅｄｒｅｆｅｒｓｔｏａｃｃｉｄｅｎｃｅａｎａｌｙｚｅｒ，ｓｙｎｔａｘａｎａｌｙｚｅｒａｎｄｔｈｅｏｐｔｉｍｉｚａｔｉｏｎｏｆｉｎｄｅｘｍｅｃｈａｎｉｓｍａｎｄＳＯｏｎ．Ａｉｍｉｎｇａｔｔｈｅｃｏｎｃｒｅｔｅｆｅａｔｕｒｅｓｏｆｅｍｂｅｄｄｅｄｄｅｖｉｃｅｓ，ｔｈｅｅｍｂｅｄｄｅｄｄａｔａｂａｓｅｓｙｓｔｅｍｄｅｓｉｇｎｅｄｉｎＬｉｎｕｘ，ｗｈｉｃｈｃｏｕｌｄｓｔｏｒｅ，ｏｐｅｒａｔｅｉｎｆｏｒｍａｔｉｏｎａｐｐｌｉａｎｃｅｓｅｆｆｅｃｔｉｖｅｌｙ．ＩｔｓｕｐｐｏｒｔｓａｎｄｍａｎａｇｅｔｈｅｄａｔａｏｆｔｈｅＡＣＩＤａｆｆａｉｒ，ＳＱＬ９２ＩＩＩｓｔａｎｄａｒｄｓｕｂｓｅｔ，ｉｎｔｅｇｒａｔｅｄｗｉｔｈｉｔｓｃｏｎｃｒｅｔｅａｐｐｌｉｃａｔｉｏｎａｎｄｔｈｅｅｍｂｅｄｄｅｄＬｉｎｕｘａｎｄｄｏｅｓｎ’ｔｎｅｅｄｕｎａｔｔａｃｈｅｄｒｕｎｎｉｎｇｅｎｇｉｎｅ，ｔｈｅｐｒｏｇｒａｍｃａｌｌｓｉｔｓｒｅｌｅｖａｎｔＡＰＩｆｕｎｃｔｉｏｎｔｏｒｅａｌｉｚｅｔｈｅａｃｃｅｓｓｏｐｅｒａｔｉｏｎ．ＴｈｒｏｕｇｈｃｏｍｐａｒｉｎｇｗｉｔｈｔｈｅＳＱＬＩＴＥ，ｔｈｅｄａｔａｂａｓｅ’ｓｐｅｒｆｏｒｍａｎｃｅｈａｓｉｍｐｒｏｖｅｄｇｒｅａｔｌｖｗｈｉｌｅｉｎｖｏｌｖｉｎｇｒｅｌａｔｉｖｅｌｙｓｍａｌｌａｍｏｕｎｔｏｆｄａｔａ，ｗｈｉｃｈｉｓｆｉｔｆ．ｏｒｔｈｅｅｍｂｅｄｄｅｄｄｅｖｉｃｅｓｗｈｉｃｈｔｒｅａｔｌｅｓｓｄａｔａ．Ｓｅｃｏｎｄｌｙ，ｔｈｅａｒｔｉｃｌｅｂａｓｅｄｏｎＡＲＭａｎｄＬｉｎｕｘｏｐｅｒａｔｉｏｎｓｙｓｔｅｍ，ｕｓｉｎｇｔｈｅｅｍｂｅｄｄｅｄｄａｔａｂａｓｅｄｅｓｉｇｎｅｄｉｎｔｈｅｆｉｒｓｔｐａｒｔｔｏｍａｎａｇｅｔｈｅｒｅａｌ＿ｄａｔａｓｙｓｔｅｍｃａｎｔｏｄｅｓｉｇｎａｒｅａｌ—ｔｉｍｅｄａｔａａｃｑｕｉｓｉｔｉｏｎｓｙｓｔｅｍ．Ｔｈｅａｓｃｏｎｑｕｅｒｔｈｅｄｅｆｅｃｔｉｎｔｒａｄｉｔｉｏｎａｌｄａｔａａｃｑｕｉｓｉｔｉｏｎｓｙｓｔｅｍ．ｓｕｃｈｄａｔａｍａｎａｇｅｍｅｎｔｃｈａｏｓａｎｄ１０Ｗｓｔｏｒａｇｅｅｆｆｉｃｉｅｎｃｙ，ａｎｄｈａｖｅａｇｏｏｄｉｎｐｅｒｆｏｒｍａｎｃｅｏｆｅｆｆｉｃｉｅｎｔｓｔｏｒａｇｅａｎｄｒａｐｉｄｃｏｍｐｌｅｘｅｎｖｉｒｏｎｍｅｎｔ．ｔｒａｎｓｍｉｓｓｉｏｎｗｈｉｌｅｂｅｉｎｇＫｅｙｗｏｒｄｓ：ＥｍｂｅｄｄｅｄＳｙｓｔｅｍ；ＥｍｂｅｄｄｅｄＤａｔａｂａｓｅ；ＡＲＭ；ＬｉｎｕｘＩＶ承水诺话书吊本人郑重声明：所呈交的学位论文，是在导师指导下独立完成的，学位论文的知识产权属于太原科技大学。如果今后以其他单位名义发表与在读期间学位论文相关的内容，将承担法律责任。除文中已经注明引用的文献资料外，本学位论文不包括任何其他个人或集体已经发表或撰写过的成果。学位论文作者（签章）：２００年月日第一章绪论第一章绪论１．１研究背景及意义随着计算环境的发展，数据库系统也从集中式、分布式发展到今天的嵌入式数据库系统。与通用的桌面系统不同，由于嵌入式系统没有充足的内存和磁盘资源，因此，不论是嵌入式的操作系统还是数据库管理系统，都要占用最小的内存和磁盘空间。若采用大型的商用数据库管理系统，则不可避免的占用大量的内存和磁盘空间，同时会产生大量的冗余数据，因此，它不能应用于嵌入式系统的数据管理。长期以来，商业数据库行业都在不停的追逐高性能的事务处理以及复杂的查询处理能力，并制定了相应的行业标准。但是对嵌入式数据库系统来说，嵌入式应用系统之间差别很大，因此它们对嵌入式数据库系统的要求较高，这主要表现在：易于维护、高度可靠性和小巧性。嵌入式系统内存较小，ＣＰＵ速度慢，因此，在嵌入式数据库系统中数据的结构和算法以及数据查询处理算法非常关键，必须采用合适的策略和特殊的数据结构、算法才能满足用户的需求…。１．２国内外研究现状嵌入式数据库（ＥＤＢ）在移动计算平台、家庭信息环境、通讯计算平台、电子商务平台等领域得到广泛的应用。正是基于这一事实，各国研究机构纷纷展开了对嵌入式数据库的研究，各大数据库厂商也将开发相应主打数据库系统的嵌入式数据库系统作为一个重要的发展方向。在国外，ＩＢＭ公司在ＤＢ２通用数据库中推出了ＩＢＭＤＢ２Ｓａｔｅｌｌｉｔｅ和Ｅｖｅｒｙｐｌａｃｅ版本，它所提供的移动计算功能使移动办公用户获得了与企业数据保持同步的能力。同时Ｉｎｆｏｒｍｉｘ公司也由旗下的Ｃｌｏｕｄｓｃａｐｅ公司推出了其移动解决方案旗舰产品的最新版本Ｃｌｏｕｄｓｃａｐｅ３．０，可以对包括从服务器到笔记本电脑，甚至到轻型信息设备，进行数据管理。而作为移动计算的市场领先者Ｓｙｂａｓｅ公司多年前就敏锐地预见到计算设备小型化的发展趋势，投入了大量的人员和资金对小型数据库进行研究与开发工作，并且在全球最早推出了移动与嵌入数据库产品包－ＳｙｂａｓｅＳｔｕｄｉ０．ＳＯＬＡｎｙｗｈｅｒｅ在国内，面对着嵌入式数据管理领域新的市场需求，东北大学软件中心凭借着多年积累的数据库系统和嵌入式系统的开发经验，在大型数据库管理系统ＯｐｅｎＢＡＳＥ的基础上，研制开发了嵌入式数据库管理系统ＯｐｅｎＢＡＳＥＭｉｎｉ。北京人大金仓信息技术嵌入式数据库的设计与实现有限公司也凭借其强大的研发实力，推出了具有自主知识版权的小金灵嵌入式移动关系数据库系统ＫｉｎｇｂａｓｅＬｉｆｅ硷１。以上这些嵌入式数据库系统在功能和性能上具有一定的共性，比如说一般对资源要求较低，占用内存空间较小，从几十Ｋ到几百Ｋ不等，支持Ｃ编程接口和标准ＳＱＬ子集的开发接口，支持ＯＤＢＣ或ＪＤＢＣ，能与支持其标准的任意数据库交换数据，支持双向数据交换能力，实现了中央数据库与嵌入式数据库间的数据双向流动等。但这些数据库系统也有各自不同的特点，鉴于嵌入式领域的特点，对嵌入式数据库产品还很难形成统一的标准，对嵌入式数据库管理系统的研究，也还有很多工作要做。１．３本文的研究目标和研究内容目标是在研究现有嵌入式数据库的基础上设计和实现一个具有如下特征的嵌入式数据库：１）零配置，程序驱动。２）实现部分的ＳＱＬ９２标准。３）数据库完整存储在磁盘文件中。４）提供简单明了的ＡＰＩ。本文的研究内容主要包括以下几方面：１．第一章主要介绍了嵌入式数据库系统研究的意义、国内外的研究现状以及本文研究的主要内容。２．第二章主要介绍了嵌入式系统，嵌入式操作系统和嵌入式数据库的特点和体系结构。３．第三章对嵌入式数据库进行概要设计和详细设计并初步实现一个可运行的嵌入式数据库。４．第四章基于第三章开发完成的ＥＤＢ的基础上，设计并实现嵌入式数据采集系统。５．第五章对第三章开发的ＥＤＢ和第四章开发的数据采集系统进行测试。６．第六章进行总结与展望。２第二二章嵌入式系统与嵌入式数据库第二章嵌入式系统与嵌入式数据库２．１嵌入式系统２．１．１嵌入式系统的定义嵌入式系统（ＥｍｂｅｄｄｅｄＳｙｓｔｅｍ）是以应用为中心，以计算机技术为基础，并且软硬件可裁剪，适用于应用系统对功能、可靠性、成本、体积、功耗有严格要求的专用计算机系统∞３。它一般由嵌入式微处理器、外围硬件设备、嵌入式操作系统以及用户的应用程序等四个部分组成，用于实现对其他设备的控制、监视或管理等功能。２．１．２嵌入式系统的特点嵌入式系统的核心是嵌入式微处理器，嵌入式微处理器一般具备以下４个特点Ｈ３：（１）对实时多任务有很强的支持能力，能完成多任务并且有较短的中断响应时间，从而使内部的代码和实时内核的执行时间减少到最低限度。（２）具有功能很强的存储区保护功能。这是由于嵌入式系统的软件结构已模块化，而为了避免在软件模块之间出现错误的交叉作用，需要设计强大的存储区保护功能，同时也有利于软件诊断。（３）可扩展的处理器结构，以能最迅速地开展出满足应用的最高性能的嵌入式微处理器。（４）嵌入式微处理器必须功耗很低，尤其是用于便携式的无线及移动的计算和通信设备中靠电池供电的嵌入式系统更是如此。２．１．３嵌入式系统的应用嵌入式系统的应用前景是非常广泛的，人们将会无时无处不接触到嵌入式产品，从家里的洗衣机、电冰箱，到作为交通工具的自行车、小汽车，到办公室里的远程会议系统等等。当嵌入式的无线电芯片的价格可被接受时，它的应用可能会无所不在。在家中、办公室、公共场所，人们可能会使用数十片甚至更多这样的嵌入式无线电芯片，将一些电子信息设备甚至电气设备构成无线网络，在车上、旅途中，人们利用这样的嵌入式无线电芯片可以实现远程办公、远程遥控，真正实现把网络随身携带瞄３。２．２嵌入式操作系统２．２．１嵌入式操作系统的定义嵌入式操作系统是一种支持嵌入式系统应用的操作系统软件，它是嵌入式系统３嵌入式数据库的设计与实现（包括硬、软件系统）极为重要的组成部分，通常包括与硬件相关的底层驱动软件、系统内核、设备驱动接口、通信协议、图形界面、标准化浏览器等ｂｒｏｗｓｅｒ［６］。嵌入式操作系统具有通用操作系统的基本特点，如能够有效管理越来越复杂的系统资源；能够把硬件虚拟化，使得开发人员从繁忙的驱动程序移植和维护中解脱出来；能够提供库函数、驱动程序、工具集以及应用程序。２．２．２嵌入式操作系统的特点嵌入式操作系统具有以下一些特点哺１：（１）体积小。嵌入式系统有别于一般的计算机处理系统，它不具备像硬盘那样大容量的存储介质，而大多使用闪存（ＦｌａｓｈＭｅｍｏｒｙ）作为存储介质。这就要求嵌入式操作系统只能运行在有限的内存中，不能使用虚拟内存，中断的使用也受到限制。因此，嵌入式操作系统必须结构紧凑，体积微小。（２）实时性。大多数嵌入式系统都是实时系统，而且多是强实时多任务系统，要求相应的嵌入式操作系统也必须是实时操作系统（ＲＴＯＳ）。实时操作系统作为操作系统的一个重要分支已成为研究的一个热点，主要探讨实时多任务调度算法和可调度性、死锁解除等问题。（３）特殊的开发调试环境。提供完整的集成开发环境是每一个嵌入式系统开发人员所期待的。一个完整的嵌入式系统的集成开发环境一般需要提供的工具是编译／连接器、内核调试／跟踪器和集成图形界面开发平台。其中的集成图形界面开发平台包括编辑器、调试器、软件仿真器和监视器等。２．３嵌入式数据库２．３．１嵌入式数据库定义嵌入式数据库是指运行在本机上、不用启动服务端的轻型数据库，它与应用程序紧密集成，被应用程序所启动，并伴随应用程序的退出而终止。２．３．２嵌入式数据库的特点嵌入式数据库系统有如下主要特点ｎ’：（１）占用存储空间小（２）可靠性、可管理性和安全性（３）互操作性和可移植性。２．３．３嵌入式数据库的关键技术为了使嵌入式系统能更好地发挥其作用，主要涉及以下几种关键技术发展方向：（１）系统的高可靠性技术（２）系统整体的微型化（３）数据同步／复制技术（４）系统可定制能力（５）系统可移植性与多平台支持（６）网络支持与数据。４第三章嵌入式数据库的分析与设计第三章嵌入式数据库的分析与设计本章将讨论如何分析和设计一个嵌入式数据库系统，包括数据库的功能需求、性能需求、运行环境、开发环境、系统架构以及各模块和模块间的关系等。３．１嵌入式数据库的体系结构嵌入式ＥＤＢ是指可在嵌入式设备中独立运行的一种数据库系统，用以处理大量的、时效性强且有严格时序的数据，它以高可靠性、高实时性和高信息吞吐量为目标，其数据的正确性不仅依赖于逻辑结果，而且依赖于逻辑结果产生的时间随１，嵌入式系统基本结构如图３－１所示。图３－１嵌入式系统基本结构目前嵌入式系统开发中，在嵌入式数据库问题上的多数看法是，嵌入式数据库从本质上说是一个“内存数据库”，是一个由应用程序管理的内存缓冲池，它在系统中的作用就是一个供多个实时任务共同使用的共享数据区。这种数据库实际上是一个嵌入在用户应用软件中的与应用程序不可分割的部分，其功能主要是数据的存和取，不具有独立性，不是一个真正意义上的数据库系统睁１。一个完整的嵌入式实时数据库系统除了包括内存数据库外，还应当含有历史数据库和数据库管理系统ＤＢＭＳ及提供给用户的接口函数，整个数据库可由ＤＢＭＳ完成对数据库的具体配置及各种操作，例如系统运行前根据实际需要对内存数据库中的记录节点进行增减等配置操作，嵌入式数据库库的模块结构如图３－２所示。５嵌入式数据库的设计与实现图３—２嵌入式ＥＤＢ的模块结构嵌入式数据库的关键是数据模型的确立，它决定了数据被访问和操作的方式，应６３．２嵌入式数据库的数据模型用程序的性能和可靠性也大部分取决于此。目前嵌入式环境下的数据库系统多数采用了关系模型结构，这也是商用数据库系统的数据模型，该模型结构是利用二维表来实现数据存储，利用索引访问和查询数据，这种模型结构是建立在严格的数学基础上的，结构简单灵活，独立性好，但在嵌入式环境下的内存开销和数据冗余较大，用户必须对其进行优化，增加了开发数据库系统的难度；有些嵌入式数据库则采用了网状模型结构，该模型通过指针来确定数据间的显式连接关系，它比关系模型中利用冗余数据和索引文件要节约大量的存储空间，具有一定的数据独立性和共享特性，运行效率较高，而且由于它避免了索引操作，比关系型数据库模式要节省存储空间，数据操作速度也更快ｎ０１。但是这种模型结构比较复杂，尤其当嵌入式系统规模增大时，其数据库的结构变得非常庞大，可能会影响到系统的实时性能。图３—３所示的是在相同数目的记录下，关系模型和网状模型的系统开销比较，从图中可以得知，网状模型因为避免了索引操作使得其开销要小于关系模型ｎｕ。７嵌入式数据库的设计与实现３．４嵌入式数据库的运行过程和开发过程３．４．１运行过程ＥＤＢ的运行过程是一个在数据库引擎总控模块的控制下进行的有序协调的过程。ＥＤＢ的运行过程分为５个步骤ｎ别。（１）数据库系统初始化ＥＤＢ的初始化调用ＡＰＩ的初始化函数启动，初始化数据库系统的全局控制结构，取数据库的运行状态信息，分配数据库内存空间，ＥＤＢ系统初始化时还将对数据字典表进行确认ｎ朝。（２）打开或创建字典表在数据库系统第一次启动时，即数据库第一次被装入时，该字典表是不存在的，在这里初始化时将创建字典表，为后续操作做好准备。在数据库系统以后的启动过程中，如果该字典己经存在，数据库系统初始化时将确认字典表是否已存在，此时如果检查到字典表不存在，将重新打开一个字典表。（３）数据库具体操作ＥＤＢ系统及其具体的字典表操作初始化后就可以在数据库操作引擎控制下调用数据存取模块或数据库维护模块对数据库进行各种操作了。对基本表的主要操作有：创建基本表、插入记录、删除记录、修改记录、查找、排序、备份和恢复以及碎片整理等，我们将在第四章对重要功能的操作流程和实现进行详细介绍。（４）关闭字典表关闭字典表后可以释放已经分配的输出缓冲区空间、结果集结构空间、控制头结构、列定义信息等内部结构变量空间，并可以释放该字典表占用的类信息结构。……（５）关闭数据库系统通过调用ＡＰＩ的关闭函数实现。主要工作是关闭数据库，释放ＥＢＤ系统申请的全局结构变量空间即ＤＢ结构，释放并分配给ＥＤＢ的空间。实际运行过程中，数据库系统初始化后，若字典表创建成功或己存在的条件下，可对字典表进行多次的打开操作和关闭操作ｎ４１。３．４．２开发过程ＥＤＢ的开发过程是按照软件工程的思想来组织实施的。开发过程依次经历了原型阶段，需求分析阶段，概要设计阶段，详细设计阶段，编码阶段，测试阶段，以及维护阶段。８第三章嵌入式数据库的分析与设计在原型阶段，主要是在台式机上围绕着ＥＤＢ的一些基本功能，如表创建，记录的插入、删除、修改等操作，在ＰＣ机上予以实现，以获得对将要开发的系统的一个初步的认识。实际开发的原型是在Ｌｉｎｕｘ环境下实现的。在需求分析阶段，主要是根据用户的要求，进一步细化系统应该具有的功能和性能要求，和用户达成一致，并为下一步的系统概要设计打好基础。在概要设计阶段，基本上确定了系统的体系结构，确定了系统向用户所提供的ＡＰＩ接口，确定了系统各个组成模块之间的关系，确定了系统的一些核心数据结构。在详细设计阶段，主要是设计各个模块具体函数的伪代码或流程图实现。在编码阶段，主要工作就是编码并调试，以实现系统预定的功能ｎ朝。在测试阶段，测试工作非常重要，除了在系统开发的各个阶段都贯穿了一些测试的内容外，还专门安排了一个比较长时间的测试阶段。测试阶段包含了功能测试，健壮性测试，性能测试等多个测试环节，经过测试阶段，系统的质量和稳定性都得到了比较大的提高。３．５概要设计３．５．１功能需求嵌入式数据库系统作为ＤＢｂｌＳ，它应当具备以下功能：（１）数据定义和数据存储这部分内容包括元组的表示，属性的表示，索引的表示，元组和属性的关系，各种数据类型的表示和存储，如整型（长整型、短整型）、字符型、实型、日期类型、时间类型等。数据文件表的格式和组织，索引文件表的格式和组织，元数据的组织和存储等等ｎ钔。（２）数据存取能实现对数据库的基本操作，如建立表，建立索引，删除表，删除索引，对元组的检索和更新操作（插入、删除、修改），其它的操作还包括排序、压缩、整理等功能。必须支持ＳＯＬＤＤＬ和ＤＭＬ一个较完备的子集。（３）访问接口嵌入式数据库系统需要提供共应用程序开发人员使用的访问接口，而且应当是符合ＳＯＬ标准的访问接口。（４）缓冲区管理为提高系统性能，减少磁盘Ｉ／ｏ操作，对数据表文件的读写必须提供缓冲机制，９嵌入式数据库的设计与实现操作系统的文件系统提供的文件缓冲是远为不够的，嵌入式数据库系统自身应该有出色的缓冲区管理功能ｎ引。（５）内存管理占用最少的内存资源和内存资源可控制是嵌入式数据库的首要目标。合适的内存管理策略，不仅有助于达到这个目标，而且有助于保护系统的堆空间，增强系统的可靠性。（６）数据库管理工具嵌入式数据库还需要一组实用工具，供用户在线或离线管理数据库，这样的工具包括数据库元数据的报表打印、数据库一致性的检查、数据库表的数据导入导出工具、碎片整理和压缩等。３．５．２性能需求衡量嵌入式数据库的性能要求有两个方面，一是作为ＤＢＭＳ系统，其性能如何，数据库中最多数据表的个数，数据表的最大文件长度，每个表的最大元组个数，每元组的最多属性个数，每个表上建立的最多索引数等等，二是作为嵌入式系统软件，其性能如何，包括内存资源占用，ＣＰＵ开销等。前文我们说过，嵌入式数据库和应用密切相关，所以有些性能指标比如响应时间或事务处理平均时间就难以确定，我们只能给出合理的参考值要求（针对特定的硬件平台）。当然，大多数的指标还是可以确定的。其它性能要求还包括对可靠性的要求，嵌入式数据库系统要保证在无人管理的情况下长时间的无故障运行ｎ６１。而且，在系统发生故障不能恢复的时候，也不可干扰或破坏设备中其它部件的正常工作。嵌入式数据库系统还应当具备良好的可伸缩性，根据不同的应用能够为系统进行定制，比如定制所需的子模块，定制缓冲区的大小等。嵌入式数据库系统还应满足较好的可移植性，能够提供开放的接口和其它系统互操作。３．５．３运行环境和开发环境ＥＤＢ目前支持的平台是各种嵌入式Ｌｉｎｕｘ，具体产品包括各种高端的消费类电子设备，需要为ＥＤＢ搭建嵌入式开发交叉平台，这个平台需要的部件包括：主机（Ｈｏｓｔ）：它是开发人员的工作机，一般是桌面系统，分析、设计和文档撰写以及代码编写、大部分的调试工作等都在主机上完成ｎ７１。目前的主机是ＲｅｄＨａｔＬｉｎｕｘ７．３，目标机（Ｔａｒｇｅｔ）：它是ＥＤＢ实际运行的平台，该平台必须运行嵌入式Ｌｉｎｕｘ操作系统。当ＥＤＢ系统基本成型后就需要从主机下载到目标机进行进一步的调试，本系统的目标机是基于ＡＲＭ９平台的嵌入式Ｌｉｎｕｘ系统。１０第三章嵌入式数据库的分析与设计３．６详细设计嵌入式数据库设计流程如图３－４所示，主要包括ＳＱＬ解析、词法分析、语法分析、ＳＱＬＡＰＩ设计、事物的调度和执行策略、脱机移动事物、日志回滚和故障恢复几个方面。由于嵌入式数据库系统中的功能较多，中的重要功能设计和实现进行介绍。限于篇幅，仅对嵌入式数据库系统ＤＤＬ模式文件ＤＭＬ语法ＤＤＬ语法解析模块解析模块数据定义模块晶僻荔＿广Ｉ簇菇“。兰塑至竖堡苎ｌｌ；苗芝缓冲区内部数据结构图３—４ＥＤＢ的体系结构ＳＱＬＡＰＩ数据访问模块３．６．１ＳＯＬ解析ＳＱＬ语句中具有独立意义的单词，称之为单位体，有时也称为原予。词法分析的主要目的就是分隔单位体，并将这些单位体按照先后顺序插入单位体链表。每种单位体的规则和意义各不相同，比如单引号，在单引号内的其他符号都失效，而两个连续的单引号才表示一个单引号字符。从功能上分析，单位体可以分成７类：括号、子查询、数值运算、比较运算、逻辑运算、变量以及其他控制符号。若从可见性分析，单位体可以分成两类，即可见单位体和非可见单位体。非可见单位体主要是一些抽象的单位体，比如逻辑单位体。任意一条合法Ｗｈｅｒｅ子句，最后经过运算必须得到一个唯一的抽象的非可见单位体，即逻辑单位体ｎ８｜。若为１，记录符合要求，需要写入结果集：反之，则不符合要求，需要跳过。则表示当前解析ＳＱＬ语句总体目标是将ＳＱＬ语句转换成系统可以理解的格式，这就是语法分析的工作。这里所谓系统可以理解的格式，是指按照ＳＱＬ９２标准，判别该ＳＱＬ语句的类型（查询、删除、修改记录等），并根据不同的类型作不同的语法分析。比如查询语句，总体而言可以分成三个部分。ｓｅｌｅｃｔ与ｆｒｏｍ之间的部分主要描述结果集嵌入式数据库的设计与实现输出格式，而ｆｒｏｍ与ｗｈｅｒｅ（若无ｗｈｅｒｅ子句，则到ＳＱＬ语句结尾）之间的部分描述本ＳＱＬ语句所涉及的表，ｗｈｅｒｅ子句则是表示查询的条件。语法分析的任务之一就是将这三个部分分开并留给以后的系统使用，这也是语法分析的结果之一。在语法分析的过程中，系统需要检查当前ＳＱＬ语句的合法性，若不合法则报错退出，并给出出错信息。每当语法分析程序解析出一条语句时，就向语句执行列表中插入一个节点，这ＴＡＢＬＥ个节点的内容包括了该条语句的类型及相应的参数信息。如识别出是ＣＲＥＡＴ语句，就将插入节点的ｔｙｐｅ域设置为ＳＱＬ—ＣＲＥＡＴＥ—ＴＡＢＬＥ（为每一种语句都定义了一个标记以标识），并将ＣＲＥＡＴＴＡＢＬＥ的相关参数信息转换为相应的数据结构放入节点的ｓｔｍｔ域中。这样当整个脚本文件解析完毕后，所有的语句就会按顺序组成一个语句执行列表。执行时，遍历这个语句执行列表。通过判断每个节点的类型，就能知道所要执行的具体函数。如判断到该节点的ｔｙｐｅ为ＳＱＬ—ＣＲＥＡＴＥ～ＴＡＢＬＥ，相应的建表函数为ＥＤＢ＿Ｃｒｅａｔｅ（）。３．６．２语法解析语法解析是数据库实现要面对的重要问题，此数据库中采用的语法是ＳＱＬ语法，符合采用ＢＮＦ范式。显然，语法解析属于编译的范畴，虽然有关课程中已经详细介绍了词法分析和语法分析的理论，但是离开具体的实现还是有相当的距离，特别是对于ＳＱＬ这样复杂庞大的语法，为了构建完善且可靠的词法分析器和语法分析器有一定的难度和工作量。可喜的是，在Ｕｎｉｘ世界存在着相关的优秀工具，这些工具能够帮助我们实现一个专业的词法和语法分析器，这便是Ｆｌｅｘ和Ｙａｃｃ。有了这些自动工具，数据库开发者要做的主要工作便是为ＳＱＬ语法寻找合适的数据结构，以及为ｆｌｅｘ和ｙａｃｃ书写正确的脚本。一般的，树型的数据结构对于表示ＳＱＬ语法是合适的，当然考虑到每个语法的特点，我们可能需要为树做某种程度的变形，而不是标准的树结构。有了合适的数据结构，下一步的工作就是在ｆｌｅｘ和ｙａｃｃ的脚本中指示它们该如何一步一步的生成ＳＱＬ解析树。３．６．３存储管理嵌入式数据库的存储管理有两个方面，其一是外部存储管理，即如何组织数据文件、索引文件，二是内部存储管理。由于嵌入式系统内存资源的紧张，如何使用内存资源必然是嵌入式软件的热门话题和重要技术点。对于ＥＤＢ，内部存储管理涉及到两个关键问题。第一个问题是缓冲区管理，它也和外部存储管理密切相关。缓冲区机制是指为１２第三章嵌入式数据库的分析与设计减少Ｆｌａｓｈ或磁盘Ｉ／０在ＥＤＢ和二级存储器之间架设了一块内存空间，其职责是在查询处理过程中让数据存取模块得到所需的元组，数据存取模块通过某种访问方法从这些缓冲区读写元组，写入元组也是写到缓冲区上，而不需要直接访问Ｆｌａｓｈ文件或磁盘系统。这种机制可以大大减少对磁盘的访问，其原因是很多时候我们要访问的元组就己经在缓冲区上了。当ＥＤＢ初始化时，缓冲区数目将是一个可以设置的参数，不同的应用能够灵活的设置缓冲区的大小。我们为每个关系都设置一定大小的缓冲区（本数据库设为８Ｋ），由于页长度固定，这样此关系对应的缓冲区能够装入８个页。当需要访问不在缓冲区中的页时，需要将缓冲区中的某个页写回Ｆｌａｓｈ或磁盘，并调入待访问的页。这样，为尽量减少颠簸，本系统采用ＬＲＵ算法。第二个问题涉及到动态内存的申请和释放。本数据库是用Ｃ／Ｃ＋＋实现的，不可避免的牵涉到大量的ｍａｌｌｏｃ和ｆｒｅｅ操作，从系统堆中取得或还出内存。嵌入式系统中堆是一种需要特别慎重对待的重要系统资源。系统的ｍａｌｌｏｃ允许用户指定任意大小的区块，在系统堆频繁的分配和释放动态内存，特别是长度各异的内存，容易造成堆支离破碎，甚至可能使系统崩溃。系统堆越杂乱，区块大小越是参差不等，找出一个适当的空闲区块的时间更长，效率更低，所谓的通用性必然牺牲效率。另外，ＥＤＢ的动态内存占用需要处于可控制的范围。鉴于这些考虑，本数据库使用了动态内存管理办法取代了系统的ｍａｌｌｏｃ和ｆｒｅｅ，它就是所谓的预分配＋内存池技术。其主要思想如下：在ＥＤＢ初始化时，根据应用规模我们为ＥＤＢ预先分配一定数量的内存，以后ＥＤＢ所有的动态内存申请都只从这块内存中取得，这样做一个明显的好处是基本上不会干扰系统堆。这块内存除非ＥＤＢ系统退出，否则这块内存将一直为ＥＤＢ所占。然后，我们在这块内存上使用内存池技术，即将它分成若干个块（ｃｈｕｎｋ）‘每个块由一定数量的等长的内存片断（ｆｒａｇｍｅｎｔ）组成，比如某个块，它由２０个片断组成，每个片断都是８字节长，我们称该块为“８字节一块’’。通过分析ＥＤＢ内部各个动态数据结构的长度，以及数据库表的属性字段长度和元组长度等因素，我们将内存池分成如下２０种块：”８字节一块”，’’１６字节一块＂，”２４一字节块”，依８字节为步进（ｓｔｅｐ）一直到“１２８字节一块”，然后是“２５６字节一块”，”５１２字节一块”，＂１０２４字节一块”和“２０４８字节一块”。超过２０４８字节的片断在嵌入式数据库应用中很少出现，我们简单的将它交由系统堆处理。需要说明的是，这加块并不是静态的在系统初始时被划分死的，而是在需要它的时候才建立，有些情况下内存池中可能就只活跃着２种块，比如“８字节一块＂和“１６字节一块”。嵌入式数据库的设计与实现将块中的空闲片断由一个链表连接起来，并由一个指针指向表头，这个链表称为空闲表（ｆｒｅｅｌｉｓｔ）。一共需要２０个空闲表。值得注意的是，在实现中无须担心空闲表会消耗掉可观的内存，我们可以直接在空闲片断上建立这种链表。当然，我们需要存储这２０个空闲表的表头，空闲表带来的额外内存开销也仅限于此。图３—５给出了空闲表和块的示意图。图３—５空闲表和和空闲块不葸图图３－５中４号链表表头指向一个“６４字节一块＂，该块含有４个片断，某个片断中含有一个０指针表示链表的结束。当ＥＤＢ中的某个模块提出动态内存申请时，内存池将视其大小从特定块中取出一个合适的空闲片断交付给该模块，同时修改空闲链表的表头指针。“合适”尊循的原则是：如果申请的长度ｎ在１２８字节以下的，那么总是交付长度为Ｌ的空闲片断，Ｌ是８的整数倍值中大于ｎ的最小数；若申请的长度大于１２８且小于等于２５６，那么交付２５６字节的片断，大于２５６小于等于５１２则交付５１２字节的片断，更大长度的依此类推，直至２０４８字节。３．６．４ＳＱＬ预处理及简单优化通过上面的算法，可以得到计算机能够理解的单位体栈（也称为单位体链表、原子链表），这样就具备了执行该ＳＱＬ语句的必要条件。为了提高效率，需要对ＳＱＬ语句做部分预处理，将冗余信息去除掉。冗余的信息是指可以直接计算出结果的信息，比如无效括号、子查询、数值运算、比较运算、集合运算以及逻辑运算等等。具体为：（１）无效括号是指括号内只含有一个单位体：这样就可以把该单位体前后的左括号和右括号删除；（２）子查询必须要在扫描之前获得其结果，这样做的好处是避免在扫描每条记录时再去计算其结果，其优化结果为一个集合单位体；（３）数值运１４第三章嵌入式数据库的分析与设计算包括混合运算，若这些运算符前后不是变量，则可提前计算；比较运算主要包括＞、＜、＝、＞＝、＜＝、！＝，同样，若这些运算符前后不是变量的话，则可以立即计算其结果，并生成一个逻辑单位体，并代替原先单位体；今集合运算主要是指ＩＮ，ＡＮＹ，ＡＬＬ，ＮＯＴＩＮ，ＥＸＩＳＴＳ，ＮＯＴＥＸＩＳＴＳ运算，其后面一般是一个集合类型的单位体（子查询的（４）逻辑运算主要是结果就是一个集合单位体），计算结果也是一个逻辑单位体；ｎｏｔ，ａｎｄ，ｏｒ三种逻辑运算符，若其前后为逻辑单位体，则可立即合并。预处理后的单位体栈，只剩下与变量相关的单位体系列。这里的变量是指具体某个表的某个属性．预处理的算法是基于不断优化的思想，也就是说，设一个优化次数变量，每次循环开始时将优化次数Ｐ置０，以后每优化一次，该变量加１，到最后判断该变量是否为０，若为０，则说明已经没有可以再优化的单位体系列，也就是说达到了最优化，这时可以退出循环。之所以采用不断优化的算法，是因为在前一次优化的基础上，有时候还有可能进行二次优化ｎ９｜。单位体栈（或称原子链表、单位体链表）经过优化后，需要根据ＳＱＬ语句的类型送交不同的ＳＱＬ执行模块。由于ＥＤＢ系统相对来说是小型系统，数据库原理中的一些更高级的优化思想就没有在系统中过多考虑。３．６．５重要ＳＯＬ语句的设计前面已经提到，基本表是嵌入式数据库系统操作的核心，而基本表的创建和删除又是嵌入式数据库系统中最基本的操作之一，嵌入式数据库系统的其它操作都必须在创建成功的基本表基础上进行乜０｜。现对本系统使用的主要数据结构描述如下：ｓｔｒｕｃｔＤｂ｛、ｃｈａｒ木ｚＮａｍｅ；／木Ｎａｍｅｏｆｔｈｉｓｄａｔａｂａｓｅ木／Ｂｔｒｅｅ鲁ｐＢｔ；｜嶙ＴｈｅＢ★Ｔｒｅｅｓｔｒｕｃｔｕｒｅｆｏｒｔｈｉｓｄａｔａｂａｓｅｆｉｌｅ★｜ＨａｓｈｔｂｌＨａｓｈ；｜嘎Ａｌｌｔａｂｌｅｓｉｎｄｅｘｅｄｂｙｎａｍｅ★ｌＨａｓｈｉｄｘＨａｓｈ；｜’Ａｌｌ（ｎａｍｅｄ）ｉｎｄｉｃｅｓｉｎｄｅｘｅｄｂｙｎａｍｅ’｜ＨａｓｈｔｒｉｇＨａｓｈ；ｌ嚏Ａｌｌｔｒｉｇｇｅｒｓｉｎｄｅｘｅｄｂｙｎａｍｅ★｜ＨａｓｈａＦＫｅｙ；ｕ８ｉｎＴｒａｎｓ；ｕｌ６ｆｌａｇｓ；ｖｏｉｄ毒ｐＡｕｘ；卜Ｆｏｒｅｉｇｎｋｅｙｓｉｎｄｅｘｅｄｂｙｔｏ－ｔａｂｌｅ★｜／木０：ｎｏｔｗｒｉｔａｂｌｅ．１：Ｔｒａｎｓａｃｔｉｏｎ．２－Ｃｈｅｃｋｐｏｉｎｔ木／产Ｆｌａｇｓａｓｓｏｃｉａｔｅｄ、析ｔｈｔｈｉｓｄａｔａｂａｓｅ堆／｝肆Ａｕｘｉｌｉａｒｙｄａｔａ．ＵｓｕａｌｌｙＮＵＬＬ彝｝ｆｒｅｅｐＡｕｘ木／ｖｏｉｄ（木ｘＦｒｅｅＡｕｘ）（ｖｏｉｄ枣）；／幸Ｒｏｕｔｉｎｅｔｏ）；ｌ５嵌入式数据库的设计与实现ｓｔｒｕｃｔＴａｂｌｅ｛净Ｎａｍｅｏｆｔｈｅｔａｂｌｅ★｜ｃｈａｒ＊ｚＮａｍｅ；ｉｎｔｎＣｏｌ；｜’Ｎｕｍｂｅｒｏｆｃｏｌｕｍｎｓｉｎｔｈｉｓｔａｂｌｅ＾｜Ｃｏｌｕｍｎ＊ａＣｏｌ；ｉｎｔｉＰＫｅｙ；净Ｉｎｆｏｒｍａｔｉｏｎａｂｏｕｔｅａｃｈｃｏｌｍｎｎ＇｜严Ｉｆｎｏｔｌｅｓｓｔｈｅｎ０，ｕｓｅａＣｏｌ［ｉＰＫｅｙ】ａｓｔｈｅｐｒｉｍａｒ），ｋｅｙ宰／Ｉｎｄｅｘ卑ｐＩｎｄｅｘ；｜毒ＬｉｓｔｏｆＳＱＬｉｎｄｅｘｅｓｏｎｔｈｉｓｔａｂｌｅ．’｛ｈａｔｔｎｕｍ；严ＲｏｏｔＢＴｒｅｅｎｏｄｅｆｏｒｔｈｉｓｔａｂｌｅ（ｓｅｅｎｏｔｅａｂｏｖｅ）枣／Ｓｅｌｅｃｔ＊ｐＳｅｌｅｃｔ；降ＮＵＬＬｆｏｒｔａｂｌｅｓ．Ｐｏｉｎｔｓｔｏｄｅｆｍｉｆｉｏｎｉｆａｖｉｅｗ．★｜ｕ８ｈａｓＰｒｉｍＫｅｙ；ｌ’Ｔｒｅｅｉｆｔｈｅｒｅｅｘｉｓｔｓｕ８ａｐｒｉｍａｒｙｋｅｙ＾ＩｋｅｙＣｏｎｆ；｜★ＷｈａｔｔｏｄｏｉｎｃａｓｅｏｆｕｎｉｑｕｅｎｅｓｓｃｏｎｆｌｉｃｔｏｎｉＰＫｅｙ★｜ｏｎＴｒｉｇｇｅｒ★ｐＴｒｉｇｇｅｒ；｜是ＬｉｓｔｏｆＳＱＬｔｒｉｇｇｅｒｓｔｈｉｓｔａｂｌｅ＾｜ｔｈｉｓｔａｂｌｅ‘ｌＦＫｅｙ★ｐＦＫｅｙ；｜噜Ｌｉｎｋｅｄｌｉｓｔｏｆａｌｌｆｏｒｅｉｇｎｋｅｙｓｉｎ＞；ｓｔｒｕｃｔ・Ｉｎｄｅｘ｛ｃｈａｒ＊ｚＮａｍｅ；ｉｎｔ卜Ｎａｍｅｏｆｔｈｉｓｉｎｄｅｘ★｜ｔｈｅｔａｂｌｅｕｓｅｄｂｙｔｈｉｓｉｎｄｅｘ★｜ｎＣｏｌｕｍｎ；ｌ蠢ＮｕｍｂｅｒｏｆｃｏｌｕｍｎｓｉｎＳＱＬｔａｂｌｅｂｅｉｎｇｃｏｎｔａｉｎｉｎｇｉｎｔ＊ａｉＣｏｌｕｍｎ；｜肆ＷｈｉｃｈＴａｂｌｅ★ｐＴａｂｌｅ；｜嶙Ｔｈｅｈａｔｃｏｌｕｍｎｓａｒｅｕｓｅｄｂｙｔｈｉｓｉｎｄｅｘ．１ｓｔｉｓ０★｜ｉｎｄｅｘｅｄ＾｜ｍｕｍ；｜鼻Ｐａｇｅｒｏｏｔｏｆｔｈｉｓｉｎｄｅｘｉｎｄａｔａｂａｓｅｆｉｌｅ囊｜ｂｙｕ８ａｕｔｏＩｎｄｅｘ；严Ｔｒｕｅｉｆｉｓａｕｔｏｍａｔｉｃａｌｌｙｃｒｅａｔｅｄ（ｅｘ：ＵＮＩＱＵＥ）幸／Ｉｎｄｅｘ＊ｐＮｅｘｔ；“产Ｔｈｅｎｅｘｔｉｎｄｅｘａｓｓｏｃｉａｔｅｄｗｉｔｈｔｈｅｓａｍｅｔａｂｌｅ宰／。）；ｓｔｒｕｃｔ一Ｔｏｋｅｎ｛严Ｔｅｘｔｏｆｔｈｅｔｏｋｅｎ．ＮｏｔＮＵＬＬ－ｔｅｒｍｉｎａｔｅｄｔ宰／ｃｏｎｓｔｃｈａｒ木ｚ：）；（１）创建基本表创建基本表通过ＡＰＩ调用ｃｒｅａｔｅｔａｂｌｅ实现。由使用者输入基本表名和该基本表的属性列定义，在接口处理层将用户的输入转变为ＥＤＢ系统能识别和操作的创建表结构。当遇到ＣＲＥＡＴＥ，ＴＡＢＬＥ和表名以后，ＣｒｅａｔｅＴａｂｌｅ函数被调用。此函数首先用新建表的表名与字典记录表中的表名比较，如果新建表表名已经存在，则提示错误退１６第三章嵌入式数据库的分析与设计出，否则分配并初始化表结构，最后产生打开主表的操作码，具体操作如图３—６所不ｏ在事弗中捕八一条记录＇ｌｌ结束图３－６基本表创建流程图基本表创建源代码：ｓｔａｔｉｃｉｎｔＣｒｅａｔｅＴａｂｌｅ（Ｂｔｒｅｅ木ｐＢｔ，ｉｎｔ木ｐｉＴａｂｌｅ）｛ＭｅｍＰａｇｅ奉ｐＲｏｏｔ；ＰｇｎｏｐｇｎｏＲｏｏｔ；ｉｎｔｒｅ；ｒｃ＝ａｌｌｏｃａｔｅＰａｇｅ（ｐＢｔ，＆ｐＲｏｏｔ，＆ｐｇｎｏＲｏｏｔ，０）；ｉｆ（ｒｅ）ｒｅｔｕｒｎｒｃ；ｚｅｒｏＰａｇｅ（ｐＢｔ，ｐＲｏｏｔ）；ｐａｇｅｒｕｎｒｅｆ（ｐＲｏｏｔ）；木ｐｉＴａｂｌｅ＝（ｉｎｔ）ｐｇｎｏＲｏｏｔ；ｒｅｔｕｒｎ０Ｋ；）１７嵌入式数据厍的设计与买现（２）删除基本表调用ｄｅｌｅｔｅＴａｂｌｅ函数来删除基本表。基本操作过程是：首先从字典表中查找要删除的表名，若是表名不存在，则提示错误退出，否则清空表中的记录，然后删除表结构和与此表相关的索引结构，最后在字典表中删除包含此表名的记录以及与此表相关的索引名记录，具体流程如图３－７所示。Ｉ在事弗表审删除包耆此表信息记录ｊＲｌ索弓Ｉ记晕◆ｌ基本表删除源代码：ｖｏｉｄ纣柬｜图３－７基本表删除流程图ＤｅｌｅｔｅＴａｂｌｅ（ＤＢ木ｄｂ，Ｔａｂｌｅ宰ｐＴａｂｌｅ）｛ｈａｔｉ；Ｉｎｄｅｘ水ｐｌｎｄｅｘ．木ｐＮｅｘｔ；ＦＫｅｙ木ｐＦＫｅｙ，宰ｐＮｅｘｔＦＫｅｙ；ｉｆ（ｐＴａｂｌｅ一－－－０）ｒｅｔｕｒｎ；产Ｄｅｌｅｔｅａｌｌｉｎｄｉｃｅｓａｓｓｏｃｉａｔｅｄｗｉｔｈｔｈｉｓｔａｂｌｅ’ｌｆｏｒ（ｐＩｎｄｅｘ＝ｐＴａｂｌｅ－＞ｐｌｎｄｅｘ；ｐＩｎｄｅｘ；ｐＩｎｄｅｘ邓Ｎｅｘｔ）第三章嵌入式数据库的分析与设计｛ｐＮｅｘｔ＝ｐｌｎｄｅｘ－＞ｐＮｅｘｔ；ａｓｓｅｒｔ（ｐＩｎｄｅｘ－＞ｉＤｂ－－－－ｐＴａｂｌｅ一＞ｉＤｂｌｌ（ｐＴａｂｌｅ一＞ｉＤａ０＆＆ｐｌｎｄｅｘ一＞ｉＤｂ—１））；Ｄｅｌｅｔｅｌｎｄｅｘ（ｄｂ，ｐＩｎｄｅｘ）；）ｆｏｒ（ｐＦＫｅｙ＝ｐＴａｂｌｅ－＞ｐＦＫｅｙ；ｐＦＫｅｙ；ｐＦＫｅｙ＝ｐＮｅｘｔＦＫｅｙ）｛ｐＮｅｘｔＦＫｅｙ２ｐＦＫｅｙ－＞ｐＮｅｘｔＦｒｏｍ；ａｓｓｅｒｔ（ｐＴａｂｌｅ－＞ｉＤｂ＜ｄｂ－＞ｎＤｂ）；Ｆｒｅｅ（ｐＦＫｅｙ）；）｜粤ＤｅｌｅｔｅｔｈｅＴａｂｌｅｓｔｒｕｃｔｕｒｅＲｓｅｌｆ．・★｜ｆｏｒ（ｉ＝０；ｉ＜ｐＴａｂｌｅ－＞ｎＣｏｌ；ｉ＋＋）｛．ＥＤＢＦｒｅｅ（Ｉ：ＩＴａｂｌｅ－＞ａＣｏｌ［ｉ］．ｚＮａｍｅ）；ＥＤＢＦｒｅｅ（ｐＴａｂｌｅ一＞ａＣｏｌ［ｉ］．ｚＤｆｌｔ）；ＥＤＢＦｒｅｅ（ｐＴａｂｌｅ一＞ａＣｏｌ［ｉ］．ｚＴｙｐｅ）；＞ＥＤＢＦｒｅｅ（ｐＴａｂｌｅ－＞ｚＮａｍｅ）；ＥＤＢＦｒｅｅ（ｐＴａｂｌｅ－＞ａＣ０１）；ＥＤＢＳｅｌｅｃｔＤｅｌｅｔｅ（ｐＴａｂｌｅ－＞ｐＳｅｌｅｃｔ）；ＥＤＢＦｒｅｅ（ｐＴａｂｌｅ）；＞（３）插入记录插入记录的主要过程为：首先在字典表中查找要插入记录的表名，若不存在，则提示出错退出。然后比较列的列表参数，如果列名与表中的列名不符，则提示出错退出。如果表名和列名都正确，那么插入数据到表中。如果此表没有索引，那么插入操作完成。如果此表有索引，那么还要更新索引表，具体流程如图３－８所示。１９嵌入式数据库的设计与实现图３－８记录插入流程图记录插入源代码：ｖｏｉｄＤａｔａｌｎｓｅｒｔ（／幸Ｐａｒｓｅｒｃｏｎｔｅｘｔ枣／产Ｎａｍｅｏｆｔａｂｌｅｉｎｔｏｗｈｉｃｈｗｅａｒｅｉｎｓｅｒｔｉｎｇ枣／／木Ｌｉｓｔｏｆｖａｌｕｅｓｔｏｂｅｉｎｓｅｒｔｅｄ木／件ＡＳＥＬＥＣＴｓｍｔｅｍｅｍｔｏｕｓｅａｓＰａｒｓｅ宰ｐＰａｒｓｅ，ＳｒｃＬｉｓｔ宰ｐＴａｂＬｉｓｔ，ＥｘｐｒＬｉｓｔ木ｐＬｉｓｔ，Ｓｅｌｅｃｔ木ｐＳｅｌｅｃｔ，ｔｈｅｄａｔａｓｏｕｒｃｅ木／ＩｄＬｉｓｔ木ｐＣｏｌｕｍｎ，ｉｎｔｏｎＥｒｒｏｒｐＣｏｌｕｍｎｎａｍｅｓｃｏｒｒｅｓｐｏｎｄｉｎｇｔｏＩＤＬＩＳＴ．牛／严Ｈｏｗｔｏｈａｎｄｌｅｃｏｎｓｔｒａｉｎｔｅｒｒｏｒｓ・／）｛第三章嵌入式数据库的分析与设计ｄｂ＝ｐＰａｒｓｅ一＞ｄｂ；产定位需要插入数据的表宰／ｚＴａｂ＝ｐＴａｂＬｉｓｔ－＞ａ［Ｏ］．ｚＮａｍｅ；ｎＣｏｌｕｍｎ＝ｐＬｉｓｔ－＞ｎＥｘｐｒ；ｄｕｍｍｙ．ｎＳｒｃ＝０：ｆｏｒ（ｉ＝０；ｉ＜ｎＣｏｌｕｍｎ；ｉ＋＋１ｉｆ（ｐＣｏｌｕｍｎ）｛ｆｏｒ（ｉ＝０；ｉ＜ｐＣｏｌｕｍｎ一＞ｎｌｄ；ｉ＋＋）｛ｐＣｏｌｕｍｎ一＞ａ［ｉ］．ｉｄｘ‘２－１；）ｆｏｒ（ｉ＝０；ｉ＜ｐＣｏｌｕｍｎ－＞ｎＩｄ；ｉ＋＋）｛ｆｏｒ（ｊ＝０；ｊ＜ｐＴａｂ－＞ｎＣｏｌ；ｊ＋＋）｛ｉｆ（ＥＤＢＳｔｒｌＣｍｐ（ｐＣｏｌｕｍｎ一＞ａ【ｉ】．ｚＮａｍｅ，ｐＴａｂ・＞ａＣｏｌ［ｊ］．ｚＮａｍｅ）一０）｛ｐＣｏｌｕｎｍ一＞ａ［ｉ】．ｉｄｘ２ｊ；ｉｆ（ｊ一－－ｐＴａｂ－＞ｉＰＫｅｙ）｛ｋｅｙＣｏｌｕｍｎ＝ｉ：）ｂｒｅａｋ；）｝ｉｆ（ｊ＞＝ｐＴａｂ－＞ｎＣ０１）｛ｉｆ（ＥＤＢＩｓＲｏｗｉｄ（ｐＣｏｌｕｍｎ－＞ａ［ｉ】．ｚＮａｍｅ））｛ｋｅｙＣｏｌｕｍｎ＝ｉ；）ｅｌｓｅ｛ＥＤＢＥｒｒｏｒＭｓｇ（ｐＰａｒｓｅ．”ｔａｂｌｅ％ＳｈａｓｎＯｃｏｌｕｍｎｎａｍｅｄ％ｓ＂，ｐＴａｂＬｉｓｔ，０，ｐＣｏｌｕｍｎ－＞ａ［ｉ】．ｚＮａｍｅ）；ｐＰａｒｓｅ－＞ｎＥｒｒ＋＋；ｇｏｔｏｉｎｓｅｒｔ＿ｃｌｅａｎｕｐ；））｝２１）（４）更新记录更新函数的运行过程与删除函数相似，唯一的不同就是把删除记录改为更新记录，具体流程如３—９所示。图３－９更新记录流程图更新记录源代码：ｖｏｉｄＥＤＢＵｐｄａｔｅ（Ｐａｒｓｅ宰ｐＰａｒｓｅ，产１１１ｅｐａｒｓｅｒｃｏｎｔｅｘｔ・／ＳｒｃＬｉｓｔ＊ｐＴａｂＬｉｓｔ，产Ｔｈｅｔａｂｌｅｉｎｗｈｉｃｈｗｅｓｈｏｕｌｄｃｈａｎｇｅｔｈｉｎｇｓ幸／２２第三章嵌入式数据库的分析与设计ＥｘｐｒＬｉｓｔ・ｐＣｈａｎｇｅｓ．／宰Ｔｈｉｎｇｓｔｏｂｅｃｈａｎｇｅｄ宰／Ｅｘｐｒ木ｐＷｈｅｒｅ．／奉ＴｈｅＷＨＥＲＥｃｌａｕｓｅ．Ｍａｙｂｅｎｕｌｌ木／ｉｎｔｏｎＥｒｒｏｒ严Ｈｏｗｔｏｈａｎｄｌｅｃｏｎｓｔｒａｉｎｔｅｒｒｏｒｓ掌／）｛／／定位所需更新的表ａＸＲｅｆ＝ＥＤＢＭａｌｌｏｃ（ｓｉｚｅｏｆ（ｉｎｔ）＋ｐＴａｂ一＞ｎＣ０１）；ｉｆ（ａ№ｆ釜Ｏ１ｇｏｔｏｕｐｄａｔｅ＿ｃｌｅａｎｕｐ；ｆｏｒ（ｉ＝０；ｉ＜ｐＴａｂ－＞ｎＣｏｌ；ｉ＋＋）ａＸＲｅｆ［ｉ】２－１；ｉｆ（ｒｏｗ＿ｔｒｉｇｇｅｒｓｅｘｉｓｔ）｛ｎｅｗｌｄｘ＝ｐＰａｒｓｅ－＞ｎＴａｂ＋＋；’ｏｌｄｌｄｘ＝ｐＰａｒｓｅ一＞ｎＴａｂ＋＋；）ｐＴａｂＬｉｓｔ一＞ａ【Ｏ］．ｉＣｕｒｓｏｒ＝ｉＣｕｒ＝ｐＰａｒｓｅ・＞ｎＴａｂ＋＋；ｆｏｒ（ｐｌｄｘ＝ｐＴａｂ一＞ｐｌｎｄｅｘ；ｐＩｄｘ；ｐｌｄｘ＝ｐｌｄｘ－＞ｐＮｅｘｔ）｛ｐＰａｒｓｅ－＞ｎＴａｂ＋＋；）ｃｈｎｇＲｅｃｎｏ２０：ｆｏｒ（ｉ＝０；ｉ＜ｐＣｈａｎｇｅｓ・＞ｎＥｘｐｒ；ｉ＋＋）｛ｉｆ（ＥｘｐｒＲｅｓｏｌｖｅｌｄｓ（ｐＰａｒｓｅ，ｐＴａｂＬｉｓｔ，０，ｐＣｈａｎｇｅｓ－＞ａ［ｉ］．ｐＥｘｐｒ））｛ｇｏｔｏｕｐｄａｔｅ＿ｃｌｅａｎｕｐ；）ｉｆ（ＥｘｐｒＣｈｅｃｋ（ｐＰａｒｓｅ，ｐＣｈａｎｇｅｓ－＞ａ［ｉ】．ｐＥｘｐｒ，０，０））｛ｇｏｔｏｕｐｄａｔｅ＿ｃｌｅａｎｕｐ；）ｆｏｒ（ｊ＝Ｏ；ｊ＜ｐＴａｂ－＞ｎＣｏｌ；ｊ＋＋）｛ｉｆ（ＳｔｒｌＣｍｐ（ｐＴａｂ一＞ａＣｏｌ［ｊ］．ｚＮａｍｅ，ｐＣｈａｎｇｅｓ一＞ａ［ｉ】．ｚＮａｍｅ）一０）｛ｉｆ（ｊ一－－ｐＴａｂ一＞ｉＰＫｅｙ）｛ｃｈｎｇＲｅｃｎｏ＝１；ｐＲｅｃｎｏＥｘｐｒ＝ｐＣｈａｎｇｅｓ・＞ａ［ｉ］．ｐＥｘｐｒ；）ａＸＲｅｆ［ｊ］＝ｉ；．２３嵌入式数据库的设计与实现ｉｆ（ｊ＞＝ｐＴａｂ－＞ｎＣ０１）｛ｉｆ（ＩｓＲｏｗｉｄ（ｐＣｈａｎｇｅｓ－＞ａ［ｉ】．ｚＮａｍｅ））｛ｃｈｎｇＲｅｃｎｏ＝１；ｐＲｅｃｎｏＥｘｐｒ＝ｐＣｈａｎｇｅｓ－＞ａ［ｉ］．ｐＥｘｐｒ；｝ｅｌｓｅ｛ＥｒｒｏｒＭｓｇ（ｐＰａｒｓｅ，”ｎｏｇｏｔｏｕｐｄａｔｅ＿ｃｌｅａｎｕｐ；ｓｕｃｈｃｏｌｕｍｎ．％ｓ”，ｐＣｈａｎｇｅｓ一＞ａ【ｉ】．ｚＮａｍｅ）；＞ｆｏｒ（ｎｌｄｘ＝ｎｌｄｘＴｏｔａｌ＝０，ｐｌｄｘ＝ｐＴａｂ一＞ｐｌｎｄｅｘ；ｐｌｄｘ；ｐｌｄｘ＝ｐｌｄｘ－＞ｐＮｅｘｔ，ｎＩｄｘＴｏｔａｌ＋＋）｛ｉｆ（ｃｈｎｇＲｅｃｎｏ）｛ｉ＝Ｏ；｝ｅｌｓｅ｛ｆｏｒ（ｉ＝０；ｉ＜ｐｌｄｘ－＞ｎＣｏｌｕｍｎ；ｉ＋＋）｛ｉｆ（ａＸＲｅｆ［ｐＩｄｘ・＞ａｉＣｏｌｕｍｎ［ｉ］］＞＝０＞）ｉｆ（ｉ＜ｐＩｄＸ一＞ｎＣｏｌｕｍｎ）ｍｄ刈斗；１ｂｒｅａｋ；＞（５）查找记录ＥＤＢＳｅｌｅｃｔＮｅｗ函数实现记录的查询操作。查询分为３种情况。第一种就是没有ｗｈｅｒｅ条件，该查询为按记录号查询，实现的是所有记录从头到尾的查询，这种情况下Ｓｅｌｅｃｔ，结构体中的指针为空：第二种是按属性列（不是索弓ＩＹＵ）查询，这种情况与２４第三章嵌入式数据库的分析．ｏｊ设计第一种类似，只是从头到尾都根据ｗｈｅｒｅ条件中的列表达式比较，符合则放入到栈中；第三种是索引查询，此种方式在数据量大的时候实现了快速查询，也是本文要重点讲述的查询方式，具体流程如图３－１０所示。“图３—１０查找记录流程图查找记录源代码：Ｓｅｌｅｃｔ幸ＥＤＢＳｅｌｅｃｔＮｅｗ（ＥｘｐｒＬｉｓｔ＾ｐＥＬｉｓｔ．｜嚏ｗｈｉｃｈｃｏｌｕｍｎｓｔｏｉｎｃｌｕｄｅｉｎｔｈｅｒｅｓｕｌｔ★｜ＳｒｃＬｉｓｔ鼻ｐＳｒｃ，ｊ｜嘎ｔｈｅＦＲＯＭｃｌａｕｓｅ一一ｗｈｉｃｈｔａｂｌｅｓｔｏｓｃａｎ｜ｌ。Ｅｘｐｒ丧ｐＷｈｅｒｅ、｜愧ｔｈｅＷＨＥＲＥｃｌａｕｓｅ＾ｌＥｘｐｒＬｉｓｔ鼻ｐＧｒｏｕｐＢｙ，｜嚏ｔｈｅＧＲＯＵＰＢＹｃｌａｕｓｅ＾｜Ｅｘｐｒ木ｐＨａｖｉｎｇ．／宰ｔｈｅＨＡＶＩＮＧｃｌａｕｓｅ宰／ＥｘｐｒＬｉｓｔ木ｐＯｒｄｅｒＢｙ，／枣ｔｈｅＯＩ己ＤＥＲＢＹｃｌａｕｓｅ木／ｉｎｔｉｓＤｉｓｔｉｎｃｔ，≯ｔｒｕｅｉｆｔｈｅＤＩＳＴＩＮＣＴｋｅｙｗｏｒｄｉｓｐｒｅｓｅｎｔ鼻｜２５嵌入式数据库的设计与实现ｉｎｔｎＬｉｍｉｔ，ｉｍｎＯｆ．ｆｓｅｔ产ＬＩＭＩＴｖａｌＬｉｅ．．１ｍｅａｎｓｎｏｔｕｓｅｄ，Ｉ‘／／枣ＯＦＦＳＥＴｖａｌｕｅ．０ｍｅａｎｓｎｏｏｆｆｓｅｔ堆／）｛Ｓｅｌｅｃｔ事ｐＮｅｗ；ｐＴａｂ・＞ｚＮａｍｅ２ｚＴａｂＮａｍｅ？ＳｔｒＤｕｐ（ｚＴａｂＮａｍｅ）：Ｏ；ｐＥＬｉｓｔ＝ｐＳｅｌｅｃｔ－＞ｐＥＬｉｓｔ；ｐＴａｂ－＞ｎＣｏｌ＝ｐＥＬｉｓｔ一＞ｎＥｘｐｒ；ａｓｓｅｒｔ（ｐＴａｂ－＞ｎＣｏｌ＞０）；ｐＴａｂ一＞ａＣｏｌ＝ａＣｏｌ＝ＥＤＢＭａＵｏｃ（ｓｉｚｅｏｆ（ｐＴａｂ一＞ａＣｏｌ［０］）宰ｐＴａｂ－＞ｎＣ０１）；ｆｏｒ（ｉ＝Ｏ；ｉ＜ｐＴａｂ・＞ｎＣｏｌ；ｉ州｛Ｅｘｐｒ牛Ｐ．宰ｐＲ；ｉｆ（ｐＥＬｉｓｔ－＞ａ［ｉ】．ｚＮａｍｅ）｛ａＣｏｌ［ｉ］．ｚＮａｍｅ＝ＥＤＢＳｔｒＤｕｐ（ｐＥＬｉｓｔ－＞ａ［ｉ】．ｚＮａｍｅ）；｝ｅｌｓｅｉｆ（①＝ｐＥＬｉｓｔ－＞ａ［ｉ］．ｐＥｘｐｒ）－＞ｏｐ一－－－ＴＫ＿ＤＯＴ＆＆（ｐＲ＿叩－＞ｐＲｉｇｈｔ）！＝０＆＆ｐＲ－＞ｔｏｋｅｎ．Ｚ＆＆ｐＲ一＞ｔｏｋｅｎ．ｚ［Ｏ】）｛ｉｎｔｃｎｔ；ＳｅｔＮＳｔｒｉｎｇ（＆ａＣｏｌ［ｉ］．ｚＮａｍｅ，ｐＲ－＞ｔｏｋｅｎ．ｚ，ｐＲ－＞ｔｏｋｅｎ．ｎ，０）；ｆｏｒ（ｊ＝ｃｎｔ＝０；ｊ《；ｊ什）＜ｉｆ（ＥＤＢＳｔｒｌＣｍｐ（ａＣｏｌ［ｊ］．ｚＮａｍｅ，ａＣｏｌ［ｉ］．ｚＮａｍｅ）－一－－Ｏ）｛ｉｎｔｎ：ｃｈａｒｚＢｕｆ［３０］；ｓｐｒｉｎｔｆ（ｚＢｕｆ，”—％ｄｆＩ，＋＋ｃｎｔ）；ｎ＝ｓｔｒｌｅｎ（ｚＢｕｆ）；ＳｅｔＮＳｔｒｉｎｇ（＆ａＣｏｌ［ｉ］．ｚＮａｍｅ，ｐＲ－＞ｔｏｋｅｎ．ｚ，ｐＲ一＞ｔｏｋｅｎ．ｎ，ｚＢｕｆ，ｎ，０）；Ｊ＝－ｌ；｝｝｝ｅｌｓｅｉｆ（ｐ－＞ｓｐａｎ．ｚ＆＆Ｐ一＞ｓｐａｎ．ｚ［Ｏ］）｛ＥＤＢＳｅｔＮＳｔｒｉｎｇ（＆ｐＴａｂ一＞ａＣｏｌ［ｉ］．ｚＮａｍｅ，ｐ－＞ｓｐａｎ．ｚ，ｐ－＞ｓｐａｎ．ｎ，０）；）ｅｌｓｅ｛ｃｈａｒｚＢｕｆ［３０］；２６第三章嵌入式数据库的分析与设计ｓｐｒｉｎｔｆ（ｚＢｕｆ，”ｃｏｌｕｎｍ％ｄ”，ｉ＋１）；ａＣｏｌ［ｉ］．ｚＮａｍｅ＞Ｄｅｑｕｏｔｅ（ａＣｏｌ［ｉ］．ｚＮａｍｅ）；｝ｐＴａｂ一＞ｉＰＫｅｙ＝－１；ｒｅｔｕｒｎｐＴａｂ；２ＳｔｒＤｕｐ（ｚＢｕｆ）；（６）删除记录此函数的输入是要删除的表名，ｗｈｅｒｅ条件可以没有，此时指删除表中的所有记录。此函数的的删除过程为：首先在字典表中检查要删除的表名，如果不存在，则提示错误退出，然后检查ｗｈｅｒｅ条件参数，若为空，则直接清空表中的数据，若有ｗｈｅｒｅ条件从句，则先比较条件中的列名是否在表的列中出现，若列名不存在，则提示错误退出，否则进行记录的删除工作，此删除过程分为两步，第一步是从头到尾扫描表，若记录满足ｗｈｅｒｅ条件，则把满足条件的记录的记录号放入到一个整数队列中。第二步是按队列中的记录号删除表中的记录。若此表还有索引，则还要更新索引记录，删除记录流程如图３－１ｌ所示。２７嵌入式数据库的设计与实现图３—１１删除记录流程图３．６．６索引设计本数据库采用Ｂ＃树索引结构，Ｂ＃树能适应随机查找和顺序查找，并且能在很大程度提高数据库的空间利用率。索引结点结构主要包括５个部分，ＦｉｌｅＨｅａｄｅｒ（数据库文件头页，它只存在于每一个数据库文件的第一页，其它的中间页或是叶子页都没有这一项），ＰａｇｅＨｅａｄｅｒ（结点头部），ＣｅｌｌＵｎｌｏｃａｔｅｄＰｉｏｎｔｅｒａｒｒａｙ（索引项指针数组，指向ｃｅｌｌｃｏｎｔｅｎｔａｒｅａ），ｓｐａｃｅ（指暂时还没分配去的，或是己被系统回收的空间），ｃｅｌｌｃｏｎｔｅｎｔａｒｅａ（指每个ｃｅｌｌ的数据集合），如图３－１２所示：第三章嵌入式数据库的分析１ｊ设计图３－１２索引节点结构示意图１．索引查找算法设计在Ｂ＃树中，继承了Ｂ＋树的优点，区别在于Ｂ＃树中可能有溢出页，也就是在查找关键字时，如果在叶子结点中如要没有发现要查找的关键字时，还需要检查溢出页，如果溢出页存在，继续在它的溢出页顺序查找，如果查找成功，则查找结束。在Ｂ＃树中，如果关键字在叶子结点中，则跟Ｂ＋树查找方法一样，这里不需要多说，如果关键字出现在溢出页中，专为查找Ｂ＃树的溢出页中关键字设计了函数ｆｉｎｄｏｖｅｒｆｌｏｗＣｅｌｌ（），用它来查找Ｂ＃树的溢出页中的关键字。ｓｔａｔｉｃｕ８木ｆｉｎｄＯｖｅｒＣｅｌｌ（ＭｅｍＰａｇｅ木ｐＰａｇｅ，ｉｎｔｉＣｅｌｌ）｛ｉｎｔｉ；ｆｏｒ（ｉ＝ｐＰａｇｅ－＞ｎＯｖｅｒｆｌｏｗ－１；ｉ＞＝Ｏ；ｉ一、｛ｉｎｔｋ：ｓｔｒｕｃｔ—ＯｖｆｌＣｅｌｌ宰ｐＯｖｆｌ；ｐＯｖｆｌ＝＆ｐＰａｇｅ－＞ａＯｖｆｌ［ｉ］；’ｋ＝ｐＯｖｆｌ；ｉｆ（ｋ＜＝ｉＣｅｌｌ）｛ｉｆ（ｋ—ｉＣｅｌｌ）｛ｒｅｔｕｒｎｐＯｖｆｌ一＞ｐＣｅｌｌ；２９嵌入式数据库的设计与实现＿｝ｉＣｅＵ－－；））＞２．索引插入算法设计在Ｂ＋树索引机制中，如果发现叶子结点已满，待插入的关键字一插入，就会引起结点的分裂。叶子结点一分为二，把关键字平均分配到两个结点，中间关键字提升，更新父结点中的关键字，完成了一次结点分裂的操作。在Ｂ＃树索引机制，当发现叶子结点己满，会先查找它的左右２Ｎ个兄弟个是否有未分配的空间，如果没有，再查找它的溢出页中是否已满，如果未满，则直插入到溢出页，否则，进行结点分裂。在Ｂ＃中，如果要插入一个关键字，首先调用函数查找树中是否存在关键字，如果关键字存在，直接返回。当关键字不存在于Ｂ＃树中，假如叶子结点空间己满，则检查它的左右２Ｎ个兄弟结点是否存在未分配的空间，如果是，则通过Ｂａｌａｎｃｅｓｏｒｔ函数来腾出空间，再把关键字插入到合适的空间中，并保持叶子结点间关键字有序。如果左右兄弟的结点都己满，则检查它溢出页是否存在未使用空间，如果存在，则插入溢出页，否则调用函数ｄｅｆｒａｇｍｅｎｔＰａｇｅ来分裂结点，把关键字插入分裂后的空间，并调用函数Ｂａｌａｎｃｅ保持叶子结点关键字的有序。３．索引删除算法设计在Ｂ＃树中，如果结点发生关键字删除操作，如果该关键字在叶子结点中，删除后，判断它的溢出页是否存在，如果存在，则将溢出中的关键字移到叶子结点中，并保持叶子结点中关键字原有顺序，如果不存在，则检查其同父结点的２Ｎ个左右兄弟是否存在溢出页，如果是，则通过“动态平衡”，腾出空位，把溢出页中关键字移到叶子结点中，并保持叶子结点关键字原有顺序，如果否，则检查该结点和它的同父结点的２Ｎ个兄弟结点，能否同时容纳于２Ｎ个结点中，如果能，则进行合并，删除一个结点，进行“动态平衡＂，保持２Ｎ个结点中关键字原有顺序，如果不能，用动态平衡算法把关键字平均分配到２Ｎ＋１个结点中，并保持原有顺序。如果删除的关键字在溢出页中，则删除过后，判断溢出页是否为空，如果是，则由于系统回收该溢出页，否则保持溢出页中关键字有序。３０第四章基于ＡＲＭ的嵌入式数据库的实现第四章基于ＡＲＭ的嵌入式数据库的实现４．１硬件平台的搭建４．１．１ＡＲＭ开发平台介绍ＡＲＭ微处理器是一种高性能、低功耗的３２位微处器，它被广泛应用于嵌入式系统中，ＡＲＭ是一家英国公司，它的文字含义是ＡｄｖａｎｃｅｄＲＩＳＣＭｉｃｒｏｐｒｏｃｅｓｓｏｒ（高级ＲＩＳＣ微处理器）。ＡＲＭ为客户提供１６／３２位嵌入式ＲＩＳＣ微控制器方案，将其ＲＩＳＣ处理器授权给电子公司使用，在便携式通讯，手持计算设备，消费类和数字化多媒体方案中，ＡＲＭ正有一种成为标准的趋势ｎ９１。４．１．２Ｓ３０２４１０开发板介绍三星（Ｓａｍｓｕｎｇ）￥３Ｃ２４１０是一款著名的移动设备处理器产品，最著名的应用是在惠普的ｉＰＡＱ系列ＰＤＡ上，￥３Ｃ２４１０有两个型号：￥３Ｃ２４１０Ｘ和￥３Ｃ２４１０Ａ，Ａ型是Ｘ型的改进型，相对来说具有更好的性能和更低的功耗，￥３Ｃ２４１０主要面向手持式设备以及高性价比、低功耗的应用，现在市面上许多高性能的ＰＤＡ、手机、数码相机、机顶盒等均采用￥３Ｃ２４１０为处理器。４．２嵌入式Ｌｉｎｕｘ开发环境的建立４．２．１嵌入式Ｌｉｎｕｘ开发环境的基本结构由于嵌入式设备没有足够的内存以及存储资源来完成其编译过程，所以就在主机上完成针对目标的代码编译生成，这个过程称为交叉编译。这也是目前大多数嵌入式设备开发所使用的编译方式。为了提高嵌入式Ｌｉｎｕｘ的开放效率，一个完善的嵌入式Ｌｉｎｕｘ开发环境是必不可少的。嵌入式Ｌｉｎｕｘ开发环境一般由如下几部分构成：Ｌｉｎｕｘ服务器（宿主机）、工作站、嵌入式目标系统和将它们连接在一起的网络环境，其具体结构如图图４－１嵌入式开发环境基本结构图中所示的嵌入式Ｌｉｎｕｘ开发环境中，Ｌｉｎｕｘ服务器作为嵌入式Ｌｉｎｕｘ内核编译、应用程序编译的公共平台，由单独的一台ＰＣ机充当，安装常用的桌面标准Ｌｉｎｕｘ操３ｌ嵌入式数据库的设计与实现作系统，如ＲｅｄｈａｔＬｉｎｕｘ等。工作站即为普通的局域网计算机，可以是一台或多台，以支持小组项目开发。工作站一般安装常用的ｗｉｎｄｏｗｓ操作系统，仍然可以完成各种日常工作。当需要使用Ｌｉｎｕｘ服务器资源时，就从工作站远程登录到Ｌｉｎｕｘ服务器，以完成各项需要的操作。工作站作为开发人员的操作终端，可能需要经常登录Ｌｉｎｕｘ服务器和工作站之间进行文件的传输，因此，一般需要在工作站上安装ＦＴ，客户端程序（如Ｃｕｔｅｆｔｐ等）和Ｔｅｌｎｅｔ客户端程序（如ＳｅｃｕｒｅＣＲＴ等）。当Ｌｉｎｕｘ服务器的ＦＴＰ服务和Ｔｅｌｎｅｔ服务运行时，开发人员就可以方便地在工作站和Ｌｉｎｕｘ服务器之间进行文件传输，并可以通过Ｔｅｌｎｅｔ方式登录到Ｌｉｎｕｘ服务器，并对其进行相关操作。４．２．２在Ｌｉｎｕｘ服务器上安装交叉编译工具１．获取交叉编译工具・开发基于Ｌｉｎｕｘ的应用程序，一般的步骤是先编写程序源代码，然后编译调试，最终生成可执行程序。交叉编译工具一般由专门的机构负责维护，可以从他们的网站上免费取得㈨。２．安装交叉编译工具下载的交叉编译工具以压缩的方式存在，需要将其安装到Ｌｉｎｕｘ服务器上。这里把交叉编译工具安装在Ｌｉｎｕｘ服务器的／ｕｓｒ／ｌｏｃａｌ／目录下，执行如下操作，建立／ｕｓｒ／ｌｏｃａｌ／ａｒｍ目录，并将下载的交叉编译工具复制到该目录下乜引：＃ｃｄ／ｕｓｒ／ｌｏｃａｌ＃ｍｋｄｉｒａｒｍ（进入目录／ｕｓｒ／ｌｏｃａｌ）（建立子文件夹）（拷贝文件）＃ｃｐ／ｈｏｍｅ／ｗｏｒｋ／ｃｒｏｓｓ一２．９５３．ｔａｒ．ｂｚ２输入如下命令解压安装编译工具：＃ｔａｒｚｘｖｆｃｒｏｓｓ一２．９５．３．ｔａｒ．ｂｚ２（解压缩文件）当以上命令执行完毕以后，会生成／ｕｓｒ／１０ｃａｌ／ａｒｍ／２．９５．３子目录，表明交叉编译器已经成功安装到了／ｕｓｒ／ｌｏｃａｌ／ａ瑚下。安装后会在该目录下生成如下的文件和目录：ａｒｍ－Ｌｉｎｕｘｂｉｎｉｎｃｌｕｄｅｉｎｆｏｌｉｂｍａｎｓｈａｒｅｔｅｓｔ—ｉｆ—ｗｒｉｔｅ其中，ｂｉｎ目录下是交叉编译器和一些工具，如编译器ａｍｔ—Ｌｉｎｕｘ—ｇｃｃ是Ｃ交叉编译器，ａｒｍ－Ｌｉｎｕｘ—ｇ＋＋是Ｃ＋＋编译器，ａｒｍ－Ｌｉｎｕｘ—ａｓ是汇编器，ａｒｍ—Ｌｉｎｕｘ—Ｉｄ是链接器。Ｌｉｂ目录下存放的是库文件，包括ｇｃｃ库、１ｉｂ－ｇｃｃ库、ｌｉｂ—ｇ＋＋库等。／ｉｎｃｌｕｄｅ目录存放编译器的头文件，包含了标准Ｃ的头文件、Ｌｉｎｕｘ的头文件、３２第四章基于ＡＲＭ的嵌入式数据库的实现特定处理器相关的Ｌｉｎｕｘ头文件等。在以上工具中，ａｒｍ－Ｌｉｎｕｘ－ｇｃｃ作为基于ＡＲＭ架构的Ｃ编译器，在系统开发过程中是最为常用的㈨。４．２．３嵌入式ＬＩｎｕｘ内核的配置与编译Ｌｉｎｕｘ最大的特点是内核具有非常良好的结构，可由用户根据特定的系统需求，对内核进行配置或裁剪，而这一特点恰恰满足了嵌入式应用的差异性需求心利。１．获取Ｌｉｎｕｘ内核源代码Ｌｉｎｕｘ内核由专门的机构维护，可以从Ｌｉｎｕｘ内核的官方发布网站：：ｈｔｔｐ：／／嗣ｗｋｅｍｅｌ．ｏｒｇ上获取功能完善的最新内核。２．Ｌｉｎｕｘ内核配与编译本系统的Ｌｉｎｕｘ内核编译步骤如下：１）整理出系统需要支持的硬件、文件系统类型以及网络协议等内容，以便配置内核时选择所需的软件支持。２）下载并解压Ｌｉｎｕｘ内核，因为安装系统时所安装的源代码默认情况下支持很多设备，这样给内核裁减降低了难度。一般都将Ｌｉｎｕｘ内核源代码放在／ｕｓｒ／ｓｒｃ下。３）清除从前编译内核时残留的文件和不必要的关联：ｃｄ／ｕｓｒ／ｓｒｃ几ｉｎｕｘ（进入文件夹）ｍａｋｅｍｒｐｒｏｐｅｒ（清除不必要的关联）确保源代码目录下没有不正确的文件和文件依赖关系，执行该命令后，内核选项会回到默认的状态下。本系统是下载的内核源码，而且是第一次编译，所以就不必执行这一步操作。４）配置内核，修改相关参数一＋。’本系统需要选择的模块有：Ｓｕｐｐｏｒｔｆｏｒｐａｇｉｎｇｏｆａｎｏｎｙｍｏｕｓｍｅｍｏｒｙ（ｓｗａｐ）／／支持虚拟内存Ｅｎａｂｌｅｌｏａｄａｂｌｅｍｏｄｕｌｅｓｕｐｐｏｒｔ（ＣＯＮＦＩＧＭＯＤＵＬＥＳ）／／动态装载模块功能Ｎｅｔｗｏｒｋｉｎｇｓｕｐｐｏｒｔ（ＣＯＮＦＩＧＮＥＴ）／／网络支持ＴＣＰ／ＩＰｎｅｔｗｏｒｋｉｎｇ／／ＴＣＰ／ＩＰ协议等系统必须的功能模块。５）运行ｍａｋｅｃｌｅａｎ，清理一些不必要的文件，如果在上次编译的基础上，删去了一些选项就必须执行这一步操作。６）编译内核３３嵌入式数据库的设计与实现编译内核的命令是：ｍａｋｅ４．２．４根文件系统的制作ｚＩｍａｇｅ对于嵌入式Ｌｉｎｕｘ来说，最简单、最常用的根文件系统是ＲＡＭＤＩＳＫ。ＲＡＭＤＩＳＫ就是指使用系统的一部分内存空间来模拟一个用户熟悉的磁盘分区，用户在ＲＡＭＤＩＳＫ上进行的所有操作都与传统的磁盘文件操作一样。因此，对于无盘系统或嵌入式系统，选择ＲＡＭＤＩＳＫ作为根文件系统是很适合的。在实际的应用过程中，通常采用的方式是从开发系统提供商获得一个已经做好的ＲＡＭＤＩＳＫ然后由用户根据自身系统的实际需求，对己有的ＲＡＭＤＩＳＫ进行增减，最终形成一个适合自身应用的ＲＡＭＤＩＳＫ。１．ＲＡＭＤＩＫ的制作１）首先为根文件系统创建空的文件镜像：ｍｋｄｉｒ／ｒａｎｔｉｎｉｔｒｄｄｄ／／创建目录・－ｉｆ＝／ｄｅｖ／ｚｅｒｏｏｆ＝ｉｎｉｔｒｄ．ｉｍｇｂｓ＝ｌｋｃｏｕｎｔ＝８１９２／／确定文件系统大小ｍｋｆｓ．ｅｘｔ２一Ｆｍｏｕｎｉｎｉｔｒｄ．ｉｍｇ／／￥Ｕ作文件系统ｉｔｒｄ．ｉｍｇ／ｍｎｔ／ｉｎｉｔｒｄ／／挂载ｔ一０ｌｏｏｐｉｎ上面命令创建了一个８１９２ＫＢ的文件系统镜像，并通过ｄｅｖ／ｚｅｒｏ进行初始化。２）创建目录，上面的命令创建了一个ＲＡＭＤＩＳＫ，要用必要的文件填充它：ｍｋｄｉｒｄｅｖｐｒｏｃｅｔｃｓｂｉｎｂｉｎｌｉｂｍｎｔｕｓｒ。２．利用已有的ＲＡＭＤＩＳＫ本系统的ＲＡＭＤＩＳＫ是这样实现：解压系统提供商的ＲＡＭＤＩＳＫ：ｇｚｉｐ—ｄｒａｍｄｉｓｋ．ｇｚ，将文件挂载到一个临时目录：＃ｍｋｄｉｒｒａｍ—ｄｉｓｋｒａｍ＿ｄｉｓｋ＃ｍｏｕｎｔ‘。０ｌｏｏｐｒａｍｄｉｓｋ＃１Ｓ根据本系统的需求，对相关文件进行增减操作，即可以往目录复制或删除一些文件。操作好后对新的ＲＡＭＤＩＳＫ文件进行压缩：＃ｕｍｏｕｎｔ／ｒａｍｄｉ＃ｇｚｉｐｒａｍｄｉｓｋｓｋ／／卸载／／压缩文件系统这样生成一个新的ＲＡＭＤＩＳＫ。有了嵌入式Ｌｉｎｕｘ和根文件系统，一个完整的嵌入式Ｌｉｎｕｘ系统就编译完成了。３４第四章基于删的嵌入式数据库的实现４．２．５网络文件系统（ＮＦＳ）及配置首先在Ｌｉｎｕｘ服务器上设置：以Ｒｏｏｔ身份登录Ｌｉｎｕｘ服务器，编辑共享目录配置文件ｅｘｐｏｒｔ，指定共享目录及权限等。执行如下的命令编辑文件：ｅｔｃ／ｅｘｐｏｒｔｓ＃ｖｉ／ｅｔｃ／ｅｘｐｏｒｔｓ（编辑ｅｘｐｏｒｔｓ的内容）在该文件中添加如下内容：／ｈｏｍｅ／ｗｏｒｋ１９２．１６８．１水添加的内容表示ＩＰ在１９２．１６８．１．木的计算机以读写的权限来访问／ｈｏｍｅ／ｗｏｒｋ目录。／ｈｏｍｅ／ｗｏｒｋ也称为服务器输出共享目录。接着执行如下命令，启动端口映射：＃／ｅｔｃ／ｒｃ．ｄ／ｉｎｉｔ．ｄ／ｐｒｏｔｍａｐｓｔａｒｔ最后执行如下命令启动ＮＦＳ服务，此时ＮＦＳ会激活守护进程，然后就开始监听客户端的请求：＃／ｅｔｃ／ｒｃ．ｄ／ｉｎｉｔ．ｄ／ｎｆｓｓｔａｒｔ在ＮＦＳ服务启动后还要检查Ｌｉｎｕｘ服务器的防火墙等设置，确保没有屏蔽掉ＮＦＳ使用的端口和允许通信的主机。首先在Ｌｉｎｕｘ服务器上进行ＮＦＳ服务器的回环测试，验证共享目录是否能够被访问。在嵌入式系统上运行如下命令。＃ｍｏｕｎｔ－ｔｎｆｓ１９２．１６８．１．１：／ｈｏｍｅ／ｗｏｒｋ／ｍｎｔ命令将Ｌｉｎｕｘ服务器的ＮＦＳ输出共享目录挂载到／ｍａｔ目录下，因此，如果ＮＦＳ工作正常，应该能够在／ｍｎｔ目录中看至Ｕ／ｈｏｍｅ／ｗｏｒｋ共享目录中的内容。在Ｌｉｎｕｘ服务器设置好以后，接下来需要进行客户端的设置。首先需要运行在嵌入式目标系统的Ｌｉｎｕｘ内核支持ＮＦＳ客户端，在嵌入式目标系统的Ｌｉｎｕｘｓｈｅｌｌ下，执行如下命令进行Ｎ