磁盘指针是如何工作的？

Question

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

那么，在磁盘上存储指针的正确方法是什么？答案是否如简单的（文件，偏移量）一样，还是有些细节需要注意？我可以直觉地将指针转换为（文件，偏移量）对，并再次转换回来，但是否存在一些微妙之处需要注意？

编辑：我应该提到我特别关注数据库在b-tree内部如何处理此问题。虽然我很感谢基于XML的答案，但我可能把问题描述得太笼统了。

- Rob Lachlan

---

非常相似：https://dev59.com/wHRC5IYBdhLWcg3wOeSB - dmckee --- ex-moderator kitten

并不完全如此。虽然我可能没有用最理想的方式表达问题，但我特别关注文件指针如何映射到磁盘指针以及反之。尤其是数据库如何高效可靠地处理这个问题。 - Rob Lachlan

不要担心。这不是要求关闭（部分原因是因为没有真正令人满意的371371答案），但你认为“...应该接受任意嵌套结构，可能带有循环引用”是什么意思？ - dmckee --- ex-moderator kitten

可能有人真的很喜欢图论。 - Rob Lachlan

Answer 1

关于(file, offset)对的理解是正确的。

在磁盘上存储数据时需要注意一个重要的问题，即磁盘速度较慢。因此，设计了特殊的数据结构来在磁盘上存储“可搜索”的数据。使用（文件，偏移量）指针访问存储在磁盘上的二叉搜索树的节点比在内存中访问这些节点慢几个数量级。

如果访问速度很重要，您会希望将预计一起访问的内容在磁盘上靠近存储。用于此目的的两个数据结构是B-tree和B+ tree。请查找它们以了解如何使用它们。许多应用程序（例如数据库）使用复杂的缓存算法将内容缓存在内存中，以便应用程序不需要一遍又一遍地去磁盘检索数据。

如果访问速度不重要，则可以像Aiden和Darren建议的那样，将数据序列化为XML格式存储在磁盘上就足够了。

编辑：如果您需要更多关于数据库如何在磁盘上存储数据的细节，您需要学习更多关于数据库理论的知识。我建议阅读一本关于数据库的好书, 以便您了解驱动磁盘格式的要求。请注意，我主要是指关系型 数据库，但还有其他 品种的数据库，它们具有完全不同的要求和因此不同的磁盘格式。从关系型数据库开始是一个好的选择，因为它们是最常用的。

简而言之，影响关系型数据库磁盘格式的几个因素包括：

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

查询优化是数据库理论中优化磁盘访问以满足查询的重要分支。希望这能帮助您入门并朝着正确的方向前进。

- Sudhanshu

---

对于速度问题，我会建议如果你的应用程序有一个API可以通过路径访问文件中的树形结构，比如“/root/child/child”，那么你可以缓存和索引这些内容以便快速搜索和打开。 - Aiden Bell

@Sudhanshu：Sqlite数据库是一个很好的选择，可以查看代码并了解它是如何完成的，而且它是公共领域的。 :) - t0mm13b

+1 @tommieb75：谢谢。是的，SQLite是一个很好的起点。然而，重要的是要先扎实理论知识，获取高层次的视角，再通过SQLite来得到实际启发。 - Sudhanshu

关于B树，这里有更多你想知道的内容。 ;) - Sudhanshu

Answer 2

任何你喜欢的方式。你可以将它存储为每个节点上其他文件的引用，或编写一个使用块引用的文件系统驱动程序。

前提条件：

1. 您的节点包含持久化位置的引用
2. 在编写节点时，您可以知道要写入哪些位置

您可以按任何希望的方式进行操作。文件系统是使用基于磁盘的inode系统的树形结构。

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

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

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

但是这意味着如果它们只是二进制块（呃）将您的值序列化为字符。您的值可以是刚写入文件的二进制块的路径：

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

从XML封装到用C编写的文件系统，您可以查看整个树实现的各种内容。

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

树就是树。

- Aiden Bell

Answer 3

二进制或文本是首要问题

从历史上看，应用程序使用复杂的二进制格式来处理结构化数据，但当前的趋势是定义一种基于文本的表示形式，因为这样可以产生更多开发者和用户友好的文件。

XML作为持久化和交换结构化数据的便携式方式被创建出来。

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

如果文件可能会变得非常大，那么你可以像OpenOffice那样将它们保留为基于文本的标记，但直接写入到压缩（我认为OO使用的是zip）存档中。

大多数语言已经拥有了序列化库；我相信C语言中也有一些Boost库。通常有多个序列化接口，使用不同的表示形式。

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

我不会使用文件偏移作为指针，这似乎太脆弱了，自然而然地，使用已经存在的XML或YAML或其他东西是有意义的。

- DigitalRoss

Answer 4

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

您应该创建一个文本或二进制格式，以树形结构保存数据。
我建议阅读关于嵌套集模型的文章，这是另一个关于在关系数据库中存储树形数据结构的示例。

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

[元数据][数据]

[元数据] = [长度][嵌套集模型位置列表] [数据记录列表] = [左边界-＃1][右边界-＃1][左边界-＃2][右边界-＃2]... [数据] = [长度][有效载荷/数据本身]

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

- Dor

Answer 5

能否将您的内存树序列化？这听起来像是发送对象到网络上的常见Java问题。对象有指向其他东西的引用，但一旦超出程序的地址空间，这些指针地址就会改变。您能将您的树序列化为XML或JSON格式吗？

- D.C.