B-树用于磁盘存储

Question

B-树用于磁盘存储

7

为什么B-树是磁盘存储的首选结构？
何种质量使其比二叉树更适合于辅助存储？
该特定“质量”是算法本身的特性还是它实现的方式？
如有参考或指针，将不胜感激。

- IUnknown

(1) 二叉树是我们用作内存数据结构的，而B-Tree则用于存储结构和访问结构。 (2) 在二叉树（或内存）数据结构中，我们希望最小化操作以提高效率，而在B-Tree中，我们希望最小化块访问次数。 (3) 在二叉树中，我们总是有两个选择，即左或右，因此搜索关键字的时间复杂度为log2(n)，而在B-Tree中，我们有m个选择，因此搜索关键字的时间复杂度为logm(n)，更加高效。 - Grijesh Chauhan

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Piotr Kołaczkowski · Accepted Answer

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

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