Perst嵌入式数据库存储结构分析与研究

引言

Perst是McObject公司发布的一款非常袖珍的开源嵌入式数据库，是一个简单，快速，便捷，面向对象，适合java与.Net的数据库。Perst不需要专门的编译器与预处理器，支持ACID事务[2]。对于在资源受限的移动设备（如手机，PDA等）上存储大量数据和对数据进行频繁的I/O操作往往要消耗很多的设备资源。由于移动设备内存小，性能较差，如果采用关系数据库（如 SQLServer2000，Oracle）管理数据，仅靠其有限的内存资源是不能运行这些数据库管理系统的，这样就有必要采用一些特殊的数据库系统。 Perst数据库正是为这类设备研究开发的，它们是如何在资源受限的设备上完成大量数据的访问操作。其实这些设备的系统资源主要消耗在从磁盘上读取数据的 I/O操作。如何提供一种有效的文件存储策略来降低对磁盘的I/O操作是嵌入式数据库软件设计的主要任务。文章将着重介绍Perst嵌入式数据库的文件存储策略和B+树索引结构[3]。

1 Perst基本概念介绍

1.1 页Page

Perst对数据库文件的基本操作都是以页为单位进行的。这些基本操作包括：内存分配，从数据库文件中读取数据，将内存中的数据写入文件等。Perst一页默认的大小是4K。

1.2 对象标识符OID

Perst创建的每个对象都是可以持久化的，即它可以被保存在数据库文件中。每个持久化的对象都会用对象标识符（OID）引用，通过对象标识符，程序可以从数据库文件中找到该对象在文件中实际存放位置。

1.3 Root Object

Perst的每个数据库文件都必须有且只能有一个称作Root Object的类。在这个类中定义了数据库文件中的所有索引结构。通过这个类，程序可以定位到数据库文件中的所有记录对象。

2 数据库Header信息的存储格式

Perst数据库文件开始的第一页中，前139个字节存放Perst数据库使用情况和数据库当前状态等Header信息。它在文件中的数据结构如图2.1所示。表2.1到2.4对图2.1中Header信息中的每个数据做了详细分析。数据意义如表所示。

图2.1 数据库的Header信息

表2.1 数据库Header信息前3个字节意义

表2.2数组root[0]结构

数组root[1]是root[0]的备份，每个元素对应的意义相同[page]

表2.3 数组root[1]结构

表2.4 事务id

数据库文件的第一页（4K）存放了整个数据库文件的Header信息。程序从数据库文件的Header信息中分离出数据库文件的使用情况和索引结构的存储位置，这样可以很快的定位数据库中的记录数据。

3 Perst的Object Index存储结构

Perst专门开辟了一段空间，称Object Index区，存放持久化对象在文件中的实际存储位置。一般这个区在文件的第2-10页，第11-19页存放这个区的备份。第2-9页的数据被标识为空闲文件区，第10页存放实际Object Index。

在Object Index区中，每个元素称为Object Handle，每Object Handle用8个字节表示，存放对应对象在文件中的实际存储位置，即对象的OID。对于4K的页，可以存放512个Object Handles。Object Index区的结构如图3.1所示。

图4.1 记录数据的存储结构[page]

在Perst中数据都是保存在对象中的，首先要将对象的每个成员转换成字节数组的形式，然后在此字节数组前面加上8个字节的记录数据基本信息，然后将该对象的整个字节数组保存在文件的相应位置。

实际上Perst在保存记录数据之前都要将记录数据的类信息保存在数据库文件中，主要目的是实现类对象的动态加载。以类 Test.User为例说明类的存储结构，它的两个成员int类型（Id）和String类型（Name）。Perst先保存类的成员变量Id和Name 的信息，然后保存类信息。图4.2是Test.User.Id的存储结构, Test.User.Name的存储结构和图4.2类似。

图4.2 类Test.User成员变量“Id”的存储结构

类Test.User的存储结构如图4.3所示：

