基于H-UT索引机制的嵌入式数据库研究与实现

摘要

随着嵌入式技术的快速发展和其应用领域的不断扩大，单纯的文件系统已经无法满足系统和用户对大量数据处理的各种要求。因此嵌入式数据库的概念随之引入，它作为嵌入式软件的一个分支越来越受到业界的重视。
　　 本文首先分析和研究了嵌入式数据库技术的基本理论，并且详细地阐述了传统索引机制Hash表，平衡二叉树，T树，UT树，Hybrid-TH等，在传统混合索引机制Hybrid-TH的基础上结合UT树提出了一种新的索引机制--H-UT(Hash-Unbalanced T Tree)。H-UT是对Hybrid-TH的进一步改进，将Hash表和树的特点有机地结合起来，在有效地降低查询时间的同时，减少空间的消耗，使之适应嵌入式实时数据库的新要求。在此基础上，以开源嵌入式数据库管理系统SQLite为原型，设计并实现了嵌入式数据库管理系统MYSQLITE。
　　 最后，通过对Hybrid-TH和H-UT两种混合索引机制的一系列对比实验，验证了H-UT索引机制的优良时空性能。

目录

文摘

英文文摘

第一章 绪论

1.1 论文研究背景及选题意义

1.2 论文的主要工作

1.3 论文的组织

第二章 嵌入式数据库概述

2.1 嵌入式数据库的发展

2.2 嵌入式数据库系统的特点

2.3 适应于嵌入式数据库的索引机制

第三章 传统索引机制分析

3.1 哈希索引机制

3.1.1 Hash索引机制概述

3.1.2 几种主要的哈希索引机制

3.2 平衡二叉树索引机制

3.2.1 平衡二叉树定义

3.2.2 平衡二叉树的基本操作

3.3 T树索引机制与UT树索引机制

3.3.1 T树索引机制

3.3.2 UT树

3.4 Hybrid-TH索引机制

3.4.1 Hybrid-TH索引机制定义

3.4.2 Hybrid-TH索引机制的基本操作

3.4.3 Hybrid-TH索引机制的性能分析

第四章 H-UT索引机制

4.1 H-UT索引机制的结构

4.1.1 H-UT的定义

4.1.2 H-UT索引机制和Hybrid-TH索引结构的区别

4.2 H-UT索引机制的基本操作

4.2.1 H-UT索引机制查询算法

4.2.2 H-UT索引机制插入算法

4.2.3 H-UT索引机制删除算法

4.3 性能分析与比较

4.3.1 空间耗用量分析

4.3.2 查找性能分析

4.3.3 最坏情况下H-UT索引机制的性能分析

第五章 嵌入式数据库管理系统MYSQLITE的实现

5.1 MYSQLITE的体系架构

5.2 MYSQLITE的接口层设计

5.3 MYSQLITE编译器设计

5.3.1 标记处理器(tokenizer)的工作过程

5.3.2 分析器(parser)处理过程

5.3.3 代码生成器工作原理

5.4 MYSQLITE虚拟机(VDBE)

5.5 MYSQLITE存取管理层设计

5.5.1 数据页设计

5.5.2 功能函数

第六章 性能测试结果与比较评价

6.1 测试平台及测试条件描述

6.2 测试结果及性能分析

6.2.1 均匀分布情况下的性能测试

6.2.2 最坏情况下性能测试

6.3 总结

第七章 结束语

致谢

参考文献

硕士在读期间的研究成果