代码之家 › 专栏 › 技术社区 › Rob Lachlan

磁盘指针如何工作?

swizzling pointers language-agnostic c

6

Rob Lachlan · 技术社区 · 15 年前

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

那么,在磁盘上存储指针的正确方法是什么呢?答案是否简单如(文件、偏移量),或者是否有我遗漏的内容?我可以凭直觉知道指针如何转换成(文件,偏移)对,然后再转换回来,但是是否有一些微妙的地方需要注意?

编辑: 我应该提到,我特别感兴趣的是对于B树,数据库如何在内部完成这项工作。虽然我很欣赏基于XML的答案,但我可能把这个问题做得比我应该做的更一般。

5 回复 | 直到 15 年前

1

4

Sudhanshu 15 年前

你对(文件,偏移)对的直觉是正确的。

在磁盘上存储数据时要注意的一个重要问题是,磁盘速度慢。因此,有一些特殊的数据结构被设计成在磁盘上存储“可搜索”的数据。使用(文件、偏移量)指针访问存储在磁盘上的二进制搜索树的节点比在内存中访问节点慢几个数量级。

如果访问速度很重要,那么您将希望在磁盘上存储希望一起访问的内容,并将其更紧密地存储在一起。用于此目的的两个数据结构是 B-tree 和 B+ tree . 看看这些,看看如何使用它们。有很多复杂的 caching algorithms 由数据库等多个应用程序使用,在内存中缓存内容,这样应用程序就不需要去磁盘上一次又一次地检索内容。

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

编辑:如果您需要更多关于数据库如何在磁盘上存储数据的详细信息,您需要了解更多关于数据库理论的信息。我建议你读一读 good book 在数据库上,以便您了解驱动磁盘格式的需求。注意,我主要指的是 relational databases 在这里,但有 other breeds 属于 databases ,完全 different requirements 因此不同的磁盘格式。不过,从关系数据库开始是一件好事,因为它们是最常用的。

简而言之,影响关系数据库磁盘格式的一些因素包括:

磁盘读/写性能
Database recovery (如果是腐败)
Relations between entities
垃圾收集
Transactional support
Primary index

Query optimization 是数据库理论中优化磁盘访问、满足查询的重要分支。希望这能让你 started 在 right direction .

2

1

Aiden Bell 15 年前

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

提供:

您的节点包含对持久存在的位置的引用
在编写节点时,您可以知道要编写的位置

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

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

也可以将XML文件用于对其他位置或单个文件的引用,以及 XPath/XPoNeX .

<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解决方案可能会膨胀 但如果你不需要速度就足够简单了。只是一个高级方法的例子。树存储是一个由来已久的问题,有各级解决方案。

树就是树。

3

1

Dor 15 年前

准确地说,存储指针值将毫无意义。

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

例如,以下是存储数据的方式:

[meta-data][data]

[元数据]=[长度][嵌套集模型位置列表] [数据记录列表]=[LFT-1][RGT-1][LFT-2][RGT-2]… [数据]=[长度][有效载荷/数据本身]

这只是一个示例,使用JSON(推荐)或XML可能会更容易。

4

1

DigitalRoss 15 年前

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

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

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

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

如果文件可能变得非常大,那么您可以像OpenOffice那样做,并将它们作为基于文本的标记保存,但直接写入压缩(我认为它是用于OO的zip)存档。

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

如果使用库、XML或yaml,则链接将隐式地出现在树结构表示中。如果您的数据有一个更通用的图表,那么无论使用文本还是二进制,都可能需要规范化链接。这是您提到的指针问题。解决此问题的一种方法是保留在读取或写入文件时使用的临时映射。也就是说,你只需说出每个链接目标,比如,a1,a2,a3…然后在目的地将其用作标记,在源位置将其用作链接名(请考虑href=)。

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

5

0

D.C. 15 年前

可以烧焦你的记忆树吗?这听起来像是在网络上发送对象的常见Java问题。对象具有对其他事物的引用,但一旦超出程序的地址空间,这些指针地址就会改变。可以将树序列化为XML或JSON形式吗?