algorithm - 用于磁盘存储的 B-Tree

Question

为什么 B 树是磁盘存储的首选结构。
什么质量使它比二叉树更适合用于二级存储。
这种特定的“质量”是算法本身的一个特征；还是它的实现方式？
任何参考或指针将不胜感激。

Answer 1

磁盘寻道是昂贵的。B-Tree 结构是专门为尽可能避免磁盘寻道而设计的。因此，B-Tree 将比二叉树更多的键/指针打包到单个节点中。此属性使树非常平坦。通常大多数 B 树只有 3 或 4 级深度，并且可以轻松缓存根节点。这只需要 2-3 次寻求在树中找到任何东西。叶子也以这种方式“打包”，因此迭代树（例如全扫描或范围扫描）非常有效，因为您每个块读取数百/数千数据行（搜索）。

在相同容量的二叉树中，您将有数十个级别，并且顺序访问每个值都需要至少一次查找。