9.3.4B-树一种外查找的数据组织结构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
一种外查找的数据组织结构 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）每个结点的结构如下：keynkeyikey2P1nPeP2PnX业[m/2]-1≤n≤m-1，并且满足有序性（5）所有的叶子结点在同一层。2/28
（4）每个结点的结构如下： n p0 key1 p1 key2 p2 . keyn pn （5）所有的叶子结点在同一层。 m/2-1≤n≤m-1，并且满足有序性 2/28
一棵3阶B-树根结点10高度h=3.13.183.64511.1214.177.919.20叶子结点层外部结点层m=3非叶子结点至少有|m/2=2个孩子，至多有m=3个孩子（这类结点的关键字个数为1～2个）根结点有两个孩子结点所有叶子结点都在同一层上3/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高度h=313.183.6124.511.1214.177919.20叶子结点层外部结点层4/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/2]-1≤n≤m-1,「m/2]≤结点子树数≤m假设m阶B-树的高度为h（h中不含外部结点层，外部结点层看成是第h+1层），访问的结点个数不超过o(h)。那么，含有N个关键字的m阶B-树可能达到的最大高度h是多少呢？显然在关键字个数固定时，每一层关键字个数越少树的高度越高。第1层最少结点数为1。第2层最少结点数为2。第3层最少结点数为2 m/2]。第4层最少结点数为2m/22个。第h层最少结点数为2m/2h-2个。第h+1层（外部结点层）最少结点数为2m/2h-1个。m阶B-树中共含有N个关键字，则外部结点必为N+1个，即N+1≥2m/2h-1，有h-1≤10glm/27(N+1)/2，则h≤1og[m/27(N+1)/2+1=0(1ogmN)。5/28
假设m阶B-树的高度为h（h中不含外部结点层，外部结点层看成是第 h+1层），访问的结点个数不超过O(h)。 那么，含有N个关键字的m阶B-树可能达到的最大高度h是多少呢？显然 在关键字个数固定时，每一层关键字个数越少树的高度越高。 第1层最少结点数为1。 第2层最少结点数为2。 第3层最少结点数为2m/2。 第4层最少结点数为2m/2 2个。 . 第h层最少结点数为2m/2 h-2个。 第h+1层（外部结点层）最少结点数为2m/2 h-1个。 m阶B-树中共含有N个关键字，则外部结点必为N+1个，即N+1≥2m/2 h-1，有 h-1≤logm/2(N+1)/2，则h≤logm/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
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分裂成两个。分裂R.Rks+1k1ks-1R..中间关键字如果此时双亲结点的关键字个数也超过Max，则要再分裂，再往上插，直至这个过程传递到根结点为止。如果根结点也需要分裂，则整个m阶B-树增高一层。7/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。112.672,6,78/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
112671117.111 24,8,1312478 11 136.101011.13124124787810111319/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
6.105,17,9,161245891113161776.10207891245111316172010166院11.137.8917 20124510/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