408第一季 - 数据结构 - B树与B+树

B树

性质

可以看见一个节点可以有多个数字了

然后也满足左小右大的特征

 然后所有的叶子节点都在同一层，然后2个数字的节点就可以有3个分支

然后呢，每个节点里面到底有几个数字是有规定的公式的

 就这个公式，m是5阶的，算出来是2和4，也就是说最少2个最多4个

然后5阶的意思就是最多有5个分叉

前提是非根

 

做题

1

这里最多有3个关键字，所以是4阶的B树

当然这种非真题不是很严谨，因为5阶，6阶都有可能

但不能7阶，因为7阶的时候就是 7/2 - 1 = 3，每个节点至少有3个关键字

2

先看第14题

算出来最少2个，最多4个

这个公式要注意的是根节点是例外，可以是1个，其他至少得2个

图画出来是这样

a

然后第15题

它问的是结点个数最多哈，也就是一个结点一个关键字就行，也就是15个

d

3

根据公式最少是1个节点，最多2个，所以这里也就是求高度为5的满二叉树

2的5次方-1 = 31

b

B树的插入

做法

有一个概念就是分裂，看图就行了

比如这里已经算好了，最少是1个关键字，最多是2个关键字

然后我要插入60，插入后发现b图这里有3个关键字，不满足要求

然后开始分裂，也就是说把中间的关键字提到上面去

那如果是4个，你可以把第2个放上面，也可以把第3个放上面都行

做题

1

这里把删除先改成插入61，删除还没学

最多2个，最少1个关键字不多说

第一次分裂后还是超出的上限，继续分裂

最后变成这样

2

 

B树的删除

做法

这上面也就是说，你删的不是叶子节点就要用左边最大或右边最小的去替代

这里即可以放78也可以放90

然后是叶子节点的删除

这是第一种

这是第二种

这里是4阶的，最少也得1个呢，所以过程是这样的

65：兄弟我被被删了，能不能借一个

74：兄弟你太性情了，没问题啊

71：不是就你想借就借啊，你放我左边我可借不了

74：那行，爹，那你下去，我替您上去得了

这是第三种

5：兄弟，借一下

65，byd找你爹去，我不够借

然后60替换到下面去，可以发现60和65可以合并，合并的时候不用担心会不会超出上限，因为本来就不够借，多一个不会怎么样

题目

1

d

2

重点

B+树

概念

B+树 = 毕加索

左边是小于等于60的  右边是大于60小于等于85的

然后数字是必须要有重复出现的，比如60就一直跑到了叶子节点，也就是说，上面的只是索引，告诉你应该往哪里走

并且叶子节点是通过指针连起来的，变成有序表

与B树的差异

然后就是B+树有二种方式查找