Perst嵌入式數(shù)據(jù)庫(kù)介紹
Perst 是McObject 公司發(fā)布的一款非常袖珍的開源嵌入式數(shù)據(jù)庫(kù), 是一個(gè)簡(jiǎn)單, 快速, 便捷, 面向?qū)ο? 適合java 與.NET 的數(shù)據(jù)庫(kù)。Perst 不需要專門的編譯器與預(yù)處理器, 支持ACID 事務(wù)。官方站點(diǎn):http://www.mcobject.com/perst
Perst 可以免費(fèi)自由下載，并免費(fèi)在非商業(yè)用途使用。
McObject 主要銷售技術(shù)支持，同時(shí)銷售商業(yè)license。
在 Perst得dual license下，用戶可以修改源代碼并使用于非商業(yè)用途。
Perst 是一個(gè)開源嵌入式數(shù)據(jù)庫(kù)軟件, 能夠有效的處理移動(dòng)設(shè)備上的大量數(shù)據(jù)。對(duì)于在資源受限的移動(dòng)設(shè)備( 如手機(jī), PDA 等)上存儲(chǔ)大量數(shù)據(jù)和對(duì)數(shù)據(jù)進(jìn)行頻繁的IO 操作往往要消耗很多的設(shè)備資源。由于移動(dòng)設(shè)備內(nèi)存小, 性能較差, 如果采用關(guān)系數(shù)據(jù)庫(kù)( 如SQLServer2000, Oracle) 管理數(shù)據(jù), 僅靠其有限的內(nèi)存資源是不能運(yùn)行這些數(shù)據(jù)庫(kù)管理系統(tǒng)的, 這樣就有必要采用一些特殊的數(shù)據(jù)庫(kù)系統(tǒng)。Perst 數(shù)據(jù)庫(kù)正是為這類設(shè)備研究開發(fā)的, 它們的作用是在資源受限的設(shè)備上完成大量數(shù)據(jù)的訪問(wèn)操作。其實(shí)這些設(shè)備系統(tǒng)資源主要消耗在從磁盤上讀取數(shù)據(jù)的IO 操作。如何提供一種有效的文件存儲(chǔ)策略來(lái)降低對(duì)磁盤的IO 操作是嵌入式數(shù)據(jù)庫(kù)軟件設(shè)計(jì)的主要任務(wù)。
像其他嵌入式數(shù)據(jù)庫(kù)一樣，Perst沒(méi)有管理上的代價(jià)，但不同的是Perst直接將對(duì)象以Java或者C#對(duì)象的形式進(jìn)行存儲(chǔ)。因此不需要在對(duì)象的內(nèi)部表現(xiàn)形式和Java/C#表現(xiàn)形式之間轉(zhuǎn)換。這個(gè)數(shù)據(jù)庫(kù)引擎非常精悍，只有約5000行代碼，McObject對(duì)此感到驕傲。根據(jù)訪問(wèn)模式不同，運(yùn)行時(shí)需要30K到300K的內(nèi)存
其他特性列舉如下：
● 垃圾收集
● 對(duì)掛起的引用的探測(cè)
● 自動(dòng)的schema更新（evolution）
● XML的導(dǎo)入/導(dǎo)出功能
● 支持主-從復(fù)制
● 可以過(guò)濾任何集合元素的一個(gè)SQL子集 ● 與AspectJ和JAssist AOP工具集成
Perst 支持 .Net 下的 Linq。
下面將著重介紹Perst 嵌入式數(shù)據(jù)庫(kù)的文件存儲(chǔ)策略和B+ 樹索引結(jié)構(gòu)
一、Perst 基本概念介紹
1. 頁(yè)P(yáng)age
Perst 對(duì)數(shù)據(jù)庫(kù)文件的基本操作都是以頁(yè)為單位進(jìn)行的。這些基本操作包括: 內(nèi)存分配、從數(shù)據(jù)庫(kù)文件中讀取數(shù)據(jù)、將內(nèi)存中的數(shù)據(jù)寫入文件等。Perst 一頁(yè)默認(rèn)的大小是4K。
2. 對(duì)象標(biāo)識(shí)符OID
Perst 創(chuàng)建的每個(gè)對(duì)象都是可以持久化的, 即它可以被保存在數(shù)據(jù)庫(kù)文件中。每個(gè)持久化的對(duì)象都會(huì)用對(duì)象標(biāo)識(shí)符( OID) 引用, 通過(guò)對(duì)象標(biāo)識(shí)符, 程序可以從數(shù)據(jù)庫(kù)文件中找到該對(duì)象在文件中實(shí)際存放位置。
3. Root Object
Perst 的每個(gè)數(shù)據(jù)庫(kù)文件都必須有且只能有一個(gè)稱作RootObject 的類。在這個(gè)類中定義了數(shù)據(jù)庫(kù)文件中的所有索引結(jié)構(gòu)。通過(guò)這個(gè)類, 程序可以定位到數(shù)據(jù)庫(kù)文件中的所有記錄對(duì)象。
二、數(shù)據(jù)庫(kù)Header 信息的存儲(chǔ)格式
Perst 數(shù)據(jù)庫(kù)文件開始的***頁(yè)中, 前139 個(gè)字節(jié)存放Perst 數(shù)據(jù)庫(kù)使用情況和數(shù)據(jù)庫(kù)當(dāng)前狀態(tài)等Header 信息。它在文件中的數(shù)據(jù)結(jié)構(gòu)如圖1 所示。表1 到表4 對(duì)圖1 中Header 信息中的每個(gè)數(shù)據(jù)做了詳細(xì)分析。數(shù)據(jù)意義如表所示。
數(shù)組root[ 1] 是root[ 0] 的備份, 每個(gè)元素對(duì)應(yīng)的意義相同
數(shù)據(jù)庫(kù)文件的***頁(yè)( 4K) 存放了整個(gè)數(shù)據(jù)庫(kù)文件的Header 信息。程序從數(shù)據(jù)庫(kù)文件的Header 信息中分離出數(shù)據(jù)庫(kù)文件的使用
情況和索引結(jié)構(gòu)的存儲(chǔ)位置, 這樣可以很快的定位數(shù)據(jù)庫(kù)中的記錄數(shù)據(jù)。
三、Perst 的Object Index 存儲(chǔ)結(jié)構(gòu)
Perst 專門開辟了一段空間, 稱Object Index 區(qū), 存放持久化對(duì)象在文件中的實(shí)際存儲(chǔ)位置。一般這個(gè)區(qū)在文件的第2- 10 頁(yè), 第11- 19 頁(yè)存放這個(gè)區(qū)的備份。第2- 9 頁(yè)的數(shù)據(jù)被標(biāo)識(shí)為空閑文件區(qū), 第10 頁(yè)存放實(shí)際Object Index。在Object Index 區(qū)中, 每個(gè)元素稱為Object Handle, 每Object Handle 用8 個(gè)字節(jié)表示, 存放對(duì)應(yīng)對(duì)象在文件中的實(shí)際存儲(chǔ)位置, 即對(duì)象的OID。對(duì)于4K 的頁(yè), 可以存放512 個(gè)Object Handles。Object Index 區(qū)的結(jié)構(gòu)如圖2 所示。
在圖2 的0x00012000h 位置以前都是空閑區(qū), 之后的才是真正存放Object Handle 的Object Index 區(qū)。如果Perst 數(shù)據(jù)庫(kù)文件中的持久化對(duì)象的OID 個(gè)數(shù)超過(guò)512 個(gè), Perst 會(huì)在數(shù)據(jù)庫(kù)文件的另一個(gè)區(qū)開辟更大的存儲(chǔ)空間充當(dāng)Object Index區(qū), 以存放更多的Object Handle。
四、Perst 記錄數(shù)據(jù)及類的存儲(chǔ)結(jié)構(gòu)
Perst 中記錄數(shù)據(jù)存放位置是根據(jù)當(dāng)前數(shù)據(jù)庫(kù)的使用情況來(lái)為記錄數(shù)據(jù)分配存儲(chǔ)空間。Perst 中每個(gè)記錄數(shù)據(jù)的存放格式都是統(tǒng)一的, 每個(gè)記錄數(shù)據(jù)的開頭占用8 個(gè)字節(jié)存放記錄數(shù)據(jù)的基本信息。前4 個(gè)字節(jié)存放這條記錄占用的字節(jié)個(gè)數(shù), 后4 個(gè)字節(jié)存放構(gòu)建這個(gè)記錄對(duì)象的類的OID, 通過(guò)這個(gè)OID 就可以動(dòng)態(tài)的加載該類的對(duì)象。以類Test. User 的記錄為例, 該記錄包含一個(gè)int 類型的數(shù)據(jù)和一個(gè)變量名為 name 的String 類型, 其存儲(chǔ)結(jié)構(gòu)如表5 所示
在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ù)的類信息保存在數(shù)據(jù)庫(kù)文件中, 主要目的是實(shí)現(xiàn)類對(duì)象的動(dòng)態(tài)加載。以類Test. User 為例說(shuō)明類的存儲(chǔ)結(jié)構(gòu), 它的兩個(gè)成員int 類型( Id) 和String 類型( Name) 。Perst 先保存類的成員變量Id 和Name 的信息, 然后保存類信息。圖2 是Test. User. Id 的存儲(chǔ)結(jié)構(gòu),Test.User. Name 的存儲(chǔ)結(jié)構(gòu)和表6 類似。
類Test.User 的存儲(chǔ)結(jié)構(gòu)如表7 所示:
以上是Perst 保存記錄對(duì)象類相關(guān)信息的存儲(chǔ)結(jié)構(gòu), 這樣Perst 可以動(dòng)態(tài)的加載類對(duì)象。
五、B+ 樹的存儲(chǔ)結(jié)構(gòu)
Perst 之所以能夠應(yīng)用在移動(dòng)設(shè)備上, 最主要的原因是它采用了存取方式效率高的B+ 樹結(jié)構(gòu)。Perst 定義的B+ 樹節(jié)點(diǎn)大, 使得構(gòu)建出的B+ 樹寬度大而深度小, 這樣設(shè)備進(jìn)行檢索的時(shí)候, 減少了對(duì)磁盤IO 操作的次數(shù), 從而降低了設(shè)備的資源消耗。
1. B+ 樹的節(jié)點(diǎn)及其構(gòu)成
Perst 的B+ 樹節(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。索引值的類型不同, Perst 節(jié)點(diǎn)的結(jié)構(gòu)也不同。
( 1) 索引值的類型是類
當(dāng)索引是用類創(chuàng)建的時(shí)候, 在節(jié)點(diǎn)的< key, value> 對(duì)中,索引值就是該記錄對(duì)象的OID, key 是該記錄對(duì)象的OID 或者是子節(jié)點(diǎn)頁(yè)對(duì)象的OID。以< OID1, OID3> , < OID2, OID4> 為例, 其中OID1 和OID2 是key, OID3 和OID4 是索引值, 且OID3< OID4 其結(jié)構(gòu)如下圖3 所示:圖3
( 2) 索引值的類型是數(shù)值類型( 如int, long, short 等)
當(dāng)創(chuàng)建索引的類型是數(shù)值類型時(shí), 節(jié)點(diǎn)< key, value> 中,索引值就是該數(shù)值, key 是子節(jié)點(diǎn)的OID 或者是和索引值相關(guān)的記錄對(duì)象的OID。以< OID1, 100> , < OID2, 125> 為例說(shuō)明其存儲(chǔ)結(jié)構(gòu), 其中索引值的類型是int, 存儲(chǔ)結(jié)構(gòu)如圖4所示:
對(duì)于這種類型的索引值, value 占用多大的空間, 是根據(jù)數(shù)值類型實(shí)際占用的空間進(jìn)行分配的。
( 3) 索引值的類型是字符串或字節(jié)數(shù)組類型
對(duì)于這種類型的索引結(jié)構(gòu), 在保存索引值的時(shí)候并不只是保存字符串或字節(jié)數(shù)組, 還會(huì)保存字符串的一些信息, 如字符串的字符個(gè)數(shù), 字符串在該節(jié)點(diǎn)中存放的相對(duì)位置。以< OID1, teacher > 為例, 其存儲(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è)的開頭按照其插入的順序存放( 從前向后) , 另一個(gè)則是從節(jié)點(diǎn)頁(yè)的末尾開始存放( 從后向前) 。這樣處理的好處是可以很快地從節(jié)點(diǎn)中取出< key,value> , 不用經(jīng)過(guò)很復(fù)雜的計(jì)算過(guò)程, 節(jié)省了設(shè)備資源的使用。
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)大小( 4K) 的數(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)行IO 操作。只有對(duì)象緩沖區(qū)滿時(shí), Perst 采用LRU 置換機(jī)制把內(nèi)存中的數(shù)據(jù)寫入數(shù)據(jù)庫(kù)文件中。
參考文獻(xiàn)《Perst 嵌入式數(shù)據(jù)庫(kù)存儲(chǔ)結(jié)構(gòu)分析與研究 》
原文鏈接：http://www.cnblogs.com/linzheng/archive/2011/03/06/1972282.html
【編輯推薦】
