B-树和2-3-4树之间差

问题描述 投票:11回答:2

是什么B-树和2-3-4树之间的区别?

还有,你怎么会发现每一个最大和最小高度?

data-structures tree theory b-tree
2个回答
22
投票

......一个链接到Wikipedia及报价:

“2-3-4树的顺序4. B树”

一个2-3-4B-tree。 这就是所谓的2-3-4树,因为儿童的非叶的数目,非根节点是2,3或4。 如果这是6,它可能已被称为3-4-5-6树,或3-6树的简称。 由于孩子的最小数量是最大的二分之一,可以直接跳过通常前者讲的m阶B-树。 B-树的顺序被定义为子节点的节点可以具有的最大数量。 在2-3-4树,正如我们所看到的,最大值为4。

它的最坏和最好的情况下,高度由general formula for B-trees给出。

最好的情况:logmn。 (所有节点都满) 最坏的情况:10gm的/ 2N。 (所有节点都半空)

哪里

  • m是树的顺序 - 一个节点可以有孩子的最大数量,在这种情况下,4 - 和
  • n是项树的数量

“B树可以有任意数量的命令” - 是的,但对于B树的特定子类,则修正提前这个数字。这就像在一般谈论的蝴蝶VS谈论Monarch butterfly。 B树是一类的数据结构,就像蝴蝶是一类昆虫。 Monarch butterflies是蝴蝶的一个子类,就像2-3-4树是B树的子类。


-1
投票

为什么b树开始存在的主要区别是在插入的时刻需要节点分裂的数量小于2-4树。在2-4树,我们有时会发现一个名为级联分裂,但在B树没有当前级联拆分项。

© www.soinside.com 2019 - 2024. All rights reserved.