磁盘指针如何工作？

Question

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

那么将指针存储在磁盘上的正确方法是什么？答案就像(文件,偏移)一样简单,还是有些东西我不知道？我可以直观地指出如何将指针转换为(文件,偏移)对,然后再返回,但是我应该注意一些细微之处吗？

编辑:我应该提一下,我特别感兴趣的是数据库如何在内部执行此操作,对于b树.虽然我很欣赏基于XML的答案,但我可能会提出比我应该更普遍的问题.

Answer 1

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

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

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

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

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

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

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

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