6

假设我想将一个复杂的数据结构（比如一棵树）存储到磁盘上。在我的数据结构中连接节点的内部指针是指针，但我不能只将这些指针写入磁盘，因为当我读回数据结构时，内存位置会发生变化。

那么将指针存储在磁盘上的正确方法是什么？答案是否像（文件，偏移量）一样简单，还是我遗漏了什么？我可以直观地知道指针如何转换为 (File, offset) 对，然后又转换回来，但是有一些我应该注意的细微之处吗？

编辑：我应该提到我对数据库如何在内部执行此操作特别感兴趣，对于 b-tree。尽管我确实很欣赏基于 XML 的答案，但我可能使这个问题比我应该提出的更笼统。

4

5 回答 5

7

您对 (file, offset) 对的直觉是正确的。

在磁盘上存储数据时要注意的一件重要事情是，磁盘很慢。因此，有一些特殊的数据结构被设计用来在磁盘上存储“可搜索”的数据。使用 (file, offset) 指针访问存储在磁盘上的二叉搜索树的节点将比访问内存中的节点慢几个数量级。

如果访问速度很重要，您可能希望将预期一起访问的内容存储在磁盘上，并且更靠近一起。用于此的一些数据结构是B-tree和B+ tree。查看这些，了解如何使用它们。一些应用程序（例如数据库）使用复杂的缓存算法将内容缓存在内存中，这样应用程序就不需要一次又一次地去磁盘检索内容。

如果访问速度不重要，那么按照 Aiden 和 Darren 的建议，简单地以 XML 形式“序列化”磁盘上的数据就足够了。

编辑：如果您需要有关数据库如何在磁盘上存储数据的更多详细信息，则需要了解有关数据库理论的更多信息。我建议阅读一本关于数据库的好书，以便您了解驱动磁盘格式的要求。请注意，我在这里主要指的是关系 数据库，但还有其他 类型的数据库，它们具有完全不同的要求，因此具有不同的磁盘格式。不过，从关系数据库开始是一件好事，因为它们是最常用的。

简而言之，影响关系数据库磁盘格式的几件事是：

  1. 磁盘读/写性能
  2. 数据库恢复（在损坏的情况下）
  3. 实体之间的关系
  4. 垃圾收集
  5. 交易支持
  6. 主索引

查询优化是数据库理论的一个重要分支，用于优化磁盘访问，以满足查询。希望这将使您朝着正确的方向开始。

于 2010-01-10T18:13:07.383 回答
1

反正你喜欢。您可以将其存储为对每个节点的文件系统顶部的其他文件的引用，或者编写使用块引用的文件系统驱动程序。

提供：

  1. 您的节点包含对持久存在的位置的引用
  2. 写节点的时候可以知道要写什么位置

你可以随心所欲地做。文件系统是使用基于磁盘的 inode 系统的树。

您始终可以使用带有标头的单个文件，并使用存储为无符号整数或映射到整数的值的字节偏移量。在文件中表示某个节点的开始......然后在每个节点的末尾有一个记录结束。

您还可以使用 XML 文件来引用其他位置或单个文件和XPath/XPointers。

<Node id="someNode">
    <value>...</value>
    <children>
        <child xpath="/node[id=1]" />
        <child xpath="/node[id=29]" />

但这意味着将您的值序列化为字符，如果它们只是二进制 blob (eww) 您的值可能是刚刚写入文件的二进制块的路径，例如：

<value>/path/to/mappable.bin</value>

查看从 XML 封装到用 C 编写的文件系统的所有内容，以了解整个树实现。

这个 XML 解决方案可能很臃肿，但如果您不需要速度，它就足够简单了。只是高级方法的一个例子。树存储是一个古老的问题，在各个层面都有解决方案。

树就是树。

于 2010-01-10T18:00:49.897 回答
1

二进制或文本是第一个问题

过去，应用程序使用复杂的二进制格式来存储结构化数据，但当前的趋势是定义基于文本的表示，因为这会产生对开发人员和用户更友好的文件。

XML 被创建为一种可移植的方式来持久化和交换结构化数据。

如果是我，我会使用类似 XML 但不那么笨重的 YAML。

如果文件可能变得非常大，那么您可以执行 OpenOffice 所做的并将它们保留为基于文本的标记，但直接写入压缩（我认为它是面向 OO 的 zip）存档。

大多数语言已经有序列化库；我确信有一些 C 的 Boost 库。通常有多个使用不同表示的序列化接口。

如果您使用库、XML 或 YAML，链接将隐含在树结构表示中。如果您的数据具有更通用的图表，那么无论您使用文本还是二进制，您都可能需要对链接进行规范化。这是你提到的指针问题。解决它的一种方法是保留在读取或写入文件时使用的临时映射。也就是说，您只需命名每个链接目标，例如 A1、A2、A3 ...，然后将其用作目标处的标记和源处的链接名称（想想 href=）。

我不会使用文件偏移量作为指针，它看起来太脆弱了，使用 XML 或 YAML 或其他已经存在的东西自然是有意义的。

于 2010-01-10T18:12:45.333 回答
1

确切地说，存储指针值是没有意义的。

您应该创建一个文本或二进制格式，将数据保存在树结构中。
我建议阅读有关Nested Set Model的内容，这是在关系数据库中存储树数据结构的另一个示例。

例如，这是您的数据的存储方式：

[meta-data][data]



[meta-data] = [ length ][ list-of-Nested-Set-Model-Locations ]
    [ list-of-data-records ] = [ lft-#1 ][ rgt-#1 ][ lft-#2 ][ rgt-#2 ] ...
[data] = [length][ payload / data-itself ]

这只是一个示例，使用 JSON（推荐）或 XML 可能会更好、更容易。

于 2010-01-10T18:20:11.677 回答
0

是否有可能对您的内存树进行序列化？这听起来像是通过网络发送对象的常见 java 问题。对象具有对其他事物的引用，但是一旦超出程序的地址空间，这些指针地址就会改变。您能否将您的树序列化为 XML 或 JSON 格式？

于 2010-01-10T18:06:50.953 回答