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