data-structures - B 树减少了多少磁盘访问？

Question

我刚刚阅读了 B 树数据结构，我有一些问题。我心中有一个疑问，在任何博客中都没有解释(也许它太明显了，我错过了)。

B 树应该通过降低树的高度来减少磁盘访问。那么，如果减少磁盘访问次数是主要关注点，那么它有多大区别呢？假设我只使用二叉树，那么我的节点比 n 元 B 树的节点需要更少的空间。所以我可以在一个页面中容纳更多的节点，就像我可以处理胖 B 树节点一样。它究竟如何影响磁盘访问？我们只是在谈论最坏的情况吗？

Answer 1

您必须了解 B 树通常用于具有分页数据访问权限的系统中。这是最常见的数据库系统。页面本质上是一块内存，您必须一次读取(和写入)。如果不阅读整个页面，您将无法阅读页面的个别部分。

重要的是:将页面从磁盘读取到内存中是很昂贵的；比对已经在内存中的页面做任何事情都要昂贵。因此，您希望尽量减少必须阅读的页数。

为此，B 树比二叉树有几个好处——考虑到它们是专门为此目的而设计的，这并不奇怪。

这些好处之一是降低了高度。如果你使用普通的二叉树，你可以在其中快速搜索。但是在这样做时，您会深入到树中。一棵有 100 万个元素的树已经有 20 的深度。所以，假设它是平衡的，你需要走下 20 个节点。与 B 树相比，高度要低很多。 child 数量为 10(顺便说一句，这是非常低的)我们已经将高度降低到大约 6。因此我们需要进行更少的比较，并且可能加载更少的页面。通常，B 树的顺序(即每个节点具有的子节点数)是以某种方式选择的，因此单个节点会填充一个完整的页面。现在这听起来可能很愚蠢，因为您需要在该节点的键中进行搜索，但它大大减少了深度，因此您必须阅读的页面数量。

另一个好处是 B 树是平衡的。这确保了所有节点在任何时候都被大致相同数量的子节点填充。通常，这大约是其容量的 75%。由于节点填满了一个完整的页面，这意味着每个包含节点的页面都被填满了它的容量。这非常好，因为它优化了节点使用的空间并避免了不包含信息的页面中的漏洞(这对于二叉树来说是一个大问题，因为它们在设计上不平衡)。另一个非常重要的影响是，这也确保了查找元素的操作数量(以及运行时间)是一致的。因此，您在所有情况下都有非常可预测的性能。对于数据库，这通常比性能可能不同的更好的最佳或平均情况重要得多。

还有其他好处，比如叶子不仅在同一层，而且在物理上彼此靠近，因为这可以提高迭代元素时的寻道时间。

基本上，B 树针对分页数据访问进行了优化，这使得它们非常特殊并且针对这些目的进行了微调，使它们能够胜过经典的二叉树(在许多其他应用程序中更简单、更高效)。