使用B+树创建索引文件

Question

我遇到了一个有趣的挑战，其中 B+ 树是数据文件的索引。该索引必须保存在索引文件中，稍后我们必须将索引从该索引文件加载到内存中。

这是我的B+树结构，来自http://www.amittai.com/prose/bpt.c

typedef struct node 
{
    void ** pointers;
    int * keys;
    struct node * parent;
    bool is_leaf;
    int num_keys;
} node; 

正如你所看到的，树的代码非常简洁并且工作正常，所以现在我有一个作为索引的 b+ 树。但我不能简单地将树中的每个节点写入文件中......写入其中的指针在新执行中不起作用。我如何开始使用 B+ 树创建索引文件？提醒一下，创建索引后，必须使用索引文件将索引加载回内存。

Answer 1

将指针转换为 id(应该是节点的内存地址和唯一 id 之间的一对一对应关系)。然后以后缀顺序或写入 id 而不是指针的方式遍历树。

要重建树，您只需从文件中读取数据，并且您看到的每个新 id 都会为其分配一些内存。 (如果您的 ID 从零开始连续，那么您可以使用固定大小的数组作为哈希表来快速轻松地完成此操作)。

如果您想真正快速地加载索引，可能有很多更聪明的方法可以做到这一点。