Perst嵌入式數據庫存儲結構分析與研究

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

5.2 B+樹(shù)在內存中的重建

Perst將整個(gè)B+樹(shù)的結構保存在數據庫文件中，當程序對數據操作的時(shí)候如何將整個(gè)B+樹(shù)裝入內存呢？

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

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

6結論

本文著(zhù)重分析了Perst的文件存儲結構。B+樹(shù)結構的設計使其在嵌入式設備上減少了對磁盤(pán)的I/O操作，適應了嵌入式設備資源受限的特點(diǎn)。

參考文獻：

[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].北京:機械工業(yè)出版社,2006.274-339.