algorithm - 什么时候二叉树比 B 树更好？

Question

在磁盘或磁带等辅助存储设备上存储二叉树或 B 树时，二叉树是否比 B 树有优势？

我被问到一个作业“B-Trees 什么时候比二叉树更有优势？”

我想出的是 B-Tree 更好，因为它需要较少的磁盘访问（每个节点访问读取更多数据），并跳转到较少的节点以到达最终节点。但是问题的措辞方式暗示了二叉树实际上确实比B树具有优势的一点。那么，当二叉树存储在二级存储上时，是否存在比 B-Tree 更好（更高效）的点？

Answer 1

比较排序树（B-tree）和简单二叉树是不正确的，它们是不相等的。所以我想你的意思是二叉搜索树。

当数据存储在相对较慢的存储上时，B-Tree 被设计为高效。例如，当您从集群大小为 4kb 的文件系统加载或保存数据时，无论您需要多少 0..4kb 范围内的数据，读取 1 字节或 4kb 都需要相同的时间，而且确实需要时间。B-tree 牢记这一事实并使用它。因此，在所有正常/一般使用场景中，使用 B-tree 会更有效（从使用空间和性能的角度来看）。