Perst嵌入式數據庫存儲結構分析與研究
加入技術(shù)交流群
在Perst中數據都是保存在對象中的，首先要將對象的每個(gè)成員轉換成字節數組的形式，然后在此字節數組前面加上8個(gè)字節的記錄數據基本信息，然后將該對象的整個(gè)字節數組保存在文件的相應位置。
實(shí)際上Perst在保存記錄數據之前都要將記錄數據的類(lèi)信息保存在數據庫文件中，主要目的是實(shí)現類(lèi)對象的動(dòng)態(tài)加載。以類(lèi) Test.User為例說(shuō)明類(lèi)的存儲結構，它的兩個(gè)成員int類(lèi)型（Id）和String類(lèi)型（Name）。Perst先保存類(lèi)的成員變量Id和Name 的信息，然后保存類(lèi)信息。圖4.2是Test.User.Id的存儲結構, Test.User.Name的存儲結構和圖4.2類(lèi)似。
占的總字節數 | Type | 類(lèi)Test.User名字的字符個(gè)數M | “Test.User”的字節數組形式 | 成員變量“Id”的字符個(gè)數N | “Id”的字節數組形式 |
4 bytes | 4 bytes | 4 bytes | 2*M bytes | 4 bytes | 2*N bytes |
圖4.2 類(lèi)Test.User成員變量“Id”的存儲結構
類(lèi)Test.User的存儲結構如圖4.3所示：
占的總字節數 | Type | 類(lèi)Test.User成員變量個(gè)數 | 成員變量“Id”對應得OID | 成員變量“Name”對應的OID |
4 bytes | 4 bytes | 4 bytes | 4 bytes | 4 bytes |
類(lèi)“Test.User”名字的字符個(gè)數N | 類(lèi)“Test.User”名字對應的字節數組形式 |
4 bytes | 4 bytes |
圖4.3 類(lèi)Test.User名字信息的存儲結構
以上是Perst保存記錄對象類(lèi)相關(guān)信息的存儲結構，這樣Perst可以動(dòng)態(tài)的加載類(lèi)對象。
5 B+樹(shù)的存儲結構
Perst之所以能夠應用在移動(dòng)設備上，最主要的原因是它采用了存取方式效率高的B+樹(shù)結構。Perst定義的B+樹(shù)節點(diǎn)大，使得構建出的B+樹(shù)寬度大而深度小，這樣設備進(jìn)行檢索的時(shí)候，減少了對磁盤(pán)I/O操作的次數，從而降低了設備的資源消耗[1]。
5.1 B+樹(shù)的節點(diǎn)及其構成
Perst的B+樹(shù)節點(diǎn)用一個(gè)頁(yè)來(lái)表示（4K），每個(gè)節點(diǎn)中包含4個(gè)字節的節點(diǎn)信息和多個(gè)key,value>，節點(diǎn)信息中前2個(gè)節點(diǎn)表示節點(diǎn)中 key,value >對的個(gè)數，后2個(gè)字節表示索引值占用的總字節數。 key,value >中value表示索引值，key表示對子節點(diǎn)或者是記錄數據對象的OID。索引值的類(lèi)型不同，Perst節點(diǎn)的結構也不同。
1）索引值的類(lèi)型是類(lèi)
當索引是用類(lèi)創(chuàng )建的時(shí)候，在節點(diǎn)的 key,value >對中，索引值就是該記錄對象的OID，key是該記錄對象的OID或者是子節點(diǎn)頁(yè)對象的OID。以OID1,OID3>，OID2,OID4>為例，其中OID1和OID2是key，OID3和OID4是索引值，且 OID3＜OID4其結構如下圖所示：
圖5.1.1 索引的類(lèi)型是類(lèi)的節點(diǎn)存儲結構
2）索引值的類(lèi)型是數值類(lèi)型（如int，long，short等）
當創(chuàng )建索引的類(lèi)型是數值類(lèi)型時(shí)，節點(diǎn) key,value >中，索引值就是該數值，key是子節點(diǎn)的OID或者是和索引值相關(guān)的記錄對象的OID。以OID1,100>，OID2,125>為例說(shuō)明其存儲結構，其中索引值的類(lèi)型是int，存儲結構如下圖所示：
評論