B 树减少了多少磁盘访问？
How much do B-trees reduce disk accesses?
刚刚看了B树数据结构，有一些疑问。我有一个疑问，在任何博客中都没有解释（也许它太明显了，我错过了）。
B 树应该通过降低树的高度来减少磁盘访问。那么，如果减少磁盘访问次数是主要关注点，那么它有多大不同呢？假设我只使用二叉树，那么我的节点需要的 space 比 n 元 B 树的节点少。所以我可以在页面中容纳更多节点，就像我可以处理胖 B 树节点一样。它究竟如何影响磁盘访问？我们只是在谈论最坏的情况吗？
B代表balanced，表示在B-tree中，左右两边的节点大小（子节点个数）大致相同。
考虑这个例子：
如下将数字添加到二叉树：如果新数字大于当前节点，则以相同的方式将其添加到右侧，否则添加到左侧（子）树。
A) 想一想如果将 1 到 100 的数字按升序相加会发生什么。
B) 现在想象一下如果像这样添加它们会发生什么 50, 25, 75, 12, 37, 62, 87, ...（从区间的中间开始，然后递归地添加中点新间隔）
B 树添加新节点的方式即使您像 A) 中那样按顺序添加它们，生成的树也类似于 B) 中生成的树
对于磁盘访问，想象一下必须在 A) 和 B) 的树中查找节点 100 并比较您必须处理多少节点（磁盘访问）才能到达它。
编辑
正如评论中指出的那样，上述 B 树的介绍并不完全正确。
B树更像是一棵排序的（节点）列表树，也就是说，每个节点由一个排序的键列表（可变但长度有限）组成，每个键引用一个子节点节点或叶子（数据节点）。这使得树甚至比平衡二叉树更平坦（这基本上就是我上面描述的）。每个节点都可以被视为必须完整读取的数据块或数据页。由于树相对平坦，查找特定数据点所需读取的页数很少。 B 树中查找的复杂性可与平衡二叉树（或就此而言对排序列表的简单二分搜索）的复杂性相媲美。区别在于必须在一步中处理的 keys/data 的数量。二叉树需要对每个级别的单个数据点进行一次读取操作，排序列表需要一次读取所有数据，而 B 树位于中间，需要每个级别的数据块。从一些操作的角度来看这是无关紧要的，从内存访问的角度来看它是非常重要的。从磁盘读取数据时，块的大小不如所需的单独读取操作的数量重要（只要它是有限的）。
目标是尽量减少磁盘寻道。读取或写入多少字节是次要的，因为顺序速度比磁盘上的随机访问快 100 倍。
这就是树高很重要的原因。
此外，树页面应该映射到物理设备块。如果每个节点只有两个值，则很难利用物理磁盘块所具有的所有 space。
您必须了解 B-trees 通常用于具有分页数据访问的系统。这是最常见的数据库系统。页本质上是一块内存，您必须立即读取（和写入）。如果不阅读整个页面，您将无法阅读页面的各个部分。
重要的是：从磁盘读取页面到内存是昂贵的；比对已经在内存中的页面做任何事情要昂贵得多。因此，您想尽量减少必须阅读的页数。
B-trees 为此目的比二叉树有几个好处——考虑到它们是专门为此目的而设计的，这不足为奇。
这些好处之一是降低了身高。如果你采用普通的二叉树，你可以在其中快速搜索。但在这样做的同时，你会走到树的深处。一棵包含 100 万个元素的树的深度已经是 20。因此，假设它是平衡的，您需要向下遍历 20 个节点。与B-tree相比，高度低了很多。 children 计数为 10（ 非常低 顺便说一句。）我们已经将高度降低到大约 6。因此我们需要进行更少的比较，并且可能加载更少的页面。通常，一个B-tree的顺序（也就是每个节点有children个数）的选择方式是这样的，所以一个节点填满一个完整的页面.现在这听起来可能很愚蠢，因为那时您需要在该节点的键中进行搜索，但它大大减少了深度，因此减少了您必须阅读的页面数量。
另一个好处是 B-trees 是平衡的。这确保了所有节点在任何时候都被大约等量的 children 填充。通常，这大约是其容量的 75%。由于节点填满了一个完整的页面，这意味着每个包含节点的页面都被填满了它的容量。这非常好，因为它优化了节点使用的 space 并避免了不包含信息的页面中的漏洞（这对于二叉树来说是个大问题，因为它们在设计上没有平衡）。另一个非常重要的影响是，这也确保了查找元素的操作次数（以及 运行 时间）是一致的。因此，对于所有情况，您的表现都非常可预测。对于数据库，这通常比拥有可能在性能上有所不同的更好的最佳或平均情况重要得多。
还有其他好处，例如让叶子不仅都在同一层，而且在物理上彼此靠近，因为这可以缩短遍历元素时的查找时间。
基本上，B-trees 针对分页数据访问进行了优化，这使它们非常特殊，并且 fine-tuned 用于这些目的，使它们优于经典的二叉树（在许多其他方面更简单、更高效）申请）。
我找到了一个很棒的讲座 here。
刚刚看了B树数据结构，有一些疑问。我有一个疑问，在任何博客中都没有解释（也许它太明显了，我错过了）。
B 树应该通过降低树的高度来减少磁盘访问。那么，如果减少磁盘访问次数是主要关注点，那么它有多大不同呢？假设我只使用二叉树，那么我的节点需要的 space 比 n 元 B 树的节点少。所以我可以在页面中容纳更多节点，就像我可以处理胖 B 树节点一样。它究竟如何影响磁盘访问？我们只是在谈论最坏的情况吗？
B代表balanced，表示在B-tree中，左右两边的节点大小（子节点个数）大致相同。
考虑这个例子： 如下将数字添加到二叉树：如果新数字大于当前节点，则以相同的方式将其添加到右侧，否则添加到左侧（子）树。
A) 想一想如果将 1 到 100 的数字按升序相加会发生什么。
B) 现在想象一下如果像这样添加它们会发生什么 50, 25, 75, 12, 37, 62, 87, ...（从区间的中间开始，然后递归地添加中点新间隔）
B 树添加新节点的方式即使您像 A) 中那样按顺序添加它们，生成的树也类似于 B) 中生成的树
对于磁盘访问，想象一下必须在 A) 和 B) 的树中查找节点 100 并比较您必须处理多少节点（磁盘访问）才能到达它。
编辑 正如评论中指出的那样，上述 B 树的介绍并不完全正确。
B树更像是一棵排序的（节点）列表树，也就是说，每个节点由一个排序的键列表（可变但长度有限）组成，每个键引用一个子节点节点或叶子（数据节点）。这使得树甚至比平衡二叉树更平坦（这基本上就是我上面描述的）。每个节点都可以被视为必须完整读取的数据块或数据页。由于树相对平坦，查找特定数据点所需读取的页数很少。 B 树中查找的复杂性可与平衡二叉树（或就此而言对排序列表的简单二分搜索）的复杂性相媲美。区别在于必须在一步中处理的 keys/data 的数量。二叉树需要对每个级别的单个数据点进行一次读取操作，排序列表需要一次读取所有数据，而 B 树位于中间，需要每个级别的数据块。从一些操作的角度来看这是无关紧要的，从内存访问的角度来看它是非常重要的。从磁盘读取数据时，块的大小不如所需的单独读取操作的数量重要（只要它是有限的）。
目标是尽量减少磁盘寻道。读取或写入多少字节是次要的，因为顺序速度比磁盘上的随机访问快 100 倍。
这就是树高很重要的原因。
此外，树页面应该映射到物理设备块。如果每个节点只有两个值，则很难利用物理磁盘块所具有的所有 space。
您必须了解 B-trees 通常用于具有分页数据访问的系统。这是最常见的数据库系统。页本质上是一块内存，您必须立即读取（和写入）。如果不阅读整个页面，您将无法阅读页面的各个部分。
重要的是：从磁盘读取页面到内存是昂贵的；比对已经在内存中的页面做任何事情要昂贵得多。因此，您想尽量减少必须阅读的页数。
B-trees 为此目的比二叉树有几个好处——考虑到它们是专门为此目的而设计的，这不足为奇。
这些好处之一是降低了身高。如果你采用普通的二叉树，你可以在其中快速搜索。但在这样做的同时，你会走到树的深处。一棵包含 100 万个元素的树的深度已经是 20。因此，假设它是平衡的，您需要向下遍历 20 个节点。与B-tree相比，高度低了很多。 children 计数为 10（ 非常低 顺便说一句。）我们已经将高度降低到大约 6。因此我们需要进行更少的比较，并且可能加载更少的页面。通常，一个B-tree的顺序（也就是每个节点有children个数）的选择方式是这样的，所以一个节点填满一个完整的页面.现在这听起来可能很愚蠢，因为那时您需要在该节点的键中进行搜索，但它大大减少了深度，因此减少了您必须阅读的页面数量。
另一个好处是 B-trees 是平衡的。这确保了所有节点在任何时候都被大约等量的 children 填充。通常，这大约是其容量的 75%。由于节点填满了一个完整的页面，这意味着每个包含节点的页面都被填满了它的容量。这非常好，因为它优化了节点使用的 space 并避免了不包含信息的页面中的漏洞（这对于二叉树来说是个大问题，因为它们在设计上没有平衡）。另一个非常重要的影响是，这也确保了查找元素的操作次数（以及 运行 时间）是一致的。因此，对于所有情况，您的表现都非常可预测。对于数据库，这通常比拥有可能在性能上有所不同的更好的最佳或平均情况重要得多。
还有其他好处，例如让叶子不仅都在同一层，而且在物理上彼此靠近，因为这可以缩短遍历元素时的查找时间。
基本上，B-trees 针对分页数据访问进行了优化，这使它们非常特殊，并且 fine-tuned 用于这些目的，使它们优于经典的二叉树（在许多其他方面更简单、更高效）申请）。
我找到了一个很棒的讲座 here。