B树中的指针

Question

我阅读了 B 树并了解它们的输入、删除方法。我读了这样的介绍：

当我们在磁盘上构建结构时，我们必须处理访问和传输时间的某些现实：

1. 对磁盘的随机访问通常需要大约 10-20 毫秒的访问时间来定位磁头并等待数据出现在它下面。
2. 一旦磁头位置正确，数据传输的速率可以超过 100 万字节/秒。
3. 然后观察不同大小块的总传输时间的行为（假设相当快的 10 毫秒访问时间和 1 兆字节/秒的传输速率）

因此，B 树数据结构是为从磁盘提供服务而设计的（这就是它们非常适合数据库的原因）。但是当我尝试实现它时，我遇到了这个问题。

正常的 B 树图显示了指向子节点的指针，这些子节点然后下降到叶子。

但是我如何在磁盘上制作指针呢？它像一个文件名吗？

Answer 1

B 树中的“指针”只是您可以查找的文件中的一个偏移量。或者，如果您要拥有固定的块大小，则它可能是一个块号，您可以在查找之前乘以块大小。

Answer 2

磁盘上的指针offsets来自文件的开头。

如果你key指向地址n那么这意味着

1. 打开数据文件
2. 读取n个字节但丢弃它们（或简单地跳过它们。这称为寻找。参见下文）
3. 开始阅读您感兴趣的数据。

现在，作为优化，

1. 数据文件可能已经打开，比如你的程序启动时；当然可以部分缓存在内存中。
2. 您可以专门指示框架转到文件中的特定位置，而不是读取和丢弃字节。大多数语言都有这个功能。所有操作系统都可以。这叫做寻求。你调用一个像file.seek(1024). 要执行跳转，操作系统必须知道您要查找的数据位于磁盘中的哪个点。这涉及更多的查找，一些磁盘移动，但这一切都由操作系统完成。
3. 您可以开始读取数据，但要知道何时停止，要么使用固定宽度的记录，要么将记录长度放在记录的前 4 个字节中。这使得headers元数据会随着复杂性而增长。

有趣的是，与每个相关联的指针key指向left并且right nodes没有数据的地方。所以，在教科书的例子中

struct node {
    int key;                      //this generally is the primary key of the table
    node left;
    node right;

    long offsetOfDataInDataFile;  // <----------- we need to add this line.
}

这种方式首先你node在tree. 然后您找到key. 在那里你得到offset了实际数据。您转到数据文件中的位置并读取内容。

如果您的表有多个索引，那么或表中的每个索引，都需要维护一个这样的树。在key该树将被索引的列的内容。