内存数据库技术研究 .pdfVIP

内存数据库技术研究

摘要：内存数据库的体系结构、存储和索引结构、并发控制、故障

恢复机制等，明显不同于磁盘数据库，很多磁盘数据库的设计思想和

方法，很难适用于内存数据库。提出了新的存储结构，改进了传统的

事务模型及恢复机制，提高了内存数据库运行速度和实时性。

关键词：内存数据库；存储；索引；恢复

1内存数据库概述

1.1内存数据库的概念

目前，被业界普遍认可的定义如下：设有数据库系统DBS，DB

为DBS中的数据库，DBM(t)为时刻t数据库在内存的数据集，

DBM(t)DB。TS为所有可能的事务的集合，AT(t)为在时刻t处于

活动状态的事务集，AT(t)TS。D-i(T)为事务T在时刻t所操作的数

据集，D-i(T)DB。若在任一时刻t，均有：T∈AT(t)，D-i(T)

DBM(t)成立，则称DBS为一个内存数据库系统，简写为MMDBS，

DB为一个内存数据库，简记为MMDB。

1.2内存数据库的特点

内存数据库与传统关系型数据库主要区别在于：内存数据库常

驻内存，体系结构设计的优化目标是提高内存和CPU利用率，由于

事务处理无需进行磁盘访问，使用MMDB的应用系统性能得到极大

提高。内存数据库与磁盘数据库的不同，如表1所示：

2内存数据库技术研究

2.1内存数据库的存储结构

内存数据库在存储关系时，一般采取分级结构，元数据与数据

应分区组织，以提高安全性。为了适应内存数据库的存储需要，我们

改进传统数据库的存储方式，同时参考其它的常用数据库，提出了新

的存储模型。首先，存储结构分两层：段和页。段是可变长的，一个

段由多个固定长的页组成，每个段存放一个关系，但并不要求构成段

的页在空间上连续。页是内存数据库的基本内存分配回收单元，其长

度固定，每页长度为8KB。页的结构由两部分组成，控制区存放记录

控制数组，信息区存放页控制信息和记录(即元组)本身。整个数据库

维护一个段表，段表中的每一项是一个段控制块。段控制块中包含一

个页表、段锁和索引链表的头指针。图1显示了新提出的内存数据组

织结构图。

从图1中可以看到：一条记录本身放在页的信息区，对记录的

访问是通过放在控制区的记录控制数组进行的。当一个事务要访问记

录时，先依据关键字查索引，找到该记录的RID。一个RID是一个

由段号、分区号、和记录控

制数组在页中的偏移量组成的三元组，用RID可以很快找到记

录插槽，从而最终定位一条记录。

2.2索引的结构

磁盘数据库采用的索引结构主要是B/B+树，其设计目标是减少

访问磁盘数据的I/O次数。而在MMDB中采用了一种新的索引结构

T树，设计目标是减少内存开销和CPU指令数。T树是由AVL树和

B树发展而来，它是一种一个节点包含多个元素的二叉树。

由于是二叉树，T树保持了AVL树二分查找的高效率，同时一

个T节点包含多个元素，像B树一样，每个节点的充满程度保持在

半满和全满之间，这样索引一般不再需要溢出块，由插入和删除所引

起的数据移动通常只需在一个节点内进行，减少了为保持树的平衡所

必须进行的旋转操作，因此，T树又保持了B树优异的更新和存储特

性。由于索引和数据全在内存中，在一个T树节点中不需要像B树

那样存放N个索引键值-指针对，只需存放指向内存中相应记录对应

字段的指针，这样索引中变长字段的存储不再是问题，另外，由于指

针一般比它指向的字段要小，大量的空间也被节省了。

2.3并发控制

内存数据库长驻内存中，较之传统数据库，在并发控制的设计

上有其新的特点。首先，内存访问速度比磁盘访问速度快，在内存数

据库中，一个事务的执行时间比传统性事务要短的多，事务持有锁的

时间很短，对锁的竞争比较小。其次,数据和元数据均常驻内存(磁盘

数据库中，锁在内存，数据通