Perst嵌入式數(shù)據(jù)庫存儲結構分析與研究

在Perst中數(shù)據(jù)都是保存在對象中的，首先要將對象的每個成員轉換成字節(jié)數(shù)組的形式，然后在此字節(jié)數(shù)組前面加上8個字節(jié)的記錄數(shù)據(jù)基本信息，然后將該對象的整個字節(jié)數(shù)組保存在文件的相應位置。

實際上Perst在保存記錄數(shù)據(jù)之前都要將記錄數(shù)據(jù)的類信息保存在數(shù)據(jù)庫文件中，主要目的是實現(xiàn)類對象的動態(tài)加載。以類 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可以動態(tài)的加載類對象。

5 B+樹的存儲結構

Perst之所以能夠應用在移動設備上，最主要的原因是它采用了存取方式效率高的B+樹結構。Perst定義的B+樹節(jié)點大，使得構建出的B+樹寬度大而深度小，這樣設備進行檢索的時候，減少了對磁盤I/O操作的次數(shù)，從而降低了設備的資源消耗[1]。

5.1 B+樹的節(jié)點及其構成

Perst的B+樹節(jié)點用一個頁來表示（4K），每個節(jié)點中包含4個字節(jié)的節(jié)點信息和多個key,value>，節(jié)點信息中前2個節(jié)點表示節(jié)點中 key,value >對的個數(shù)，后2個字節(jié)表示索引值占用的總字節(jié)數(shù)。 key,value >中value表示索引值，key表示對子節(jié)點或者是記錄數(shù)據(jù)對象的OID。索引值的類型不同，Perst節(jié)點的結構也不同。

1）索引值的類型是類

當索引是用類創(chuàng)建的時候，在節(jié)點的 key,value >對中，索引值就是該記錄對象的OID，key是該記錄對象的OID或者是子節(jié)點頁對象的OID。以OID1,OID3>，OID2,OID4>為例，其中OID1和OID2是key，OID3和OID4是索引值，且 OID3＜OID4其結構如下圖所示：

圖5.1.1 索引的類型是類的節(jié)點存儲結構

2）索引值的類型是數(shù)值類型（如int，long，short等）

當創(chuàng)建索引的類型是數(shù)值類型時，節(jié)點 key,value >中，索引值就是該數(shù)值，key是子節(jié)點的OID或者是和索引值相關的記錄對象的OID。以OID1,100>，OID2,125>為例說明其存儲結構，其中索引值的類型是int，存儲結構如下圖所示：

圖5.1.2 索引的類型是數(shù)值類型的節(jié)點存儲結