c++ - 主内存 B+ 树的持久化策略

Question

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

1. 将节点对象保存在 Pre-order 中，并为空子指针写入 NULLS。
2. 为节点提供 IDS 并在写入时保存节点 ID 而不是指针 到磁盘，然后在重新实例化期间使用 ID 解析指针。
3. 保存时使用文件偏移值(物理内存中的地址)而不是子节点的主内存地址。这可能意味着我必须从 leaf-up 保存。

我还查看了几个序列化库。 Google ProtocolBuffers 和 Boost 序列化。

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

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 的数据中，而不是保存链接。并为每个 NodeHead 实例提供一个 ID，并使用它来维护“子”关系。如果可以用更好的方式做到这一点，我希望得到一些建议。

Answer 1

数据(键、值)对是单独保存在磁盘上，还是需要将它们与索引一起持久化？您是将数据本身保存在内存中，还是仅将索引驻留在内存中，而数据在磁盘上？如果整个数据集都驻留在内存中，则根本不要保留树结构。只需保存(键，值)对的有序列表并在加载时重建树。我从未使用过该库，但任何合理的 B 树实现都应该能够非常有效地从预先排序的记录流构建内存中 B 树。