主存B +树的持久性策略

我正在尝试为使用C++的键值对开发主存索引。我需要确保索引在崩溃后可恢复。我正在使用我发现的CSB +树实现（BSD许可证）here 我面临的主要挑战是在重新实例化节点后维护父子关系数据。我已经搜索了各种策略来保存和恢复到/从磁盘“树结构”。其中一些是：主存B +树的持久性策略

将节点对象保存在预订中，并为空子指针写入NULLS。
在将写入磁盘时，将IDS赋予节点并保存节点的ID而不是指针，然后在使用ID重新实例化期间解析指针。
保存时使用文件偏移量值（物理内存中的地址）而不是子节点的主内存地址。这可能意味着我不得不从叶子开始保存。

我也看了几个序列化库。 Google ProtocolBuffers和Boost Serialization。

现在实现中的“节点”有许多指针变量。其中一些是指向其他节点的指针，而另一些则是指向“键值”的指针。下面的代码是简化版本以保留本质。

struct NodeHead 
{ 
    NodeHead *null; // null indicates internal node 
    char *children; // ptr to children 
    NodeEntry entries[1]; // entry array 
} 

struct NodeEntry 
{ 
    uint16_t offset; // offset to NodeHead of the key in byte 
    uint8_t next; // index of the next entry; 0xff means null 
    uint8_t num; // [0]: number of entries in use 
};

我想直接写入条目值到数据的nodehead而不是节约了link.And给每个NodeHead实例ID和用它来维持“孩子们”的关系。如果这可以以更好的方式完成，我希望得到一些建议。

来源

2011-03-24 AjP

如果发生崩溃，你说的是堕胎或任何硬性中断，你将无法序列化任何东西...所以你的策略是什么使你的数据在你崩溃之前持久化？在每次修改时序列化所有内容不太可行。 – 2011-03-25 07:46:36

我不会在每次修改时序列化。我会定期检查一下。在检查点期间，我更愿意将索引的“快照”（以及叶子中的数据）保存到磁盘。所以，启动后我可以恢复索引结构。在2个检查点之间，我将保留所有事务的日志，以便在恢复到最新的已提交操作后更新索引快照。关于将快照保存到磁盘，我发现一个类似的问题，问http://stackoverflow.com/questions/872070/saving-btrees-to-a-disk-file-and-read-it。我一直在坚持如何继续 – AjP 2011-03-25 18:12:31

你也可以做选项3，让自己拥有索引引用（没有指针只是引用页面偏移量 - 在页面中分配索引），然后当你快速索引索引时，你可以检查索引'脏位“，并检查索引的该页是否已更新，并将整个脏索引页复制到磁盘。无需走树，只需索引页面的索引。 [我提出了类似于CUDA内存复制问题的东西 - 我必须是一个小技巧小马:)] – PAntoine 2011-04-05 18:04:24

数据（键，值）对是分开保存在磁盘上，还是需要将它们与索引一起保存？数据存储在内存中，还是只保存索引内存，而数据在磁盘上？如果整个数据集都是驻留内存的，那么不要坚持树结构。只需保存（键，值）对的有序列表并重新加载树。我从来没有使用过这个库，但任何合理的B树实现应该能够非常有效地从预先分类的记录流中构建一个内存中的B树。

来源

2011-04-18 04:59:17

主存B +树的持久性策略

回答

相关问题