c++ - 如何在磁盘上存储一棵树并使添加/删除/交换操作变得容易

Question

好吧，这个问题需要你阅读一下。我会尽量保持简短。

我有一棵树(不是二叉树，只是一棵树)，每个节点都有相关数据(二进制数据，我不知道它们是什么，也不知道它们有多长)

树的每个节点还有一个与它在树中的显示方式无关的索引，为了简短起见，它可能是这样的:

索引号表示用户希望导航树的顺序并且不能重复。

我需要将这个结构存储在磁盘上的一个文件中。

我的问题是:如何设计一种软盘存储格式，使树的加载和操作尽可能容易。

事实上应该允许用户

• 为一个元素创建一个子 block (这应该很简单，向文件添加数据就足够了，注意避免重复索引)
• 删除一个子节点(我应该提示用户“你是否也想删除这个节点的所有子节点？还是我应该将它的子节点添加到它的父节点？”)。棘手的是删除一个节点也可以释放一个索引，我不能让用户在添加另一个节点时再次使用该索引(或者他设置的顺序可能会被弄乱)，我需要更新整棵树!
• 将一个索引与另一个索引交换

我正在使用 C++ 和 Qt，到现在为止我想到了很多具有很多字段的结构，就像这样

struct dataToBeStoredInTheFile
{
    long data_size;
    byte *data; //... the data here

    int index;
    int number_of_children;
    int *children_indices; // ... array of integers
}

这有利于用各自的索引标识每个节点，但是在两个节点之间交换索引或删除一个节点并更新每个其他节点的索引时它会非常慢，因为您必须遍历所有节点及其所有“children_indices”数组。

使用“哈希”之类的东西来标识每个节点是否会更灵活？我应该使用两个索引，一个用于树中的位置，一个用于用户的索引吗？如果您对存储数据有更好的想法，欢迎您

Answer 1

我建议使用类似 boost.serialization 的东西，那么您就不必担心保存到磁盘时的实际格式，而可以专注于有效的内存解决方案。

编辑: 重新阅读您的问题，我发现您正在使用 Qt，在这种情况下，它应该有自己的序列化框架供您使用。