5

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

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

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

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

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

但是我如何在磁盘上做指针呢？它像文件名吗？

4

2 回答 2

6

磁盘指针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棵树的 将是被索引的列的内容。

于 2013-10-02T09:33:39.690 回答
5

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

于 2013-10-02T08:18:33.860 回答