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

作者：時(shí)間：2012-03-20 來(lái)源：網(wǎng)絡(luò)

加入技術(shù)交流群
- 掃碼加入
  和技術(shù)大咖面對(duì)面交流
  海量資料庫(kù)查詢(xún)

在Perst中數(shù)據(jù)都是保存在對(duì)象中的，首先要將對(duì)象的每個(gè)成員轉(zhuǎn)換成字節(jié)數(shù)組的形式，然后在此字節(jié)數(shù)組前面加上8個(gè)字節(jié)的記錄數(shù)據(jù)基本信息，然后將該對(duì)象的整個(gè)字節(jié)數(shù)組保存在文件的相應(yīng)位置。

實(shí)際上Perst在保存記錄數(shù)據(jù)之前都要將記錄數(shù)據(jù)的類(lèi)信息保存在數(shù)據(jù)庫(kù)文件中，主要目的是實(shí)現(xiàn)類(lèi)對(duì)象的動(dòng)態(tài)加載。以類(lèi) Test.User為例說(shuō)明類(lèi)的存儲(chǔ)結(jié)構(gòu)，它的兩個(gè)成員int類(lèi)型（Id）和String類(lèi)型（Name）。Perst先保存類(lèi)的成員變量Id和Name 的信息，然后保存類(lèi)信息。圖4.2是Test.User.Id的存儲(chǔ)結(jié)構(gòu), Test.User.Name的存儲(chǔ)結(jié)構(gòu)和圖4.2類(lèi)似。

占的總字節(jié)數(shù)	Type	類(lèi)Test.User名字的字符個(gè)數(shù)M	“Test.User”的字節(jié)數(shù)組形式	成員變量“Id”的字符個(gè)數(shù)N	“Id”的字節(jié)數(shù)組形式
4 bytes	4 bytes	4 bytes	2*M bytes	4 bytes	2*N bytes

圖4.2 類(lèi)Test.User成員變量“Id”的存儲(chǔ)結(jié)構(gòu)

類(lèi)Test.User的存儲(chǔ)結(jié)構(gòu)如圖4.3所示：

占的總字節(jié)數(shù)

Type

類(lèi)Test.User成員變量個(gè)數(shù)

成員變量“Id”對(duì)應(yīng)得OID

成員變量“Name”對(duì)應(yīng)的OID

4 bytes

類(lèi)“Test.User”名字的字符個(gè)數(shù)N	類(lèi)“Test.User”名字對(duì)應(yīng)的字節(jié)數(shù)組形式
4 bytes	4 bytes

圖4.3 類(lèi)Test.User名字信息的存儲(chǔ)結(jié)構(gòu)

以上是Perst保存記錄對(duì)象類(lèi)相關(guān)信息的存儲(chǔ)結(jié)構(gòu)，這樣Perst可以動(dòng)態(tài)的加載類(lèi)對(duì)象。

5 B+樹(shù)的存儲(chǔ)結(jié)構(gòu)

Perst之所以能夠應(yīng)用在移動(dòng)設(shè)備上，最主要的原因是它采用了存取方式效率高的B+樹(shù)結(jié)構(gòu)。Perst定義的B+樹(shù)節(jié)點(diǎn)大，使得構(gòu)建出的B+樹(shù)寬度大而深度小，這樣設(shè)備進(jìn)行檢索的時(shí)候，減少了對(duì)磁盤(pán)I/O操作的次數(shù)，從而降低了設(shè)備的資源消耗[1]。

5.1 B+樹(shù)的節(jié)點(diǎn)及其構(gòu)成

Perst的B+樹(shù)節(jié)點(diǎn)用一個(gè)頁(yè)來(lái)表示（4K），每個(gè)節(jié)點(diǎn)中包含4個(gè)字節(jié)的節(jié)點(diǎn)信息和多個(gè)key,value>，節(jié)點(diǎn)信息中前2個(gè)節(jié)點(diǎn)表示節(jié)點(diǎn)中 key,value >對(duì)的個(gè)數(shù)，后2個(gè)字節(jié)表示索引值占用的總字節(jié)數(shù)。 key,value >中value表示索引值，key表示對(duì)子節(jié)點(diǎn)或者是記錄數(shù)據(jù)對(duì)象的OID。索引值的類(lèi)型不同，Perst節(jié)點(diǎn)的結(jié)構(gòu)也不同。

1）索引值的類(lèi)型是類(lèi)

當(dāng)索引是用類(lèi)創(chuàng)建的時(shí)候，在節(jié)點(diǎn)的 key,value >對(duì)中，索引值就是該記錄對(duì)象的OID，key是該記錄對(duì)象的OID或者是子節(jié)點(diǎn)頁(yè)對(duì)象的OID。以O(shè)ID1,OID3>，OID2,OID4>為例，其中OID1和OID2是key，OID3和OID4是索引值，且 OID3＜OID4其結(jié)構(gòu)如下圖所示：

圖5.1.1 索引的類(lèi)型是類(lèi)的節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)

2）索引值的類(lèi)型是數(shù)值類(lèi)型（如int，long，short等）

當(dāng)創(chuàng)建索引的類(lèi)型是數(shù)值類(lèi)型時(shí)，節(jié)點(diǎn) key,value >中，索引值就是該數(shù)值，key是子節(jié)點(diǎn)的OID或者是和索引值相關(guān)的記錄對(duì)象的OID。以O(shè)ID1,100>，OID2,125>為例說(shuō)明其存儲(chǔ)結(jié)構(gòu)，其中索引值的類(lèi)型是int，存儲(chǔ)結(jié)構(gòu)如下圖所示：