图4.3 类Test.User名字信息的存储结构

以上是Perst保存记录对象类相关信息的存储结构，这样Perst可以动态的加载类对象。

5 B+树的存储结构

Perst之所以能够应用在移动设备上，最主要的原因是它采用了存取方式效率高的B+树结构。Perst定义的B+树节点大，使得构建出的B+树宽度大而深度小，这样设备进行检索的时候，减少了对磁盘I/O操作的次数，从而降低了设备的资源消耗[1]。

5.1 B+树的节点及其构成

Perst的B+树节点用一个页来表示（4K），每个节点中包含4个字节的节点信息和多个，节点信息中前2个节点表示节点中< key,value >对的个数，后2个字节表示索引值占用的总字节数。< key,value >中value表示索引值，key表示对子节点或者是记录数据对象的OID。索引值的类型不同，Perst节点的结构也不同。

1）索引值的类型是类

当索引是用类创建的时候，在节点的< key,value >对中，索引值就是该记录对象的OID，key是该记录对象的OID或者是子节点页对象的OID。以，为例，其中OID1和OID2是key，OID3和OID4是索引值，且 OID3＜OID4其结构如下图所示：

图5.1.1 索引的类型是类的节点存储结构

2）索引值的类型是数值类型（如int，long，short等）

当创建索引的类型是数值类型时，节点< key,value >中，索引值就是该数值，key是子节点的OID或者是和索引值相关的记录对象的OID。以，为例说明其存储结构，其中索引值的类型是int，存储结构如下图所示：

图5.1.2 索引的类型是数值类型的节点存储结[page]

从以上三种不同类型的节点存储结构，可以看出B+树节点存储结构的共同点：1）节点的前4个字节保存该节点的基本信息；2）的存放：一个从节点页的开头按照其插入的顺序存放（从前向后），另一个则是从节点页的末尾开始存放（从后向前）。这样处理的好处是可以很快地从节点中取出，不用经过很复杂的计算过程，节省了设备资源的使用。

5.2 B+树在内存中的重建

Perst将整个B+树的结构保存在数据库文件中，当程序对数据操作的时候如何将整个B+树装入内存呢？

Perst中有一个可以引用所有记录对象的Root Object的类，通过这个类Perst除了可以动态的加载B+树类对象，而且可以很快的从数据库文件中定位B+树根节点的文件存储位置。

Perst找到相应的B+树根节点的时候，会一次性的从数据库文件中读取一个节点大小（4K）的数据到内存中。由于在节点构建的时候索引值是顺序存放的，因此程序可以用二分查找的算法在节点中查找符合条件的索引值，如果找到就可以定位到此节点的子节点或者是和索引值对应的记录对象。如果节点是叶节点，程序就可以从这个节点中找出和索引值对应的对象的OID，通过OID，Perst就可以从文件中读取到整个记录的字节数组形式，通过类对象的动态加载机制可以把字节数组还原为记录对象的形式。如果是内部节点，根据内部节点的OID，Perst会将内部节点的数据读取到内存中。这些被加载到内存中的数据会临时的存放在一个对象缓冲区，当需要的时候就可以直接从对象索引区读取数据，而不用重复的进行I/O操作。只有对象缓冲区满时，Perst采用LRU置换机制把内存中的数据写入数据库文件中。

6结论

本文着重分析了Perst的文件存储结构。B+树结构的设计使其在嵌入式设备上减少了对磁盘的I/O操作，适应了嵌入式设备资源受限的特点。

参考文献：

[1]Ramez Elmasri,Shamkant B.Navathe数据库系统基础初级篇[M].北京:人民邮电出版社，2007.305-355.

[2]东缘.Perst嵌入式数据库获Android平台兼容性验证[EB/OL]. http://webservices.ctocio.com.cn/wsopen/114/7766114.shtml.

[3] Abraham Silberschatz,Henry F.Korth,S.Sudarshan.数据库系统概念[M].北京:机械工业出版社,2006.274-339.