Perst嵌入式數(shù)據(jù)庫存儲結構分析與研究
加入技術交流群
對于這種類型的索引值，value占用多大的空間，是根據(jù)數(shù)值類型實際占用的空間進行分配的。
3）索引值的類型是字符串或字節(jié)數(shù)組類型
對于這種類型的索引結構，在保存索引值的時候并不只是保存字符串或字節(jié)數(shù)組，還會保存字符串的一些信息，如字符串的字符個數(shù)，字符串在該節(jié)點中存放的相對位置。以OID1,“teacher”>為例，其存儲結構如下圖所示：
圖5.1.3 索引類型是字符串的節(jié)點存儲結構
從以上三種不同類型的節(jié)點存儲結構，可以看出B+樹節(jié)點存儲結構的共同點：1）節(jié)點的前4個字節(jié)保存該節(jié)點的基本信息；2）key,value>的存放：一個從節(jié)點頁的開頭按照其插入的順序存放（從前向后），另一個則是從節(jié)點頁的末尾開始存放（從后向前）。這樣處理的好處是可以很快地從節(jié)點中取出key,value>，不用經(jīng)過很復雜的計算過程，節(jié)省了設備資源的使用。
5.2 B+樹在內存中的重建
Perst將整個B+樹的結構保存在數(shù)據(jù)庫文件中，當程序對數(shù)據(jù)操作的時候如何將整個B+樹裝入內存呢？
Perst中有一個可以引用所有記錄對象的Root Object的類，通過這個類Perst除了可以動態(tài)的加載B+樹類對象，而且可以很快的從數(shù)據(jù)庫文件中定位B+樹根節(jié)點的文件存儲位置。
Perst找到相應的B+樹根節(jié)點的時候，會一次性的從數(shù)據(jù)庫文件中讀取一個節(jié)點大小（4K）的數(shù)據(jù)到內存中。由于在節(jié)點構建的時候索引值是順序存放的，因此程序可以用二分查找的算法在節(jié)點中查找符合條件的索引值，如果找到就可以定位到此節(jié)點的子節(jié)點或者是和索引值對應的記錄對象。如果節(jié)點是葉節(jié)點，程序就可以從這個節(jié)點中找出和索引值對應的對象的OID，通過OID，Perst就可以從文件中讀取到整個記錄的字節(jié)數(shù)組形式，通過類對象的動態(tài)加載機制可以把字節(jié)數(shù)組還原為記錄對象的形式。如果是內部節(jié)點，根據(jù)內部節(jié)點的OID，Perst會將內部節(jié)點的數(shù)據(jù)讀取到內存中。這些被加載到內存中的數(shù)據(jù)會臨時的存放在一個對象緩沖區(qū)，當需要的時候就可以直接從對象索引區(qū)讀取數(shù)據(jù)，而不用重復的進行I/O操作。只有對象緩沖區(qū)滿時，Perst采用LRU置換機制把內存中的數(shù)據(jù)寫入數(shù)據(jù)庫文件中。
6結論
本文著重分析了Perst的文件存儲結構。B+樹結構的設計使其在嵌入式設備上減少了對磁盤的I/O操作，適應了嵌入式設備資源受限的特點。
參考文獻：
[1]Ramez Elmasri,Shamkant B.Navathe數(shù)據(jù)庫系統(tǒng)基礎初級篇[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.
評論