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

格式都是统一的，每个记录数据的开头占用8个字节存放记录数据的基本信息。前4个字节存放这条记录占用的字节个数，后4个字节存放构建这个记录对象的类的 OID，通过这个OID就可以动态的加载该类的对象。以类Test.User的记录为例，该记录包含一个int类型的数据和一个变量名为“name”的 String类型，其存储结构如图4.1所示：

图4.1 记录数据的存储结构

在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个字节的节点信息和多个key,value>，节点信息中前2个节点表示节点中 key,value >对的个数，后2个字节表示索引值占用的总字节数。 key,value >中value表示索引值，key表示对子节点或者是记录数据对象的OID。索引值的类型不同，Perst节点的结构也不同。

1）索引值的类型是类

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

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

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

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

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

对于这种类型的索引值，value占用多大的空间，是根据数值类型实际占用的空间进行分配的。

3）索引值的类型是字符串或字节数组类型

对于这种类型的索引结构，在保存索引值的时候并不只是保存字符串或字节数组，还会保存字符串的一些信息，如字符串的字符个数，字符串在该节点中存放的相对位置。以OID1,“teacher”>为例，其存储结构如下图所示：

图5.1.3 索引类型是字符串的节点存储结构

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

5.2 B+树在内存中的重建

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

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

Perst找到相应的B+树根节点的时候