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

從以上三種不同類型的節(jié)點存儲結(jié)構(gòu)，可以看出B+樹節(jié)點存儲結(jié)構(gòu)的共同點：1）節(jié)點的前4個字節(jié)保存該節(jié)點的基本信息；2）key,value>的存放：一個從節(jié)點頁的開頭按照其插入的順序存放（從前向后），另一個則是從節(jié)點頁的末尾開始存放（從后向前）。這樣處理的好處是可以很快地從節(jié)點中取出key,value>，不用經(jīng)過很復(fù)雜的計算過程，節(jié)省了設(shè)備資源的使用。

5.2 B+樹在內(nèi)存中的重建

Perst將整個B+樹的結(jié)構(gòu)保存在數(shù)據(jù)庫文件中，當(dāng)程序?qū)?shù)據(jù)操作的時候如何將整個B+樹裝入內(nèi)存呢？

Perst中有一個可以引用所有記錄對象的Root Object的類，通過這個類Perst除了可以動態(tài)的加載B+樹類對象，而且可以很快的從數(shù)據(jù)庫文件中定位B+樹根節(jié)點的文件存儲位置。

Perst找到相應(yīng)的B+樹根節(jié)點的時候，會一次性的從數(shù)據(jù)庫文件中讀取一個節(jié)點大小（4K）的數(shù)據(jù)到內(nèi)存中。由于在節(jié)點構(gòu)建的時候索引值是順序存放的，因此程序可以用二分查找的算法在節(jié)點中查找符合條件的索引值，如果找到就可以定位到此節(jié)點的子節(jié)點或者是和索引值對應(yīng)的記錄對象。如果節(jié)點是葉節(jié)點，程序就可以從這個節(jié)點中找出和索引值對應(yīng)的對象的OID，通過OID，Perst就可以從文件中讀取到整個記錄的字節(jié)數(shù)組形式，通過類對象的動態(tài)加載機制可以把字節(jié)數(shù)組還原為記錄對象的形式。如果是內(nèi)部節(jié)點，根據(jù)內(nèi)部節(jié)點的OID，Perst會將內(nèi)部節(jié)點的數(shù)據(jù)讀取到內(nèi)存中。這些被加載到內(nèi)存中的數(shù)據(jù)會臨時的存放在一個對象緩沖區(qū)，當(dāng)需要的時候就可以直接從對象索引區(qū)讀取數(shù)據(jù)，而不用重復(fù)的進行I/O操作。只有對象緩沖區(qū)滿時，Perst采用LRU置換機制把內(nèi)存中的數(shù)據(jù)寫入數(shù)據(jù)庫文件中。

6結(jié)論

本文著重分析了Perst的文件存儲結(jié)構(gòu)。B+樹結(jié)構(gòu)的設(shè)計使其在嵌入式設(shè)備上減少了對磁盤的I/O操作，適應(yīng)了嵌入式設(shè)備資源受限的特點。

參考文獻：

[1]Ramez Elmasri,Shamkant B.Navathe數(shù)據(jù)庫系統(tǒng)基礎(chǔ)初級篇[M].北京:人民郵電出版社，2007.305-355.

[2]東緣.Perst嵌入式數(shù)據(jù)庫獲Android平臺兼容性驗證[EB/OL]. http://webservices.ctocio.com.cn/wsopen/114/7766114.shtml.

[3] Abraham Silberschatz,Henry F.Korth,S.Sudarshan.數(shù)據(jù)庫系統(tǒng)概念[M].北京:機械工業(yè)出版社,2006.274-339.