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