1

我正在阅读Cormen 等人的算法简介中的B-Tree主题。人。而且我在实际程序中实现伪代码的磁盘操作时遇到了困难。这可能是这种情况，因为我在这里不清楚对对象的描述。任何人都可以指导我如何进行。

以下为正文节选，介绍发展情况：

我们在伪代码中对磁盘操作进行建模，如下所示。设x是指向对象的指针。如果对象当前在计算机的主内存中，那么我们可以像往常一样引用对象的字段：key[x]例如。但是，如果 引用的对象x驻留在磁盘上，那么我们必须先执行将Disk-Read (x)对象读x入主存的操作，然后才能引用其字段。（我们假设如果x已经在主内存中，则Disk-Read (x)不需要磁盘访问；它是“无操作”。）类似地，该操作Disk-Write(x)用于保存对 object 字段所做的任何更改x。处理对象的典型模式如下：

    x <- a pointer to some object 
    Disk-Read (x) 
    operations that access and/or modify the fields of x 
    Disk-Write(x) // Omitted if no fields of x were changed. 
    other operations that access but do not modify fields of x

所以很明显，如果x要在磁盘上存储一个对象，除非我们将它带入主存，否则我们无法引用它，但是我们如何x首先指向磁盘中的对象，这个是什么，我在实施时遇到了问题。

我无法理解如何在实际程序中实现这些磁盘操作。

创建一个空的 B 树

要构建 B 树T，我们首先使用B-Tree-Create创建一个空的根节点。该过程使用一个辅助过程Allocate-Node，它及时分配一个磁盘页面作为新节点使用O(1)。（我知道在堆上分配，但这里他们是在谈论直接在磁盘上分配吗？此外，如果x持有对分配在磁盘上的对象的引用，那么如果不将其带入主内存，我们就不可能按照前面的摘录处理它的属性）。我们可以假设由创建的节点Allocate-Node不需要Disk-Read，因为磁盘上还没有存储该节点的有用信息。（如果不看，怎么设置属性x？）

  В-Tree-Create (T): 
  1 x <- Allocate-Node() 
  2 leaf[x] <- true 
  3 n[x] <- 0 
  4 Disk-Write (x) 
  5 root[T] <- x

我知道如何在堆上分配并说使用fwrite()inC programming language将其写入磁盘，但是如何将链接合并到磁盘中？应该ftell()用于获取文件中对象的开始并相应地进行链接？

我不太明白如何优雅地将对象写入磁盘，保持链接结构。（ Aaron M. Tenenbaum 等人撰写的使用 C 和 C++ 的文本数据结构。仅以图形方式处理该主题，没有核心实现。而且我还没有学习正式的 DBMS 课程）

请指导我，如果可能的话。谢谢..

[注意我和这个问题一样，但建议的答案包含大量代码，没有任何文档或生动的评论，谷歌搜索这些东西会产生在主内存中维护的 B-tree（这不是它们的设计目的）。任何人都可以用一种更简单的编程语言（例如碎片整理等] [此外这里有一个关于该主题的视频讲座，但可惜没有实现的细节]C

4

0 回答 0