河池学院：《数据结构》课程电子教案（PPT教学课件）第9章 查找 9.3 树表的查找（2/2）

一种外查找的数据组织结构 B-树中所有结点的最大子树个数称为B-树的阶，通常用m表示，从查找效 率考虑，要求m≥3。一棵m阶B-树或者是一棵空树，或者是满足下列要求的m叉 树： （1）树中每个结点至多有m棵子树（即至多含有m-1个关键字， 设Max=m-1）。 （2）若根结点不是叶子结点，则根结点至少有两棵子树。 （3）除根结点外，所有结点至少有m/2棵子树（即至少含有 m/2-1个关键字，设Min=m/2-1）。 1/28

（4）每个结点的结构如下： n p0 key1 p1 key2 p2 . keyn pn （5）所有的叶子结点在同一层。 m/2-1≤n≤m-1，并且满足有序性 2/28

一棵3阶B-树 10 3 6 13 18 1 2 4 5 7 9 11 12 14 17 19 20 根结点 外部结点层 叶子结点层 高度h=3 m=3 非叶子结点至少有m/2=2个孩子，至多有m=3个孩子（这类结 点的关键字个数为1～2个） 根结点有两个孩子结点 所有叶子结点都在同一层上 3/28

1. B-树的查找 在B-树中查找给定关键字的方法类似于二叉排序树上的查找，不同的是在 每个结点上确定向下查找的路径不一定是二路的，而是n+1路的（n为该结点的 关键字个数）。 10 3 6 13 18 1 2 4 5 7 9 11 12 14 17 19 20 根结点 外部结点层 叶子结点层 高度h=3 4/28

假设m阶B-树的高度为h（h中不含外部结点层，外部结点层看成是第 h+1层），访问的结点个数不超过O(h)。 那么，含有N个关键字的m阶B-树可能达到的最大高度h是多少呢？显然 在关键字个数固定时，每一层关键字个数越少树的高度越高。 第1层最少结点数为1。 第2层最少结点数为2。 第3层最少结点数为2m/2。 第4层最少结点数为2m/2 2个。 . 第h层最少结点数为2m/2 h-2个。 第h+1层（外部结点层）最少结点数为2m/2 h-1个。 m阶B-树中共含有N个关键字，则外部结点必为N+1个，即N+1≥2m/2 h-1，有 h-1≤logm/2(N+1)/2，则h≤logm/2(N+1)/2+1=O(logmN)。 m/2-1≤n≤m-1， m/2≤结点子树数≤m 5/28

2. B-树的插入 （1）利用前述的查找过程找到关键字k的插入结点p（注意m阶B-树的插 入结点一定是某个叶子结点）。 （2）判断结点p是否还有空位置，即其关键字个数n是否满足n<Max （Max=m-1）： ① 若n<Max成立，说明结点p有空位置，直接把关键字k有序插入到结 点p中（插入关键字k后结点p的所有关键字仍有序）。 6/28

② 若n=Max，说明结点p没有空位置，需要把结点p分裂成两个。 p k1 . ks . kn . 中间关键字 k1 . ks-1 . ks . ks+1 . kn 分裂 如果此时双亲结点的关键字个数也超过Max，则要再分裂，再往 上插，直至这个过程传递到根结点为止。如果根结点也需要分裂，则 整个m阶B-树增高一层。 7/28

【例9.16】关键字序列为（1，2，6，7，11，4，8，13，10，5，17， 9，16，20，3，12，14，18，19，15），创建一棵5阶B-树。 解：这里m=5，结点中最大关键字个数Max=m-1=4。 1 1 2,6,7 1 2 6 7 8/28

11 1 2 6 7 11 1 2 7 11 6 4,8,13 1 2 4 7 8 11 13 6 10 1 2 4 7 8 10 11 13 6 1 2 4 6 10 7 8 11 13 9/28

5,17,9,16 1 2 4 5 6 10 7 8 9 11 13 16 17 20 1 2 4 5 6 10 7 8 9 11 13 16 17 20 1 2 4 5 6 10 16 7 8 9 11 13 17 20 10/28