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

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

實(shí)際上Perst在保存記錄數(shù)據(jù)之前都要將記錄數(shù)據(jù)的類信息保存在數(shù)據(jù)庫文件中，主要目的是實(shí)現(xiàn)類對象的動態(tài)加載。以類 Test.User為例說明類的存儲結(jié)構(gòu)，它的兩個成員int類型（Id）和String類型（Name）。Perst先保存類的成員變量Id和Name 的信息，然后保存類信息。圖4.2是Test.User.Id的存儲結(jié)構(gòu), Test.User.Name的存儲結(jié)構(gòu)和圖4.2類似。

圖4.2 類Test.User成員變量“Id”的存儲結(jié)構(gòu)

類Test.User的存儲結(jié)構(gòu)如圖4.3所示：

圖4.3 類Test.User名字信息的存儲結(jié)構(gòu)

以上是Perst保存記錄對象類相關(guān)信息的存儲結(jié)構(gòu)，這樣Perst可以動態(tài)的加載類對象。

5 B+樹的存儲結(jié)構(gòu)

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

5.1 B+樹的節(jié)點(diǎn)及其構(gòu)成

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

1）索引值的類型是類

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

圖5.1.1 索引的類型是類的節(jié)點(diǎn)存儲結(jié)構(gòu)

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

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

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