Perst嵌入式数据库存储结构分析与研究
对于这种类型的索引值，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+树根节点的时候，会一次性的从数据库文件中读取一个节点大小（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.
评论