◆若key0kK<keyi+1=1,2,keynum-1) while (g!=NULL) T=T->ptri]: {p=q;q->key[0]=K;严设置查找哨兵1 ◆若Kkey[keynum]:T-T->ptr[keynum: for (n=g->keynum K<g->key[n];n-) 转①，直到T是叶子结点且未找到相等的关键字，则 if (n>0&&EQ(q->key[n].K))return n 查找失败。 q=q->ptr[n] (②算法实现 } retum 0; int BT_search(BTNode*T,KeyType K,BTNode*p) } 严在B树中查找关键字K查找成功返回在结点中的位置 严及结点指针p:香则返回0及最后一个结点指针) (3)算法分析 {BTNode *g;int n; 在B树上的查找有两中基本操作： p=q=T: ◆在B树上查找结点（查找算法中没有体现）： ◆在结点中查找关键字：在磁盘上找到指针ptr所指 因此有：h1+8.(+1)/2=1+gm21(+1)2) 向的结点后，将结点信息读入内存后再查找。因此， 即在含有个关键字的B树上进行查找时，从根结 磁盘上的查找次数（待查找的记录关键字在B树上的 点到待查找记录关键字的结点的路径上所涉及的结点数 层次数)是决定B树查找效率的首要因素。 不超过1+gm2(+1)/2)。 根据m阶B树的定义，第一层上至少有1个结点， 第二层上至少有2个结点：除根结点外，所有非终端结 点至少有m/2棵子树，.，第h层上至少有mv22个 结点。在这些结点中：根结点至少包含1个关键字，其 它结点至少包含m/2-1个关键字，设s=m/2,则总的 关键字数目n满足： n≥1+s-1)22s2=1+20s-11=2s11 2 s-1 3B树的插入 (2)结点“分裂”方法 B树的生成也是从空树起，逐个插入关键字。插 设待“分裂”结点包含信息为： 入时不是每插入一个关键字就添加一个叶子结点，而是 首先在最低层的某个叶子结点中添加一个关键字，然后 (m,AgK,A,K2,A2,…KmA,从其 有可能“分裂”。 中间位置分为两个结点： (m21,Ag,K,A1,.,Kmw21,4m2i) ()插入思想 (m-m/21.Am21,Kimz2+1 Am2+..,Km:Am) ①在B树的中查找关键字K,若找到，表明关键字 已存在，返回：否则，K的查找操作失败于某个叶子 并将中间关键字Km2插入到p的父结点中，以分裂 结点，转②： 后的两个结点作为中间关键字Km2的两个子结点。 ②将K插入到该叶子结点中，插入时，若： 当将中间关键字Km2插入到p的父结点后，父结点 也可能不满足m阶B树的要求（分枝数大于），则必须 ◆叶子结点的关键字数<m-1:直接插入： 对父结点进行“分裂”，一直进行下去，直到没有父结点 ◆叶子结点的关键字数m1:将结点“分裂”。 或分裂后的父结点满足阶B树的要求。 22 7 ◆ 若key[i]<K<key[i+1](i=1, 2, …keynum-1)： T=T->ptr[i]； ◆ 若K>key[keynum]：T=T->ptr[keynum]； 转①，直到T是叶子结点且未找到相等的关键字，则 查找失败。 ⑵ 算法实现 int BT_search(BTNode *T, KeyType K, BTNode *p) /* 在B_树中查找关键字K, 查找成功返回在结点中的位置 */ /* 及结点指针p; 否则返回0及最后一个结点指针 */ { BTNode *q ; int n ; p=q=T ; 8 while (q!=NULL) { p=q ; q->key[0]=K ; /* 设置查找哨兵 */ for (n=q->keynum ; K<q->key[n] ; n--) if (n>0&&EQ(q->key[n], K) ) return n ; q=q->ptr[n] ; } return 0 ; } ⑶ 算法分析 在B_树上的查找有两中基本操作： ◆ 在B_树上查找结点(查找算法中没有体现)； 9 ◆ 在结点中查找关键字：在磁盘上找到指针ptr所指 向的结点后，将结点信息读入内存后再查找。因此， 磁盘上的查找次数(待查找的记录关键字在B_树上的 层次数)是决定B_树查找效率的首要因素。 根据m阶B_树的定义，第一层上至少有1个结点， 第二层上至少有2个结点；除根结点外，所有非终端结 点至少有⎡m/2⎤棵子树，…，第h层上至少有⎡m/2⎤h-2个 结点。在这些结点中：根结点至少包含1个关键字，其 它结点至少包含⎡m/2⎤-1个关键字，设s=⎡m/2⎤，则总的 关键字数目n满足： n≧1+(s-1)∑ 2si-2=1+ i=2 h =2sh-1-1 s-1 sh-1-1 2(s-1) 10 因此有： h≦1+ ㏒s((n+1)/2)=1+㏒⎡m/2⎤((n+1)/2) 即在含有n个关键字的B_树上进行查找时，从根结 点到待查找记录关键字的结点的路径上所涉及的结点数 不超过1+ ㏒⎡m/2⎤((n+1)/2) 。 11 3 B_树的插入 B_树的生成也是从空树起，逐个插入关键字。插 入时不是每插入一个关键字就添加一个叶子结点，而是 首先在最低层的某个叶子结点中添加一个关键字，然后 有可能“分裂”。 ⑴ 插入思想 ① 在B_树的中查找关键字K，若找到，表明关键字 已存在，返回；否则，K的查找操作失败于某个叶子 结点，转 ②； ② 将K插入到该叶子结点中，插入时，若： ◆ 叶子结点的关键字数<m-1：直接插入； ◆ 叶子结点的关键字数=m-1：将结点“分裂” 。 12 ⑵ 结点“分裂”方法 设待“分裂”结点包含信息为： (m，A0，K1，A1，K2，A2，… ，Km，Am)，从其 中间位置分为两个结点： (⎡m/2⎤-1，A0，K1，A1，… ，K⎡m/2⎤-1 ，A⎡m/2⎤-1 ) (m-⎡m/2⎤，A⎡m/2⎤，K⎡m/2⎤+1，A⎡m/2⎤+1 ，… ，Km，Am ) 并将中间关键字K⎡m/2⎤插入到p的父结点中，以分裂 后的两个结点作为中间关键字K⎡m/2⎤的两个子结点。 当将中间关键字K⎡m/2⎤插入到p的父结点后，父结点 也可能不满足m阶B_树的要求(分枝数大于m)，则必须 对父结点进行“分裂”，一直进行下去，直到没有父结点 或分裂后的父结点满足m阶B_树的要求