C++永久對象存儲 （Persistent Object Storage for C++）
2024-07-21 02:09:51
供稿：網友
c++永久對象存儲 （persistent object storage for c++）
簡介 描述對象類型 從存儲器中分配和釋放對象 永久對象協議 存儲器構造函數 打開存儲器 post++ 的安裝 post++ 類庫 和 post++一起使用 stl 類 替換標準分配子 如何使用 post++ s調試 post++ 應用的細節 關于 post++ 更多的一些信息 簡介
post++ 提供了對應用對象的簡單有效的存儲. post++ 基于內存文件鏡像機制和頁面鏡像處理。post++ 消除了對永久對象訪問的開銷. 此外 post++ 支持多存儲，虛函數, 數據更新原子操作, 高效的內存分配和為指定釋放內存方式下可選的垃圾收集器. post++ 同樣可以很好的工作在多繼承和包含指針的對象上。
描述對象類型
post++ 存儲管理需要一些信息以使永久對象類型支持垃圾收集器，裝載時引用重定位和初始化虛表內函數指針。但不幸的是c++語言沒有提供運行時從類中或許這些信息的機制。為了避免使用一些特殊的工具（預處理器）或“臟哄騙”途徑（從調試信息中獲取類信息），這些信息必須由程序員來指明。這些稱為類注冊器的東西可以簡單的通過post++提供的一些宏來實現。
post++ 在從存儲器重載入對象時調用缺省構造函數來初始化對象。為了使對象句柄能夠存儲，程序員必須在類定義中包含宏 classinfo(name, field_list) . name 指明對象的名字。 field_list 描述類的的引用字段。在頭文件 classinfo.h 定義了三個宏用于描述字段:
ref(x) 描述一個字段. refs(x) 描述一個一維固定數組字段。. (例如：定長數組). vrefs(x) 描述可變一維數組字段。可變數組只能是類的最后一個成員。當你定義類的時候，你可以指定一個僅包含一個元素的數組。具體對象實例中的元素個數可以在生成時指定。
這些宏列表必須用空格分開: ref(a) ref(b) refs(c). 宏 classinfo 定義了缺省構造函數 (沒有參數的構造函數) 和類描述符. 類描述符是類的一個靜態成員名為 self_class. 這樣類 foo 的描述符可以通過 foo::self_class 訪問. 基類和成員的缺省構造函數會被編譯器自動調用，你不必擔心需要明確調用他們。但是對于序列化的類中的結構成員不要忘記在結構定義中使用 classinfo 宏。然后通過存儲器管理注冊該類使其可被訪問。這個過程由宏 register(name) 完成。類名將和對象一起放在存儲器中。在打開存儲器的時候類在存儲和應用程序之間被鏡像。存儲器中的類名和程序中的類名進行比較。如果有類沒有被程序定義或應用程序和存儲器中的類有不同的大小，程序斷言將失敗。
下面的例子闡述了這些規則:
struct branch { object* obj; int key; classinfo(branch, ref(obj));};class foo : public object { protected: foo* next; foo* prev; object* arr[10]; branch branches[8]; int x; int y; object* childs[1]; public: classinfo(foo, ref(next) ref(prev) refs(arr) vrefs(linked)); foo(int x, int y);};register(1, foo);main() { storage my_storage("foo.odb"); if (my_storage.open()) { my_root_class* root = (my_root_class*)my_storage.get_root_object();if (root == null) { root = new_in(my_storage, my_root)("some parameters for root");}... int n_childs = ...;size_t varying_size = (n_childs-1)*sizeof(object*);// we should subtract 1 from n_childs, because one element is already// present in fixed part of class. foo* fp = new (foo:self_class, my_storage, varying_size) foo(x, y);...my_storage.close(); }}
從存儲器中分配和釋放對象
post++ 為了管理存儲內存提供了特別的內存分配子. 這個分配子使用兩種不同的方法: 針對分配小對象和大對象。所有的存儲內存被劃分為頁面（頁面的大小和操作系統的頁面大小無關，目前版本的 post++ 中采用了 512 字節). 小對象是這樣一些對象，他們的大小小于或等于256字節（頁面大小/2）. 這些對象被分配成固定大小的塊鏈接起來。每一個 鏈包含相同大小的塊。分配對象的大小以8個字節為單位。為每個對象分配的包含這些塊大小為256的的鏈的數量最好不要大于14（不同的均衡頁面數）. 在每個對象之前 post++ 分配一個對象頭，包含有對象標識和對象大小。考慮到頭部剛好8個字節，并且在c++中對象的大小總大于0，大小為8的塊鏈可以舍棄。分配和釋放小對象通常情況下是非常快的: 只需要從l1隊列中進行一次插入/刪除操作. 如果鏈為空并且我們試圖分配新的對象，新頁被分配用來存儲像目前大小的對象（頁被劃分成塊添加到鏈表中）。大對象（大于256字節）所需要的空間從空閑頁隊列中分配。大對象的大小和頁邊界對齊。post++ 使用第一次喂給隨機定位算法維護空閑頁隊列（所有頁的空閑段按照地址排列并用一個特別的指針跟隨隊列的當前位置）。存儲管理的實現見文件 storage.cxx
使用顯式還是隱含的內存釋放取決于程序員。顯式內存釋放要快（特別是對小對象而言）但是隱含內存釋放（垃圾收集）更加可靠。在 post++ 中使用標志和清除垃圾收集機制。在存儲中存在一個特別的對象：根對象。垃圾收集器首先標志所有的對象可被根對象訪問（也就是可以從根對象到達，和通過引用遍歷）。這樣在第一次gc階段所有未被標志的對象被釋放。垃圾收集器可以在對象從文件載入的時候生成（如果你傳遞 do_garbage_collection 屬性給 storage::open() 方法）。也可以在程序運行期間調用 storage::do_mark_and_sweep() 方法調用垃圾收集器。但是請務必確定沒有被程序變量指向的對象不可從根對象訪問（這些對象將被gc釋放）。
基于多繼承c++類在對象中可以有非零偏移并且對象內也可能有引用。這是我們為什么要使用特別的技術訪問對象頭的原因。post++ 維護頁分配位圖，其中每一個位對應存儲器中的頁。如果一些大對象分配在幾個頁中，所有這些對象占用的頁所對應的位除了第一個外都被置為1。所有其他頁在位圖中有對應清空位。要找到對象起始地址，我們首先按頁大小排列指針值。然后 post++ 從位圖中查找對象起始頁（該頁在位圖中有零位）。然后從頁開始處包含的對象頭中取出對象大小的信息。如果大小大于頁大小的一半那我們已經找到了對象描述：它在該頁的開始處。反之我們計算頁中所使用的固定塊的大小并且把頁中指針偏移按塊大小計算出來。這種頭部定位方案被垃圾收集器使用，類 object 定義了 operator delete，和被從對象頭部解析出對象大小和類信息的方法使用。
在 post++ 中提供了特別重載的 new 方法用于存儲中的對象分配。這個方法需要創建對象的類描述，創建對象的存儲器，以及可選的對象實例可變部分的大小作為額外的參數。宏 new_in(storage, class) 提供永久對象創建“語法糖”。永久對象可以被重定義的 operator delete 刪除。
永久對象協議
在 post++ 中所有的永久對象的類必須繼承自 object.h 中定義的類 object 。這個類不含任何變量并提供了分配/釋放對象及運行時得到類信息和大小的方法。類 object 可以是多繼承中一個基類（基類的次序無所謂）。每一個永久類必須有一個供post++ 系統使用的構造函數（見 describing object class 一節）。這意味著你不能使用沒有參數的構造函數來初始化。如果你的類構造函數甚至沒有有意義的參數，你必須加一個虛構的以和宏 classinfo 創建的構造函數區別開來。
為了訪問永久存儲器中的對象程序員需要某種根對象，通過它可以使用普通的c指針訪問到每一個其他對象。post++ 存儲器提供了兩個方法用于指定和得到根對象的引用：
void set_root_object(object* obj); object* get_root_object();
當你創建新存儲時 get_root_object() 返回 null。你需要通過 set_root_object() 方法創建根對象并且在其中保存引用。下一次你打開存儲時，根對象可以通過 get_root_object() 得到。
提示：在實際應用中類通常在程序開發和維護過程中被改變。不幸的是 post++ 考慮到的簡單沒有提供自動對象轉換的工具（參見 goods 中的懶惰對象更新設計示例），所以為了避免添加新的字段到對象中，我只能建議你在對象中保留部分空間供將來使用。這對根對象來說意義尤其重大，因為它是新加入對象的優選者。你也需要避免轉換根對象的引用。如果沒有其他對象含有指向根對象的引用，那么根對象可以被簡單的改變（通過 set_root_object 方法）到新類的實例。post++ 存儲提供設置和取得村出版標識的方法。這個標識可以用于應用根據存儲器和應用的版本來更新存儲器中對象。
存儲器構造函數
你可以在應用中同時使用幾個存儲器。存儲器構造函數有一個必需的參數 - 存儲文件路徑。如果這個文件沒有擴展名，那么 post 為文件名添加一個后綴“.odb”。這個文件名也被 post++ 用于形成幾個輔助文件的名字：
文件描述使用時機后綴包含新存儲器映像的臨時文件用于非事務處理模式下保存存儲器新映像".tmp"事務記錄文件用于事務模式下保存鏡像頁面".log"保存存儲器文件備份僅用于windows-95下重命名臨時文件".sav"
存儲器構造函數的另兩個參數具有缺省值。第一個參數 max_file_size 指出存儲器文件擴展限制。如果存儲器文件大于 storage::max_file_size 那么它不會被切除但是也不可能更進一步的擴展。如果 max_file_size 大于文件大小，行為依賴于打開存儲器的模式。在事務模式下，文件在讀寫保護下被鏡像到內存中。windows-nt/95 擴展文件大小到 max_file_size。文件大小被 storage::close() 方法縮短到存儲器中最后一個對象的邊界。在 windows 中為了以讀寫模式打開存儲器需要在磁盤上至少有 storage::max_file_size 的空閑字節數即使你不準備向其中加入新對象。
存儲器構造函數的最后一個參數是 max_locked_objects，這個參數僅在事務模式下用于提供鏡像頁面的寫事務記錄文件的緩沖區。為了提供數據一致性 post++ 必須保證修改頁在刷新到磁盤前鏡像頁被保存在事務記錄文件中。post++ 使用兩個途徑中的一個：同步記錄寫 (max_locked_objects == 0) 和在內存中頁面鎖定的緩沖寫。通過內存中鎖定頁面，我們可以保證它在事務記錄緩沖錢不被交換到磁盤上。鏡像頁面在異步方式下被寫到事務記錄文件中 （包括啟用操作系統緩沖）。當鎖定頁面數超過 max_locked_pages，記錄文件緩沖被刷新到磁盤上并且所有鎖定頁面被解鎖。這個方法可以顯著的提高事務處理能力（在nt下提高了5倍）。但是不幸的是不同的操作系統使用不同的方法在內存中鎖定頁面。
windows 95 根本不支持。 在 windows nt 每個進程可以鎖定它的頁面，但是鎖定頁面的總數不可以超過進程運行配置限制。在缺省情況下進程可以鎖定超過30個的頁面。如果你指定 max_locked_pages 參數大于30，那么 post++ 將試圖擴展進程配置適合你的需求。但是從我的經驗來看30個和60個鎖定頁面之間性能的差距是非常小的。 在unix下只有超級用戶可以在內存中鎖定頁面。這是之所以文件構造函數檢查進程是否具有足夠的權限使用鎖定操作。因此如果你指定 max_locked_pages 參數大于0，那么在存儲類創建時將決定使用同步還是異步寫事務記錄文件。如果你希望使用內存鎖定機制帶來的好處（2-5 倍，根據事務類型），你需要改變你的應用的所有者為 root 并且給予 set-user-id 權限：chmod +s application.
打開存儲器
post++ 使用內存內存映射機制訪問文件中的數據。在 post++ 通過兩個不同的方法提供數據一致性。首先而且更加先進的是基于事務機制使用的鏡像頁面在出錯后來提供存儲恢復和事務回滾。在寫鏡像頁面前創建運算被使用。這個運算以如下方式執行：所有文件映射頁面被設置為只讀保護。任何對這些頁面的寫訪問將引起訪問違反異常。這個異常被一個特別的句柄捕獲，它改變頁面保護為可讀寫并放這個頁面的拷貝在事務記錄文件中（記錄文件名為原文件名和后追“.log”的組合）。所有接下來這個頁面的寫操作將不再引起頁面錯誤。存儲器方法 commit() 刷新所有的改變頁面到磁盤上并截斷記錄文件。storage::commit() 方法被 storage::close() 隱含調用。如果錯誤在 storage::commit() 操作前發生，所有的改變將通過拷貝事務記錄中改變的頁面到存儲數據文件被復原。同樣所有的改變可以通過顯式調用 storage::rollback() 方法來復原。通過指定 storage::open() 方法的 storage::use_transaction_log 屬性來選擇文件訪問事務所基于的模式.
另外一個提供數據一致性的手段基于寫拷貝機制。在這種情況下源文件沒有受到影響。任何試圖對文件鏡像頁面的改變，導致產生一個該頁面的拷貝，它從系統交換區種分配并具有讀寫許可。文件直到顯式調用 storage::flush() 方法時才更新。這個方法寫數據到臨時文件（帶后綴“.tmp”）然后重命名為原來的。因此這個操作形成文件的一個原子更新（當然假設在操作系統能保證 rename() 操作的原子數）。
注意：如果你沒有使用事務處理，storage::close() 方法不會刷數據到文件中。所以如果你在此前調用 storage::flush() 方法所有的自上次 flush 之后的改變將會丟失。
windows 95 細節：在 windows 95 中重命名到已有的文件是不行的，所以源文件首先被保存為帶后綴“.sav”的文件名。然后后綴為“.tmp”的臨時文件被重命名為原來的名字以及最后的舊的拷貝被刪除。所以如果錯誤發生在 flush() 操作中并且之后你找不到存儲文件，請不要驚慌，只需找到以后綴“.sav”結束的文件并且重命名為原來的就可以了。
提示：如果你計劃在程序執行期間保存數據我強烈建議你使用事務處理。也可以采用寫拷貝的途徑但是這樣需要多得多的消耗。同樣如果存儲非常大事務處理也通常更好，因為生成臨時的文件拷貝需要很多的磁盤空面和時間。
這里有幾個屬性供存儲器 open() 方法使用：
support_virtual_functions 如果存儲器中的對象帶有虛函數則必須設置這個屬性。如果沒有設置這個屬性，post++ 假定所有的永久對象在存儲中只包含有引用（對存儲器中其他對象的）。所以只有在數據文件映像的基地址發生改變時才需要調整引用（這個地址被存放在數據文件的第一個字中并且 post++ 通常試圖映像文件到相同的地址上來避免不必要的引用調整）。但是如果對象類包含虛函數，指向虛表的指針被放在對象內。如果你重新編譯你的應用，這個標的地址可能改變。post++ 庫比較執行對象的時間戳和這個應用產生的數據庫的時間戳進行比較。如果這個時間戳不等的話，則會校正虛表的指針。為了得到應用時間戳 post++ 必須可以定位執行文件對象。不幸的是沒有找到執行文件名的簡便的方法。在 unix 下post++ 看命令行解釋器設置的環境變量“_”的值。但如果進程不是從命令行執行的（比如通過system()）或者工作目錄被 chdir() 改變這個方法將不起作用。最簡單的方法是使用文件comptime.cxx，它必須在每次重編譯你的應用時被編譯并和存儲庫一同被鏈接。在 windows 中沒有這個問題，執行映像的名稱可以通過 win32 api 得到。在存儲器打開時 post++ 比較這個時間戳和數據文件的時間輟，如果他們不等并且指定了 support_virtual_functions 屬性那么校正所有對象（通過調用缺省構造函數）。 read_only 通過設置這個屬性程序員說明他只需要數據文件讀權限。post++ 將創建數據文件的只讀視圖并且任何改變存儲器中的對象或者分配新對象的嘗試將會導致保護違例錯。這里有一個例外：如果不能夠映像數據文件到相同的地址或者應用程序發生改變時并且指定了 support_virtual_functions ，那么對此區域的保護被臨時改變為寫拷貝并且裝載的對象被轉換。 use_transaction_log 設置這個屬性強制對所有數據文件更新使用事務。影子頁面被用來執行事務。事務在第一次修改存儲后被打開。通過 storage::commit() 或者 storage::rollback() 操作顯式的關閉。方法 storage::commit() 保存所有的改變頁面到磁盤上并且截斷事務記錄，方法 storage::rollback() 忽略此次事務中的所有改變。 no_file_mapping 缺省情況下 post++ 將映像數據文件到進程虛擬內存中。這種情況下打開數據庫的時間將大大減少，因為文件頁面將在需要時調入。但是如果數據庫大小不是特別大或者數據庫中所有數據需要立即訪問，那么把文件讀入內存優于使用虛擬內存映像因為這種情況下沒有額外的頁面溢出錯誤。標志 no_file_mapping 阻止 post++ 映像文件并根據分配的內存段讀文件。 fault_tolerant 這個標志被應用程序用于在系統或應用出錯情況下想保護數據庫的一致性。如果使用了事務 use_transaction_log 這個標志不必指定，因為一致性可以由事務機制來提供。如果沒有指定 use_transaction_log 標志并且設置了 fault_tolerant 標志， post++ 將不改變源文件而保持它的一致性。這依靠讀文件到內存中（如果沒有設置 no_file_mapping 標志）或者使用寫拷貝頁面保護。在后一種情況下試圖改變映像到文件的頁面將導致在系統交換文件中生成頁面拷貝。flush() 方法將保存內存內數據庫的映像到臨時文件中然后使用原子操作重命名到源文件。如果沒有指定 fault_tolerant 標志，post++ 在數據庫頁面上原有位置進行修改，提供最大的應用性能（因為沒有拷貝修改頁面和保存數據庫映像到臨時文件的額外開銷）。在修改頁面沒有立刻刷新到磁盤的條件下，部分改變可能因為系統錯誤而丟失（最壞的事是部分修改的頁面保存了而另外一些沒有保存 - 這樣數據庫的一致性可能被攪亂了）。 do_garbage_collection 當設置了這個屬性時 post++ 將在打開儲存器時執行垃圾收集。垃圾收集操作和指針對齊聯系在一起。使用垃圾收集往往比手工內存釋放來的安全（考慮到掛起的引用問題），但是顯式內存釋放開銷較少。post++ 中的垃圾收集相比顯式內存分配有一個更大的優勢：內存收集器對小對象使用的頁面進行優化。如果頁中沒有 已分配的小對象那么垃圾收集器將在空閑頁中包含這一頁。這不會在顯式釋放時完成，因為小對象的空閑單元被串成鏈不能簡單從這個鏈中移開（在垃圾收集器中所有的鏈被重新構造）。即使你使用顯式內存釋放，我仍建議你每隔一定時間做垃圾收集來檢查引用的一致性和沒有內存泄漏（garbage_collection 方法返回釋放對象的數目，如果你確信你已經釋放了所有的不能到達的對象，那么這個值將會是0）。考慮到垃圾收集器修改存儲中所有的對象（設置掩碼位），重連鏈中 空閑對象），在事務模式下運行gc可能是消耗時間和磁盤空間的操作，因為所有文件中的頁將被拷貝到事務記錄文件中）。
你可以通過 file::max_file_size 變量指定存儲文件的最大尺寸。如果數據文件的大小比 file::max_file_size 并且模式不是 read_only，那么虛擬空間 size_of_file - file::max_file_size 以外的字節將被保留在文件映像空間的后面。當存儲大小擴展時（因為分配新對象），這些頁面將被提交（在 windows nt）并被使用。如果文件大小大于 file::max_file_size 或者使用了 read_only 模式，那么映像區域的大小和文件大小一致。在后一種情況下不可能進行存儲擴展。在 windows 中我使用 globalmemorystatus() 方法來得到關于系統真實可分配的虛擬內存的信息并減少 file::max_file_size 為該值。不幸我發現在 unix 中沒有輕便的調用可用來達到相同的目的（getrlimit 不返回用戶進程可使用的虛擬內存的確切信息）。
對象存儲的接口在文件 storage.h 定義并且實現部分可在 storage.cxx 中看到。依賴于操作系統的映像內存文件的部分被封裝在 file 類中，其定義在 file.h 實現在 file.cxx.
post++ 的安裝
post++ 的安裝十分簡單。目前在以下系統已經過測試：digital unix, linux, solaris, windows nt 4.0, windows 95. 我希望對于大部分所有其他新 unix 方言（aix, hp-ux 10, sco...）也沒有問題。不幸的是我沒有時用過這些系統。在 windows 下我使用 microsoft visual c++ 5.0 和 borland 5.02 compilers 編譯。visual c++ 的 makefiel 是 makefile，broland c++ 的 makefile 是 makefile。
為使用 post++ 唯一你需要的東西就是函數庫（在 unix 下是 libstorage.a 在 windows 下是and storage.lib）。這個庫可以通過運行 make 命令生成。有個特別的 make.bat 用于 microsoft visual c++，它使用 makefile.mvc 作為輸入調用 nmake （如果你正在使用 borland 請編輯這個文件或者通過 make.exe -f makefile.bcc 命令調用）。
在 unix 下的安裝可以通過拷貝 post++ 庫和同文件到一些標準系統目錄下來完成。你必須為 makefile 里 install_lib_path 和 install_inc_path 變量設置恰當的值并運行 make install 命令。install_lib_path 的缺省值為 /usr/local/lib install_inc_path 的是 /usr/local/include。你可以通過明確指定路徑到 post++ 目錄來編譯和鏈接而避免拷貝文件到系統目錄中。
post++ 類庫
post++ 包括一些持久類的定義，她們可以用于你的應用也可以作為開發 post++ 類的好例子。你可以看見那些類的實現中甚至沒有 post 特定的代碼。這些類包括 array（數組）, matrix（矩陣）, string（字符串）, l2-list（l2-列表）, hash table（哈希表）, avl-tree（avl-樹）, r-tree（r-數）, text object（文本對象）. r-tree 提供了提供空間對象（包含空間對等物的對象）的快速訪問。文本對象包含了 boyer and moore 算法的修正，擴展到由 or/and 關系組合的多樣式搜索。這些類的定義可以在以下文件中發現：
描述接口實現arrays of scalars and references, matrixes and stringsarray.harray.cxxl2-list and avl-treeavltree.havltree.cxxhash table with collision chainshashtab.hhashab.cxxr-tree with quadratic method of nodes splittingrtree.hrtree.cxxt-tree (combination of avl tree and array)ttree.httree.cxxtext object with modified boyer and moore search algorithmtextobj.htextobj.cxx
在論文 "a study of index structures for main memory database management systems" 中 t.j. lehman and m.j carey 提議使用 t-trees 作為主要內存數據庫的一個存儲的有效的數據結構。t-trees 基于 avl 樹由 adelson-velsky and landis 提議。在這個分段中，我們提供 t-trees 一個概覽作為在 post++ 中的實現。
像 avl 樹一樣，t-tree的左子樹和右子樹高度差不大于1。和 avl 樹不一樣，t-tree的每一個節點排列次序保存多個關鍵值而不是單一關鍵值。一個節點里最左邊和最右邊關鍵值定義包含在這個節點內關鍵值的范圍。這樣，一個節點左子樹只包含比最左關鍵值小的關鍵值，而右子樹包含比該節點最右關鍵值大的關鍵值。節點內落在最小和最大關鍵值之間的關鍵值被稱作被該節點約束（ bounded ）。注意等于最大關鍵字或最小關鍵字的關鍵字可以根據索引是否全局唯一和查找條件認為是被約束或不被約束（e.g. “大于”（"greater-than"） 相對于 “大于等于”（"greater-than or equal-to"））。
一個既有左子樹也有右子樹的節點被歸為內部節點（internal node），僅有一個子樹的節點被歸為不完全葉（semi-leaf），一個沒有子樹的節點被歸為葉（leaf）。為了保持高占用率，每個內部節點具有一個必須包含的關鍵值的最小數目（一般為 k-2，如果 k 是可以排列在一個節點里的關鍵字的最大數目）。然而，對于葉子和不完全葉來說沒有占用率條件。
在t-tree中查找相當于直接查找。對于每一個節點，檢查看一下關鍵值是否在該節點最左和最右關鍵值之間；如果是這種情況，就是說節點里包這個關鍵值的話就返回該值（否則關鍵值不包含在樹中）。否則，如果關鍵值比最左關鍵值小，那么查找左子樹，反之搜索右子樹。重復這個過程直到發現這個關鍵值或者查找到null節點。
在t-tree中插入和刪除稍微復雜一些。對于插入操作，首先使用上面的搜索過程來查找約束插入關鍵值的節點。如果存在這樣的節點，那么節點中有空余的話關鍵值被插入到這個節點中。如果節點中沒有空余，那么關鍵值被插入到節點中，該節點的最左關鍵值被插入到該節點的左子樹中（如果左子樹為空，就分配一個新的節點把最左關鍵值插入）。如果沒有發現約束節點，那我們用n來表示搜索失敗的最后遇到的節點并按下述步驟繼續：如果n有空余，那么關鍵值就插入到n中；否則，關鍵值將被插入到一個新節點并根據關鍵值以及最左關鍵值和最右關鍵值作為n的右或左子節點/樹。
刪除關鍵值從判定包含關鍵值的節點開始，并從節點中刪除關鍵值。如果刪除關鍵值后剩下一個空的葉結點，那么節點也被刪除。如果刪除后剩下一個內部節點或者不完全葉其中包含比最小數量少的關鍵值，那么不足的將通過移動左子樹中最大的關鍵值到節點中或者合并節點和右子樹來補充。
無論插入還是刪除，分配/釋放節點可能導致樹不平衡和進行旋轉操作（rr, rl, ll, lr）。（下面的描述中子樹的高度包括了插入和刪除的影響。）在插入情況下，檢查沿著新分配節點開始的節點到根節點的節點直到
發現一個節點有兩個等高的子樹（在這種情況下不需要旋轉了），或者 發現一個節點的左子樹和右子樹有大于1的不同高度并執行包含節點的單一旋轉。
在刪除情況下，檢查沿著釋放節點的父母開始到根節點的節點直到發現一個節點它的子樹高度相差1。而且每一次遇到一個節點的子樹的高度相差大于1時，進行一次旋轉。注意釋放一個節點可能導致多次旋轉。
有幾個測試程序來測試 post++ 持久類庫中的類，他們被包含在缺省的make目標中：
programtested classestesttree.cxxavl-tree, l2-node, hash tabletesttext.cxxtext, stringtestspat.cxxrectangle, r-tree, hash tabletestperf.cxxt-tree insert, find and remove operations
和post++一起使用stl類
從 post++ 存儲器中保存和取得stl類是可能的。post++ 提供了特別的stl分配子并重載了new/delete操作符來保持stl對象。有幾個使得stl持久的模型，通過以下幾個宏來控制：
use_microsoft_stl 使用 microsoft stl 類，隨 microsoft visual c++ 一起附帶。這個類庫和c++ stl 標準不完全兼容。 use_std_allocators 使用和c++標準中一樣的分配子。分配子對象包含在stl對象中，分配子對象中的實例方法用于分配/釋放空間。所以有可能執行一個“聰明的”分配子：僅在對象包含這個分配子的情況下分配子才為 post++ 存儲器中的對象分配空間而且這個分配子也放在存儲器中。否則，對象所占空間將通過標準 malloc() 函數這個正常途徑來分配。這個選項可以和 sgi stl 庫以及 microsoft stl 庫一起使用。注意順從標準的 sgi stl 分配子使用了許多沒有廣泛實現的語言特性。特別是，他們依賴于成員模板，局部特殊化，局部分類（排序）的方法模板，typename 關鍵字，以及使用 template 關鍵字來引用依賴類型的模板成員。所以在指定這個宏定義時只有少數 c++ 編譯器可以編譯 sgi stl 庫。如果沒有設置這個宏，那么 post 提供一個含有靜態成員函數的分配子并且所有對象都從 post++ 存儲器中分配。使用這個分配子的應用一次只能打開一個post++ 存儲器。 redefine_default_allocator 有兩個途徑使得 stl 對象持久，一個途徑是引入新類型：
typedef basic_string<char, char_traits<char>, post_alloc<char> > post_string;
另外一個途徑是使所有類具有持久能力。當定義了 redefine_default_allocator 宏，任何 stl 類可以在 post++ 存儲器中分配。為了在持久存儲器中創建新對象，你必須指定存儲器作為 new 操作符額外的參數。如果存儲器被忽略，那么對象將使用標準 malloc() 函數。
post++ 到 stl 的接口不需要任何 stl 類的改變，所以你可以使用你想執行的任何 stl。但是作為一個結果，stl類不包含類型描述所以 post++ 沒有stl 對象的格式信息。所以 post++ 不能夠進行垃圾收集和引用對齊。當使用了 stl 接口時，post++ 存儲器必須始終鏡像到相同的虛擬地址上。如果你傳遞 storage::fixed 標志到 storage::open(int flags) 方法，那么如果不能鏡像存儲器到相同的內存地址 post++ 將報告錯誤并且返回 false。如果你的應用只使用了一個存儲器并且不鏡像其他對象到虛擬內存中，那么幾乎所有的操作下都可能鏡像存儲器到相同的內存地址。
post++ 到 stl 庫的接口定義在在頭文件 post_stl.h 中。這個文件必須包含在任何 stl 包含文件中。同樣宏 redefine_default_allocator，use_std_allocators 以及 use_microsoft_stl 被在 post_stl.h 之前定義。
post++ 包含使用 stl++ 類的例子 stltest.cxx。這個例子使用兩個 stl 類 - string 和 vector。從標準輸入讀進來的行被壓入到 vector 中并且程序被再次啟動所有的vector的元素被打印到標準輸出上。這個例子被包含在為 microsoft visual c++ 配置的 makefile 的缺省目標中（其使用vc 中附帶的 microsoft stl 類）。你也可以嘗試用其他版本的 stl 庫來構建這個測試但是不要忘記關于 redefine_default_allocator 和 use_std_allocators 宏。這個例子同樣可以和 sgi stlport 3.12 以及 gcc 2.8.1 一起測試。
替換標準分配子
在前面一節中我解釋了如何和 stl 庫一起使用 post++。但是仍然有很多其他你想用的c++和c庫以及應用，而且沒有提供象 stl 這種易通融的分配機制。在這種情況下唯一可能的解決方案（如果你不想改變此庫的任何源代碼的話）就是用一個 post++ 提供的來替換標準的分配機制。這樣任何動態分配對象都從 post++ 存儲器中分配（除了一個不能在這種情況下使用的存儲器）。
post++ 發行包中包含的文件 postnew.cxx 重定義了標準的 malloc，free，realloc 和 calloc 函數。當打開存儲器時，所有的對象被在存儲器中分配。否則 sbrk() 函數被用來分配對象（為這些對象分配的空間沒有回收）。可能不需要接觸這些標準c分配函數而僅需重載缺省的c++操作符 new 和 delete。當編譯 postnew.cxx 時定義 do_not_redefine_malloc 宏來這么做。從 postnew.cxx 生成的目標文件必須在標準c庫前傳遞給鏈接程序。
作為一個 post++ 這樣使用的例子可以參見 testnew.cxx 和 testqt.cxx。第一個舉例說明了標準c++數組如何持久化。第二個舉例說明了post++如何和qt類庫一起工作。
就 post++ 沒有關于存儲類的格式信息這里有一些限制在 post++ 的使用上：
包含虛函數的類不被支持（post++ 不能正確的初始化到虛函數表的指針）。 隱式內存釋放（垃圾收集器）是不可能的 - post++ 沒有關于對象內部指針位置的信息。 存儲器必須總映射到相同的虛擬地址上因為如果基地址改變了 post++ 不能調整指針。
如果所有這些限制不是你的應用所必需的，你可以使其持久化而不需要任何代碼的改動。這個方法在c和c++程序中都可以使用。
如何使用 post++
這里有幾個 post++ 類和應用的例子。其中最簡單的就是游戲“猜動物”。這個游戲的算法非常簡單并且結果看起來給人以深刻的印象（有些象人工智能）。此外這個游戲是一個非常好的例子，闡明了持久對象存儲的好處。這個游戲的源代碼在文件 guess.cxx 中。創建這個游戲包含在缺省的make目標中。執行guess來運行它。
unix specific: 當你準備和 post++ 庫鏈接你的unix應用并且持久對象中波阿含虛函數，請不要忘記重編譯 comptime.cxx 文件并包含在鏈接列表中。這個文件是必須的用于 post++ 提供可執行文件的時間戳，被放在存儲器中用來判定什么時候應用被改變并在需要的時候重新初始化對象內的虛函數表。attention! 這個文件必須在你每次重新鏈接你的應用時被重新編譯。我建議你讓編譯器為你調用鏈接程序并包含 comptime.cxx 源文件在為運行映像目標文件提供的對象文件列表中（see makefile）。
調試 post++ 應用的細節
這一節的內容對使用了事務的應用是非常有意義的。post++ 使用頁面保護機制來提供當源頁面修改時生成影子頁面，當存儲器打開或事務提交時所有文件頁面的映像是只讀保護的。所以任何試圖修改分配在這些頁面里對象的內容將導致一個訪問違例異常。這個異常被指定的 post++ 句柄處理。但是如果你使用調試器，它將首先捕獲這個異常并停止應用程序。如果你想調試你的應用你必須作一些準備：
在 unix 可以充分的告訴調試器不要捕獲 sigsegv 信號。比如對于 gdb 它可以通過命令來完成：handle sigsegv nostop noprint pass。如果 sigsegv 信號不是由存儲頁面保護違例產生，但是是程序中的一個錯誤，post++ 異常處理程序將“理解”它不是自己的異常并送出一個 sigabrt 信號到己進程中，這可以被調試器捕獲。 在 windows post++ 使用不處理異常過濾器來（ unhandled exception filter ）處理存儲器頁面保護違例。不幸的是不可能讓 microsoft debugger 忽略不處理異常。如果你準備調試你的應用，你必須把所有你的程序代碼（main 或者 winmain 函數）封裝為結構化的異常阻塞。你必須在 borland c++ 中總使用結構化異常處理，因為 unhandled exception filter 沒有在borland中被正確調用。請使用兩個宏 sen_try 和 sen_access_violation_handler() 來封裝 main（或 winmain）的函數體：
main() { sen_try { ... } sen_access_violation_handler(); return 0; }
請確定調試器對此異常的行為是“如果沒有處理就停止”而不是“總是停止”（你可以在 debug/exceptions 菜單中檢查它）。在文件 testrans.cxx 中你可以發現使用結構化異常處理的例子。
關于 post++ 的更多的一些信息
post++ 是 freeware。開發出她希望是有用的。通過她你可以做任何你想做的（在開發產品中使用 post++ 沒有任何限制）。我將很高興來幫助你使用 post++ 和得到關于 post++ 任何類型的信息（錯誤報告，建議...）。post++ 的免費軟件情形并不意味著缺少支持。我保證將努力修正任何報告的錯誤。也提供 e-mail 支持。post++ 有幾種用途：在不同期間保存信息，在文件中保存對象系統，快照， 信息系統... 但是如果你感到你需要在你的應用使用更重要的面向對象數據庫以提供并發，分布式以及事務處理，請訪問 goods (generic object oriented database system) home page。
look for new version at my homepage | e-mail me about bugs and problems
