嵌入式内存数据库的研究与设计

摘要：近年来,各种嵌入式内存数据库不断涌现,但由于各种原因,很多产品不具有通用性、高效性、可靠性,以致于很难在市场上推广开来。针对上述情况,提出一种新的嵌入式内存数据库的设计方法,该方法结合当前流行的java语言和面向对象的思想,充分利用java语言本身的多线程机制,研究出基于多线程机制的嵌入式内存数据库的事务模型,检查点方法和恢复策略,同时对数据库的存储管理和索引机制进行了探讨。实践证明,相对于其它产品,本方法能大幅度的提高嵌入式内存数据库的性能。

0引言

随着硬件的发展，内存的容量在不断扩大，人们长期思考的将全部或大部分数据存放在 内存中运行成为可能。同时，嵌入式设备在日常生活中得到广泛应用，如何对其内部日益繁 多的数据进行管理显得很关键。当前嵌入式内存数据库产品很多，大多数产品由于各方面的 限制，在性能和市场前景方面表现欠佳。在嵌入式内存数据库研究领域，新的存储与索引方 法被不断提出，同时面向对象的程序设计语言java作为当前主流开发语言，在多线程和死锁 处理方面有其独特之处，为提出新的嵌入式内存数据库的设计方法，及基于事务模型的恢复 方法提供了可能。

1嵌入式内存数据库概述

嵌入式内存数据库的设计一般采取两种思路：一种是对传统的大型数据库进行裁剪和改 进，很多处理问题的方法仍采用传统数据库的方法，某些方法在嵌入式内存数据库不适用则 做些稍微改进，这种思路没有逃离传统数据库设计思想的束缚。另一种则是根据嵌入式内存 数据库自身的特点，提出新的体系结构，存储结构和恢复机制，以满足嵌入式内存数据库的 要求。目前，第二种方法被普遍采用和推崇，本文新的设计方法就采用后者。

1.2嵌入式内存数据库的体系结构

在新的体系结构中，我们采用关系数据模型，最上层提供外部查询接口，支持多种常用 语言如C,java等语言连接数据库。第二层是对SQL语句进行解析的查询命令分解与优化层， 这一层下面是两个重要的模块：数据组织与管理和事务管理器。其中，数据组织与管理模块 完成常用的索引和数据组织工作，事务管理器具有创建事务，调度事务，回收事务的功能。 内存工作区是该体系结构最重要的模块，全部数据操作及日志处理在这里进行，它在事务处 理时为每一个事务分配一个内存工作区，其中存放数据和日志。日志管理器管理内存工作区 中的日志，而恢复管理器则在系统出现故障时起作用。该数据库大部分操作在内存工作区中 运行，只有当发生检查点操作和数据库备份，及系统恢复时才与外面的磁盘打交道，因此该 数据库是典型的嵌入式内存数据库。上述体系结构图如图1所示：

2．数据的存储与索引

嵌入式内存数据库通常在内存受限的环境中进行，CPU能直接操纵内存中的数据，且数 据经常由于各种故障而丢失。因此合理的有效利用内存资源，减少内存开销和CPU指令数， 使内存空间得到高效利用很关键，为此我们引用了一种新的存储与索引方法——T树。

T树是将AVL树和B树结合在一起而得出的一种新的数据结构，T树也是一种二叉树，只不 过每个结点(称为T结点)都包含多个元素。每个T结点都包含一系列从小到大排序后的元素和 三个指针，指针分别指向父结点和左右结点。某一T结点A的左结点中必会包含比A结点中最 小元素小的最大元素，而A结点的右结点中必会包含比A结点中最大元素大的最小元素。因为 是二叉树，所以T树具有AVL树固有的二分查找特性，又因为每个结点包含多个元素,其又包 含了B树良好的更新和存储特性的优点。对T树来说，因插入和删除数据所造成的数据移动通 常可以局限在一个结点内进行，和AVL树一样，T树也是通过旋转来使树达到平衡的, 但其所 需要的旋转操作的次数远少于AVL树[ 2 ]。T树结点结构如图2所示:

3基于事务处理的恢复模块设计

本嵌入式内存数据库，我们采用了基于多线程的事务模型，利用java语言作为开发语言， Eclipse3.2为开发工具，充分采用java语言的多线程机制和面向对象的思想来开发数据库。

在该事务模型中，我们将事务作为一个线程来看待，理由如下:(1)java语言有自己独特 的多线程机制，具有开始状态，各种活动状态，结束状态，把线程作为一个事务整体运行， 能够满足事务需求的各种操作，及自身的ACID属性。(2)java语言有多线程处理时的同步操 作，事务处理时可以利用这种思想处理多事务之间的并发控制操作[ 3 ] 。我们利用事务管理 器创建事务，并在影子内存工作区为每一个事务分配相应的影子内存工作区，其中包括该事 务应处理的数据和日志，可以说该模型是影子