将B-Tree保存在File中时，B-Tree丢失的好处是什么？

Question

我正在阅读有关B-Tree的内容，知道它专门用于存储在二级存储器中，这很有趣。但我很少有点困惑：

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

Answer 1

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

磁盘上的B-Tree是一个由数据块组成的基于磁盘的数据结构，这些块一次只能读写一个块。典型：

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

因此，要在B树中查找项目，您将读取根块（它可能会从缓存中出来），查看它以找到相应的子块并读取它（也可能是缓存之外），也许这样做再次，最后读取相应的叶块并提取数据。