站长之家- 问答 2020-09-09T15:56:03 +08:00

b树和b+树有什么不同 b树和b+树特点区别汇总

b+树和b+树有哪些不同之处,这两者的特征区别具体是什么样的呢,在数据库索引中,b树和b+树的特征、优劣势分别是什么样的呢,以下我们来介绍下b树和b+树的特征和优势。

B树,即二叉搜索树:

1、所有非叶子结点至多拥有两个儿子(Left和Right);

2、所有结点存储一个关键字;

3、非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

B+树是B-树的变体,也是一种多路搜索树:

1、其定义基本与B-树同,除了:

2、非叶子结点的子树指针与关键字个数相同;

3、非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);

4、为所有叶子结点增加一个链指针;

5、所有关键字都在叶子结点出现;

B+的特性:

1、所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;

2、不可能在非叶子结点命中;

3、非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;

4、更适合文件索引系统;

b+树,是b树的一种变体,查询性能更好。

1、有n棵子树的非叶子结点中含有n个关键字(b树是n- 1 个),这些关键字不保存数据,只用来索引,所有数据都保存在叶子节点(b树是每个关键字都保存数据)。

2、所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。

3、所有的非叶子结点可以看成是索引部分,结点中仅含其子树中的最大(或最小)关键字。

4、通常在b+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结点。

5、同一个数字会在不同节点中重复出现,根节点的最大元素就是b+树的最大元素。

b+树相比于b树的查询优势:

1、b+树的中间节点不保存数据,所以磁盘页能容纳更多节点元素,更“矮胖”;

2、b+树查询必须查找到叶子节点,b树只要匹配到即可不用管元素位置,因此b+树查找更稳定(并不慢);

3、对于范围查找来说,b+树只需遍历叶子节点链表即可,b树却需要重复地中序遍历

B*树

1、B*树是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;

2、B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2);

3、B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/ 2 的数据

4、复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父

5、结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;

6、B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);

7、如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/ 3 的数据到新结点,最后在父结点增加新结点的指针;所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

推荐阅读

B+树是什么意思 B+树怎么理解

b树和b+树的区别是什么?b+树数据结构详细介绍

推荐关键词

24小时热搜

查看更多内容

大家正在看

b树和b+树的区别是什么?b+树数据结构详细介绍

B+树是什么意思 B+树怎么理解

原神爆炎树大型攻略 爆炎树怎么打阵容怎么选

原神爆炎树怎么打 爆炎树详细打法攻略

引领web3.0浪潮,移动labs重磅推出“精灵树”

中兴Grand S、Nubia 5杀向美国:树高端形象

原神急冻树攻略 超详细急冻树阵容打法攻略

DNF圣诞树怎么获得 圣诞树获取方法解析