摘 要：目前，绝大多数嵌入式数据库系统都使用B+树索引机制。它的优点是效率高，能同时进行随机查找和顺序查找，且能动态维持平衡。然而根据研究表明B+树索引机制平均空间利用率仅达到50%左右，这对存储空间有限的嵌入式设备而言，B+树索引机制存在浪费存储空间的缺点。
本文的主要任务是研究和实现一个具有较高存储空间利用率的，面向嵌入式数据库的索引机制。笔者首先介绍嵌入式数据库中比较有代表意义的索引机制以及它们的优缺点，再分析了B+树索引机制，AVL树索引机制，HASHAVL树索引机制的实现思想及其优缺点，最后，Matalab试环境平台，进行了测试实验，对树索引机制在相同条件下的消耗时间利用率两个方面进行测试和比较，并分析各种索引机制测试结果出现差异的原因，这对实时性要求不高的嵌入式数据库系统(如智能手机等移动设备中利用嵌入式数据库系统来管理用户资料)中，如何充分利用有限的嵌入式设备存储空间有较强的指导意义。
关键词：嵌入式数据库，索引机制，算法实现，Matalab
毕业设计（论文）外文摘要
The development of embedded memory database transplantation
Abstract: Currently, the most embedded database systems use B+ tree indexing mechanism. It has advantage of high efficiency and being able to process operations on the records of B+ tree randomly and sequentially, It can maintain the dynamic balance of the tree.However,the B+ tree indexing mechanism has a fatal disadvantage for wasting storage space capacity in the embedded systems. The statistic shows that B+ tree indexing mechanism guarantee only about 50% storage utilization.
The main task of this dissertation is to study and achieve an indexing mechanism in the embedded database system ,It has higher utilization than B+ tree indexing mechanism. At first, The dissertation introduces some classic indexing mechanism in the embedded database and analyses their advantage and disadvantages. the embedded database on behalf of more significance in the index mechanisms as well as their advantages and disadvantages, and then analyzed the mechanism of B+ tree index, AVL tree indexing mechanism, HASHAVL tree indexing mechanism for the realization of ideas and their advantages and disadvantages, and finally, Matlab Test environmental platform, a test experiment, the index mechanism of the tree under the same conditions in the two aspects of the utilization of time-consuming to test and compare, The result has some advantages for making the best use of the limited storage space for equipment in the embedded database system which request for a little real-time performance, such as intelligent mobile phones use embedded database system to manage users' information..
Keywords: Embedded Database, Indexing Mechanism , Algorithm realized , Matalab
本课题的研究手段
模拟仿真是一基于模型的活动，是用模型模拟来代替真实系统进行实验和研究。因此，首先就要对待仿真的问题进行定量描述，这就是建立系统的数学模型。模型是对真实世界的模仿，真实世界是五彩缤纷的，因此模型也是千姿百态的；根据模型中是否包含随机因素，可分为随机型和确定型模型。根据模型是否具有时变性，可分为动态模型和静态模型；根据模型参数是否在空间连续变化，可分为分布参数模型和集中参数模型；根据模型参数是否随时间连续变化，可分为连续系统模型和离散系统模型；根据模型的数学描述形式，又可分为常微分方程、偏微分方程、差分方程、离散事件模型等。
仿真计算
仿真计算是对所建立的仿真模型进行数值实验和求解的过程，不同的模型有不同的求解方法。例如：对于连续系统，通常用常微分方程、传递函数，甚至偏微分方程对 其进行描述。由于要得到这些方程的解析解几乎是不可能的，所以总是采用数值解法，如：对于常微分方程主要采用各种数值积分法，对于偏微分方程则采用有限差 分法、特征法、蒙特卡罗法或有限元方法等。
又例如：对于离散事件系统，通常采用概率模型，其仿真过程实际上是一个数值实验的过程，而这些参数又必须符合一定的概率分布规律。对于不同类型的离散事件系统（如随机服务系统、随机库存系统、随机网络计划等）有不同的仿真方法。
随着被仿真对象复杂程度的提高和对仿真实时性的迫切要求，研究新的仿真算法一直是一项重要的任务，特别是研究各种并行的仿真算法。
仿真结果的分析
要想通过模拟仿真得出正确、有效地结论，必须对仿真结果进行科学的分析。早期的仿真软件都是以大量数据的形式输出仿真的结果，因此有必要对仿真结果数据进行 整理，进行各种统计分析，以得到科学的结论。现代仿真软件广泛采用了可视化技术，通过图形、图表，甚至动画生动逼真地显示出被仿真对象的各种状态，使模拟 仿真的输出信息更加丰富、更加详尽、更加有利于对仿真结果的科学分析。
研究本课题所使用的语言和工具
Visual Studio2005是微软公司发布的一种面向对象的、运行于.NET Framework之上的高级程序设计语言。模拟分析统计软件Matalab 7.1。
论文的章节安排
本论文的文章安排如下：
第一章: 介绍课题背景，本论文研究的意义以及国内外嵌入式数据库的研究现状。
第二章 : 介绍嵌入式数据库的定义，特点，以及在各行各业中的应用;介绍国内外比较有影响力的嵌入式数据库.
第三 章 : 介绍在嵌入式数据库使用较多的几种索引机制，并分析它们的优缺点。
第四 章 :对传统的嵌入式数据库索引机制进行实现。
第五 章 : 试验分析，并用Matalab进行统计对比，做出结论。
最后是参考文献和致谢。
目 录 24000字
1 绪论 1
1.1 本课题的研究意义 1
1.2 国内外发展趋势 2
1.3 本课题采用的研究手段和途径 3
1.3.1 本课题的研究手段 3
1.3.2 研究本课题所使用的语言和工具 4
1.4 可行性分析 4
1.5 论文的章节安排 5
2 嵌入式数据库背景知识 6
2.1 嵌入式数据库概述 6
2.1.1 嵌入式数据库定义 6
2.1.2 嵌入式数据库特点 6
2.1.3嵌入式数据库研究现状 7
2.1.4嵌入式数据库应用 9
2.2国内外主要的嵌入式数据库产品 10
2.2.1 国外嵌入式数据库系统介绍 10
2.2.2 国内嵌入式数据库系统介绍 12
3 嵌入式数据库索引技术 14
3.1 线性散列方法 14
3.1.1 定义 14
3.1.2 查找方法 14
3.1.3 插入方法 14
3.1.4 删除方法 15
3.1.5 优缺点 15
3.2 ISAM树 15
3.2.1 定义 15
3.2.2 查找方法 16
3.2.3 插入方法 17
3.2.4 删除方法 17
3.2.5 优缺点 17
3.3 B树 17
3.3.1 定义 18
3.3.2 查找方法 18
3.3.3 插入方法 19
3.3.4 删除方法 19
3.3.5 优缺点 20
3.4 R树 20
3.4.1 定义 21
3.4.2 查找方法 21
3.4.3 插入方法 22
3.4.4 删除方法 22
3.4.5 优缺点 22
3.5 小结 23
4 传统索引机制的实现 24
4.1 二叉树的实现 24
4.2 AVL树的实现 31
4.3 哈希AVL树的实现 34
4.4 哈希红黑树的实现 37
5 实验测试 42
5.1测试环境 42
5.2 查询测试 42
5.3 删除测试 42
5.4 插入测试 43
6 改进 45
6.1树的定义 45
6.2 改进树的查找 46
6.3 实验测试 46
结 论 47
致 谢 48
参 考 文 献 49
|
