algorithm - B-Tree 保存在 File 中的好处是不是就没了？

Question

我正在阅读有关 B-Tree 的文章，很有趣的是知道它是专门为存储在辅助内存中而构建的。但我对以下几点感到困惑:

1. 如果我们将 B-Tree 保存在辅助内存中(通过 Java 中的序列化)，B-Tree 的优势是不是会丢失？因为一旦节点被序列化，我们将无法访问对子节点的引用(因为我们进入主内存)。所以这意味着，我们将不得不一个一个地读取所有节点(因为没有可用于子节点的引用)。如果我们必须读取所有节点，那么树的优势是什么？我的意思是，在那种情况下，我们不会在树上使用二进制搜索。有什么想法吗 ？

Answer 1

当在磁盘上使用 B-Tree 时，它​​不会从文件中读取、反序列化、修改和序列化，然后写回。

磁盘上的 B 树是一种基于磁盘的数据结构，由数据 block 组成，这些 block 一次读取和写入一个 block 。通常:

• B 树中的每个节点都是一个数据 block (字节)。 block 具有固定大小。
• block 通过它们在文件中的位置寻址(如果使用文件)，或者如果 B-Tree block 直接映射到磁盘扇区则通过它们的扇区地址寻址。
• “指向子节点的指针”只是一个数字，即节点的 block 地址。
• block 很大。通常大到可以容纳 1000 个或更多的 child 。那是因为读取一个 block 是昂贵的，但成本并不取决于 block 的大小。通过保持 block 足够大以便整个树中只有 3 或 4 层，我们可以最大限度地减少访问任何特定项目所需的读取或写入次数。
• 通常使用缓存，以便大多数访问只需要触及磁盘上树的最低级别。

所以要在 B 树中找到一个项目，您需要读取根 block (它可能会从缓存中取出)，遍历它以找到合适的子 block 并读取它(同样可能会从缓存中取出)，也许再做一次，最后读取适当的叶 block 并提取数据。