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