1

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

我有一棵树（不是二叉树，只是一棵树），其中包含与每个节点关联的数据（二进制数据，我不知道它们是什么，也不知道它们有多长）

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

在此处输入图像描述

索引号代表用户想要导航树的顺序，不能重复。

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

我的问题是：如何设计一种灵活的磁盘存储格式，使加载和在树上工作尽可能容易。

实际上应该允许用户

  • 为元素创建一个子块（这应该很容易，将数据添加到文件中就足够了，注意避免重复索引）
  • 删除一个子节点（我应该提示用户“你想删除这个节点的所有子节点吗？还是应该将它的子节点添加到它的父节点？”）。关于这一点的棘手部分是删除节点也可以释放索引，并且我不能让用户在添加另一个节点时再次使用该索引（或者他设置的顺序可能搞砸了），我需要更新整棵树！
  • 用另一个索引交换索引

我正在使用 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”数组。

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

4

3 回答 3

2

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

编辑：重新阅读你的问题，我看到你正在使用 Qt，在这种情况下，它应该有它自己的序列化框架，你可以使用它。

于 2012-07-24T10:48:05.680 回答
1

  1. 如果它不必是单个文件，您可以使用文件/目录结构来表示您的树，其中每个节点对应于一个文件（每个内部节点都有一个目录）。也许不是最有效的，但非常容易做到。

  2. 同样，如果您对文件数量有一定的灵活性（但没有上面那么多），您可以为树结构创建一个文件（这样每个节点的大小都是固定的，从而简化了其操作）和一个单独的文件用于存储节点内容。为了加快处理“内容文件”的速度，您可以像垃圾收集系统一样对待它：只需在最后不断添加新/更新的节点，将旧节点标记为不再使用，并定期清除内容。

  3. 更好的是，遵循@JoachimPileborg 的建议 :)

于 2012-07-24T10:49:53.010 回答
1

我认为您不应该使用用户指定的索引来识别节点，因为这与您存储树的方式没有直接关系，并且您没有通过索引访问节点的有效方法。您应该为每个节点保留两个索引——一个是用户指定的，另一个是依赖于实现的；或维护一个数组，将用户指定的索引映射到您用于实现的索引。

此外，如果您使用不同的结构来存储树可能会更好。对于每个节点，存储以下内容：

  • 父级索引
  • 最左边儿子的索引
  • 左兄弟的索引
  • 右兄弟的索引

通过这种方式添加一个节点并交换两个节点可以通过一些简单的指针操作来完成（我不是指显式指针 - 无论如何索引有点像指针）。删除节点可能仍然很慢，因为您必须访问所有子节点。

作为奖励，如果您使用这种结构，每个节点都有固定的大小（与您提出的链表不同）。这意味着您可以通过在文件中查找来直接访问节点。

您还应该维护用户可用于新节点的最小索引 - 例如，即使最大索引为 5 并且已被删除，您仍将 6 作为下一个空闲索引，因此 5 不能重复使用。

于 2012-07-24T11:45:04.827 回答