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