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
本文作者: