简述B-树和B+树的区别,B-树和B+树的区别是什么?

2020-12-30 16:49:41 字数 5856 阅读 3880

1楼:乐意丶

对于一棵m阶的b-树和一棵m阶的b+树,它们的主要差异:

①b-树的叶子结点不含任何信息,而b+树的叶子结点含信息(关键字及其记录等)。

②b-树上的叶子结点不会指向它的兄弟结点,而b+树上的叶子结点会指向它的兄弟结点。

作点解释:这些叶子结点一个指向一个,最终连接成一个链表。

③b-树只能进行分区间查找,而b+树上可以有两种查找:顺序查找和分区间查找。

④b-树上所有的非叶结点都满足有n个关键字的话有n+1棵子树,而b+树上所有的非叶结点含n个关键字的话只含n棵子树。这个不同引起了如下几点的不同:

(1)b-树的非叶结点有n+1个查找区间,而b+树的却少了一个区间,这个区间恰好是最右边的区间(如果存在,这个区间所指的子树上的所有关键字的值都大于结点的所有关键字的值)。

(2)在b-树上,除根的非叶结点的子树个数不能少于m/2取上界(这个值用lowbou表示),等价地,关键字的个数不能少于lowbou-1,但在b+树上这个关系发生了变化,除根的其他结点的子树个数同样不能少于lowbou,但关键字的个数却不能少于lowbou,而不是lowbou减一,这个会给b+树的一些算法的具体实现带来不同。

(3)由于根结点至少需要两棵子树,因而b-树上的根结点的关键字可以只有一个,但是b+树不能,它至少要有两个关键字,这样它才可以有两棵子树(至于为什么根结点都需要两棵子树,是因为它们都是平衡的)。

⑤b-树上每一个关键字都配有记录,而在b+树上只有叶子结点上的关键字才配有记录。

作点解释:在b+树上,所有关键字的记录(指针)都集中在叶子结点上,其他地方的关键字只是充当索引,并没有与之配有相应的记录的指针。

⑥b-树查找可以停在某个非叶结点上,而b+树不能停在非叶结点上,它需要一直查找到叶子结点才能停下,因为b+树的关键字的记录只在叶子结点上。

作点补充和解释:在b+树上只要给定的关键字的大小不要比根结点的所有关键字都大(这样就没查找的必要了,因为全树最大的值就在根结点的最右边),那么对于这个关键字的查找,最后一定是停在叶子结点上的,无论它是否存在在b+树上,或者换句话说,无论查找成功与否。

⑦b-树上的关键字在全树中出现且仅出现一次,而在b+树上一个关键字可以出现在多个位置,可以有多个,但只有一个位置的关键字配有记录。

⑧b+树非叶结点上最右边的关键字表明了它所有子树中关键字的最大值,而b-树没有这规律

b+树和b-树最大的差别可以说是⑤,甚至这不仅是和b-树的差异,和其他一般的bst树都是这样,b+树上非叶结点上的关键字只是索引,它没有记录,而关键字真正的记录是在叶子结点上。

注意:①b-树上非叶结点是全部的内部结点,而b+树上的非叶结点不是全部的内部结点,它除去了最下层的结点。

②lowbou是子树下界的意思,或者说最小子树个数。

b-树和b+树的区别是什么?

2楼:景三四

b-树是一种多路搜索树(并不是二叉的。),一颗m阶的b-树,或为空树,或者定义任意非叶子结点最多只有m个儿子。

且m>2;根结点的儿子数为[2, m]。

除根结点以外的非叶子结点的儿子数为[m/2]。

每个结点存放至少m/2-1(取上整)和至多m-1个关键字;(至少2个关键字)非叶子结点的关键字个数=指向儿子的指针个数-1;

b+树, b+树是b-树的变体,也是一种多路搜索树:其定义基本与b-树同。

b-树是一种 多路搜索 树(并不是二叉的。),一颗 m 阶 的b-树,或为空树,或 者定 义任意非叶子结点最 多只 有m 个儿子。

且m>2;根 结 点的儿 子 数 为 [2, m]。

除根结 点以 外的非叶子结点的儿子数为[m/2]。

每个结 点存放至 少m/2-1 (取上整) 和至 多 m- 1 个 关键 字;(至少2个关键字)非叶子结点的关 键 字个数 =指 向儿子 指针个数-1;

b+树, b+树是b-树的变体, 也是一种多路搜索树:其定义基本与b-树同。

b+树和b-树的差别

3楼:匿名用户

b+树是对b-树的改进,要求所有的信息都在叶子节点上,且叶子节点都在同一深度,而b-树的叶子节点可以在任意深度。

4楼:佘奇费莫昆琦

b-树是一种多路搜索树(并不是二叉的。),一颗m阶的b-树,或为空树,或者定义任意非叶子结点最多只有m个儿子。

且m>2;根结点的儿子数为[2,

m]。除根结点以外的非叶子结点的儿子数为[m/2]。

每个结点存放至少m/2-1(取上整)和至多m-1个关键字;(至少2个关键字)非叶子结点的关键字个数=指向儿子的指针个数-1;

b+树,

b+树是b-树的变体,也是一种多路搜索树:其定义基本与b-树同。

b-树是一种

多路搜索

树(并不是二叉的。),一颗m阶

的b-树,或为空树,或

者定义任意非叶子结点最

多只有m

个儿子。

且m>2;根

结点的儿子数

为[2,

m]。除根结

点以外的非叶子结点的儿子数为[m/2]。

每个结点存放至

少m/2-1

(取上整)和至多

m-1个关键

字;(至少2个关键字)非叶子结点的关

键字个数

=指向儿子

指针个数-1;

b+树,

b+树是b-树的变体,

也是一种多路搜索树:其定义基本与b-树同。

5楼:荤荡冠运莱

b-树:多路搜索树,每个结点存储m/2到m个关键字,非叶子结点存储指向关键字范围的子结点;

所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;

b+树:在b-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;b+树总是到叶子结点才命中;

6楼:乐意丶

对于一棵m阶的b-树和一棵m阶的b+树,它们的主要差异:

①b-树的叶子结点不含任何信息,而b+树的叶子结点含信息(关键字及其记录等)。

②b-树上的叶子结点不会指向它的兄弟结点,而b+树上的叶子结点会指向它的兄弟结点。

作点解释:这些叶子结点一个指向一个,最终连接成一个链表。

③b-树只能进行分区间查找,而b+树上可以有两种查找:顺序查找和分区间查找。

④b-树上所有的非叶结点都满足有n个关键字的话有n+1棵子树,而b+树上所有的非叶结点含n个关键字的话只含n棵子树。这个不同引起了如下几点的不同:

(1)b-树的非叶结点有n+1个查找区间,而b+树的却少了一个区间,这个区间恰好是最右边的区间(如果存在,这个区间所指的子树上的所有关键字的值都大于结点的所有关键字的值)。

(2)在b-树上,除根的非叶结点的子树个数不能少于m/2取上界(这个值用lowbou表示),等价地,关键字的个数不能少于lowbou-1,但在b+树上这个关系发生了变化,除根的其他结点的子树个数同样不能少于lowbou,但关键字的个数却不能少于lowbou,而不是lowbou减一,这个会给b+树的一些算法的具体实现带来不同。

(3)由于根结点至少需要两棵子树,因而b-树上的根结点的关键字可以只有一个,但是b+树不能,它至少要有两个关键字,这样它才可以有两棵子树(至于为什么根结点都需要两棵子树,是因为它们都是平衡的)。

⑤b-树上每一个关键字都配有记录,而在b+树上只有叶子结点上的关键字才配有记录。

作点解释:在b+树上,所有关键字的记录(指针)都集中在叶子结点上,其他地方的关键字只是充当索引,并没有与之配有相应的记录的指针。

⑥b-树查找可以停在某个非叶结点上,而b+树不能停在非叶结点上,它需要一直查找到叶子结点才能停下,因为b+树的关键字的记录只在叶子结点上。

作点补充和解释:在b+树上只要给定的关键字的大小不要比根结点的所有关键字都大(这样就没查找的必要了,因为全树最大的值就在根结点的最右边),那么对于这个关键字的查找,最后一定是停在叶子结点上的,无论它是否存在在b+树上,或者换句话说,无论查找成功与否。

⑦b-树上的关键字在全树中出现且仅出现一次,而在b+树上一个关键字可以出现在多个位置,可以有多个,但只有一个位置的关键字配有记录。

⑧b+树非叶结点上最右边的关键字表明了它所有子树中关键字的最大值,而b-树没有这规律

b+树和b-树最大的差别可以说是⑤,甚至这不仅是和b-树的差异,和其他一般的bst树都是这样,b+树上非叶结点上的关键字只是索引,它没有记录,而关键字真正的记录是在叶子结点上。

注意:①b-树上非叶结点是全部的内部结点,而b+树上的非叶结点不是全部的内部结点,它除去了最下层的结点。

②lowbou是子树下界的意思,或者说最小子树个数。

b- 树 和b+树的应用?

7楼:牢廷谦籍念

b-树:多路搜索树,每个结点存储m/2到m个关键字,非叶子结点存储指向关键字范围的子结点;

