一种新的嵌入式内存数据库的设计

　随着 硬件的发展，内存的容量在不断扩大，人们长期思考的将全部或大部分数据存放在 内存中运行成为可能。同时， 嵌入式设备在日常生活中得到广泛应用，如何对其内部日益繁 多的数据进行管理显得很关键。当前嵌入式内存数据库 产品很多，大多数产品由于各方面的 限制，在性能和市场前景方面表现欠佳。在嵌入式内存数据库研究领域，新的存储与 索引方 法被不断提出，同时面向对象的程序设计语言 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 ］。