data-structures - B树和2-3-4树的区别

Question

B树和2-3-4树有什么区别？

另外，您如何找到每个的最大和最小高度？

Answer 1

...维基百科的链接 和引用：

“2-3-4 树是 4 阶 B 树。”

A2-3-4 是一个 B-tree。
它被称为 2-3-4 树，因为非叶、非根节点的子节点数为 2,3 或 4。
如果它是 6，它可能被称为 3-4-5-6 树，或简称 3-6 树。
由于孩子的最小数量是最大值的一半，因此通常可以跳过前者并谈论m阶的 B-tree 。
B树的顺序定义为节点可以拥有的最大子节点数。
正如我们所见，在 2-3-4 树中，最大值为 4。

最坏和最好的高度由B-trees 的通用公式给出。

最佳情况：log _m n。 （所有节点都已满）
最坏情况：log _m/2 n。（所有节点都是半空的）

在哪里

• m是树的顺序 - 一个节点可以拥有的最大子节点数，在这种情况下为 4 - 并且
• n是树中的条目数

“B 树可以有任意数量的顺序” - 是的，但是对于特定的 B 树子类，您需要提前确定该数量。这就像在谈论一般的蝴蝶与谈论帝王蝶。B树是一类数据结构，就像蝴蝶是一类昆虫一样。帝王蝶是蝴蝶的子类，就像 2-3-4 树是 B 树的子类一样。

Answer 2

b-tree之所以存在的主要区别是插入时所需的节点分裂数量少于2-4棵树。在 2-4 树中，我们有时会发现一个称为级联分裂的术语，但在 b-tree 中不存在级联分裂。