所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;

b+树:在b-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;b+树总是到叶子结点才命中;

b-树和b+树的区别是什么?

8楼:乙熹羿懿

对于一棵m阶的b-树和一棵m阶的b+树,它们的主要差异:

①b-树的叶子结点不含任何信息,而b+树的叶子结点含信息(关键字及其记录等)。

②b-树上的叶子结点不会指向它的兄弟结点,而b+树上的叶子结点会指向它的兄弟结点。

作点解释:这些叶子结点一个指向一个,最终连接成一个链表。

③b-树只能进行分区间查找,而b+树上可以有两种查找:顺序查找和分区间查找。

④b-树上所有的非叶结点都满足有n个关键字的话有n+1棵子树,而b+树上所有的非叶结点含n个关键字的话只含n棵子树。这个不同引起了如下几点的不同:

(1)b-树的非叶结点有n+1个查找区间,而b+树的却少了一个区间,这个区间恰好是最右边的区间(如果存在,这个区间所指的子树上的所有关键字的值都大于结点的所有关键字的值)。

(2)在b-树上,除根的非叶结点的子树个数不能少于m/2取上界(这个值用lowbou表示),等价地,关键字的个数不能少于lowbou-1,但在b+树上这个关系发生了变化,除根的其他结点的子树个数同样不能少于lowbou,但关键字的个数却不能少于lowbou,而不是lowbou减一,这个会给b+树的一些算法的具体实现带来不同。

(3)由于根结点至少需要两棵子树,因而b-树上的根结点的关键字可以只有一个,但是b+树不能,它至少要有两个关键字,这样它才可以有两棵子树(至于为什么根结点都需要两棵子树,是因为它们都是平衡的)。

⑤b-树上每一个关键字都配有记录,而在b+树上只有叶子结点上的关键字才配有记录。

作点解释:在b+树上,所有关键字的记录(指针)都集中在叶子结点上,其他地方的关键字只是充当索引,并没有与之配有相应的记录的指针。

⑥b-树查找可以停在某个非叶结点上,而b+树不能停在非叶结点上,它需要一直查找到叶子结点才能停下,因为b+树的关键字的记录只在叶子结点上。

作点补充和解释:在b+树上只要给定的关键字的大小不要比根结点的所有关键字都大(这样就没查找的必要了,因为全树最大的值就在根结点的最右边),那么对于这个关键字的查找,最后一定是停在叶子结点上的,无论它是否存在在b+树上,或者换句话说,无论查找成功与否。

⑦b-树上的关键字在全树中出现且仅出现一次,而在b+树上一个关键字可以出现在多个位置,可以有多个,但只有一个位置的关键字配有记录。

⑧b+树非叶结点上最右边的关键字表明了它所有子树中关键字的最大值,而b-树没有这规律

b+树和b-树最大的差别可以说是⑤,甚至这不仅是和b-树的差异,和其他一般的bst树都是这样,b+树上非叶结点上的关键字只是索引,它没有记录,而关键字真正的记录是在叶子结点上。

注意:①b-树上非叶结点是全部的内部结点,而b+树上的非叶结点不是全部的内部结点,它除去了最下层的结点。

②lowbou是子树下界的意思,或者说最小子树个数。

C语言a b和a b的区别,C语言,++a+b和++b+a有什么区别

1楼 匿名用户 自增对象不同 a b 最后自增的是b a b 最后自增的a b c语言, a b和 b a有什么区别 2楼 珑月三 a b是先a加1,然后再加b b a是先b 1,然后再加a 3楼 亱風 a b是a先自加然后加b b a是b自加,,然后加a 结果一样,但是a 和b的值不相同 c语言b...

与狼共舞衣服a版和b版的区别,与狼共舞衣服A版和B版的区别

1楼 绿蓑江上 与狼共舞衣服a版表示正常体型 b版表示偏胖体型。 服装系列产品采用国家标准号型,具体表示为 号 型 体型代号,如 170 92a 175 96b。 号 指人体的身高, 型 表示 净 围度。上装指胸围。下装指腰围,a或b 指体型分类代号。 男子体型代号 体型分类代号 净胸围与净腰围差值...

葫芦丝b调和c调的区别

1楼 赤秀英鲁昭 葫芦丝b调和c调没有好坏之分,根据曲子的调性选择就可以了。例如吹月光下的凤尾竹使用的c调,有一个美丽的地方用降b调。 2楼 童云德庆戌 葫芦丝的好坏不在于调,而在于制作工艺。c调还是降b调不能决定葫芦丝的好坏。各种调的葫芦丝吹奏方法是一样的,只是在音色上的区别,这种区别也是为了适应...