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

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

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

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

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

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

6結(jié)論

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

參考文獻(xiàn)：

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

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

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