数据结构 -- B树和B+树

B树

B树

5叉查找树

最少1个关键字，2个分叉

最多4个关键字，5个分叉

如何保证查找效率

（1）eg.对于5叉排序树，规定除了根节点外，任意结点都至少有3个分叉，2个关键字

（若每个结点内关键字太少，导致树变高，要查找更多层结点，效率低）

【策略】

m叉查找树中，规定除了根结点外，任何结点至少有[m/2]个分叉，即至少含有[m/2]-1个关键字

为什么要除了根结点之外？

当树中只有一个结点时，没有办法保证

（2）不够“平衡”，树很高，有很多层节点

【策略】

m叉查找树中，规定对于任何一个结点，其所有子树的高度都要相同

满足这两点策略要求的树即为B树

B树，又称多路平衡查找树，B树中所被允许的孩子个数的最大值称为B树的阶，通常用m表示。一颗m阶的B树或为空树，或为满足以下特性的m叉树：

①树中每个结点至多有m棵子树，至多含有m-1个关键字

②若根结点不是终端结点，则至少有两棵子树

③除根结点外的所有非叶子节点至少有[m/2]个分叉，即至少含有[m/2]-1个关键字

⑤所有的叶子结点都出现在同一层，并且不带信息（可以视为外部结点或者类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）

④所有非叶子节点的结构如下：

大部分学校算B树的高度不包括叶子结点（失败结点）

问题：含n个关键字的m阶B树，最小高度、最大高度是多少？

B树的插入

B树的插入

在插入key后，若导致原结点的关键字字数超出上限，则从中间位置（[m/2]）将其的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（[m/2]）的结点插入原结点的父结点

新元素一定是插入到最底层“终端结点”，通过“查找”来确定插入位置

叶子结点必须在同一层

B树的删除

若被删除关键字在非终端节点，则用直接前驱或后继来替代被删除的关键字

直接前驱：当前关键字左侧指针所指子树“最右下”的元素

直接后继：当前关键字右侧指针所指子树“最左下”的元素

若删除关键字在非终端节点，则用直接前驱或直接后继来替代被删除的关键字

删除后关键字数量不低于下限：直接删除

删除后关键字数量低于下限：兄弟够借，用当前节点的后继（前驱）、后继的后继（前驱的前驱）来填补空缺

删除后关键字数量低于下限：兄弟不够借，若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左右兄弟结点的关键字个数均=[m/2]-1，则将关键字删除后与左（或右）兄弟结点以及双亲结点中的关键字进行合并

B+树

定义

一棵m阶的B+树需要满足以下条件
①每个分支结点最多有m棵子树

②非叶根结点至少有两棵子树，其他每个分支节点至少有[m/2]棵子树

③结点子树个数与关键字个数相等

④所有的叶结点包含全部关键字及指向对应记录的指针，叶结点中将关键字按大小排序，并且相邻叶结点按大小顺序相互连接起来

⑤所有分支结点中仅包含它的各个子节点中关键字的最大值以及指向其子节点的指针

B+树的查找

多路查找：无论查找成功与否，都要找到最后一层结点

顺序查找：直接通过指针p在叶子层进行查找

B+树 VS B树

m阶B+树：