B-Tree保存在File中不是就失去了它的好处了吗？

Question

我正在阅读有关 B 树的内容，很有趣的是，它是专门为存储在辅助内存中而构建的。但我对以下几点感到有点困惑：

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

Answer 1

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

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

• B 树中的每个节点都是一个数据块（字节）。块具有固定的大小。
• 如果使用文件，则按块在文件中的位置寻址；如果 B 树块直接映射到磁盘扇区，则按块地址寻址。
• “指向子节点的指针”只是一个数字，即节点的块地址。
• 块很大。通常足够大，可容纳 1000 名或更多儿童。这是因为读取一个块的成本很高，但成本与块的大小关系不大。通过保持块足够大，以便整个树中只有 3 或 4 个级别，我们可以最大限度地减少访问任何特定项目所需的读取或写入次数。
• 通常使用缓存，以便大多数访问只需要触及磁盘上树的最低级别。

因此，要在 B 树中查找项目，您需要读取根块（它可能会从缓存中出来），浏览它以找到适当的子块并读取它（同样可能会从缓存中出来），也许会这样做再次，最后读取适当的叶块并提取数据。