数据结构(七)——B树和B+树

7.4.1_1 B树

5叉查找树

//5叉排序树的结点定义
struct Node {ElemType keys[4];          //最多4个关键字struct Node &child[5];     //最多5个孩子int num;                   //结点中有几个关键字
};

如何保证查找效率？
eg:对于5叉排序树，规定除了根节点处。任何结点都至少有3个分叉，2个关键字

策略: ①m叉查找树中，规定除了根节点外，任何结点至少有 $\left \lceil m/2 \right \rceil$ 个分叉，即至少含有 $\left \lceil m/2 \right \rceil -1$ 个关键字
②m叉查找树中，规定对于任何一个结点，其所有子树的高度都要相同。

7.4.1 B树

B树，又称多路平衡查找树，B树中所被允许的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树:
1)树中每个结点至多有m棵子树，即至多含有m-1个关键字。
2)若根结点不是终端结点，则至少有两棵子树。
3)除根结点外的所有非叶结点至少有 $\left \lceil m/2 \right \rceil$ 棵子树，即至少含有 $\left \lceil m/2 \right \rceil -1$ 个关键字。
5)所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空)。

7.4.1_2 B树的插入和删除

B树的插入

7.4.1_3 B+树

一棵m阶的B+树需满足下列条件:
1）每个分支结点最多有m棵子树(孩子结点)。
2）非叶根结点至少有两棵子树，其他每个分支结点至少有「m/2]棵子树。
3）结点的子树个数与关键字个数相等。
4）所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。
5）所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。

B+树 VS B树
m阶B+树:
1)结点中的n个关键字对应n棵子树
2)根节点的关键字数n∈[1, m]
其他结点的关键字数 $n\in [\left \lceil m/2 \right \rceil ,m]$
3)在B+树中，叶结点包含全部关键字,非叶结点中出现过的关键字也会出现在叶结点中
4）在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

m阶B树:
1)结点中的n个关键字对应n+1棵子树
2)根节点的关键字数n∈[1, m-1]。
其他结点的关键字数 $n\in [\left \lceil m/2 \right \rceil -1,m-1]$
3)在B树中，各结点中包含的关键字是不重复的
4)B树的结点中都包含了关键字对应的记录的存储地址