当根结点分裂时，因没有父结点，则建立一个新的 f 分裂m 根，B树增高一层。 b h m 例（下页）：在二个3阶B树(23树)上插入结点的 a)一操2-3 b)插入d后 [⊙浙入p后并进行分裂 过程。 f m 分裂 f h m ()算法实现 bd b d p 要实现插入，首先必须考虑结点的分裂。设待分 d描入后 e侧)描入g后并进行分要 裂的结点是p,分裂时先开辟一个新结点，依此将结点p 中后半部分的关键字和指针移到新开辟的结点中。分裂 fh m 分裂 之后，而需要插入到父结点中的关键字在P的关键字向 量的p->keynum+1位置上。 b d b d g 0缝续进行分裂 在B中进行入的过程 BTNode *split(BTNode*p) void insert BTree(BTNode 'T,KeyType K) *结点p中包含个关键字，从中分裂出一个新的结点*/ 严在B树T中插入关键字K, BTNode*q;int k,mid,j; BTNode *q,*s1=NULL,*s2=NULL int n: q=(BTNode *)malloc(sizeof(BTNode)): if(BT search(T,K,p)】 严树中不存在关键字K mid=(m+1)/2;q->ptr[o]=p->ptr[mid] while (pl=NULL) for (j=1,k=mid+1;k<=m;k++) q->key]=p->key[k] {p->key0=K;”设置晴兵y q->ptr[j++]=p->ptr[k] for (n=p->keynum K<p->key[n]n--) }广将p的后半部分移到新结点q中】 p->key[n+1]=p->key[n] q->keynum=m-mid p->keynum=mid-1 p->ptr[n+1]=p->ptr[n] return(q); }产后移关键字和指针*7 p->key[n]=K;p->ptr[n-1]=s1 p->ptrn+1]=s2;P置关键字K的左右指针7 利用m阶B树的插入操作，可从空树起，将一组 if (++(p->keynum ))<m break 关键字依次插入到m阶B树中，从而生成一个m阶B else{s2=split(p);s1=p;r分裂结点py 树 K=p->key[p->keynum+1]; 4B树的删除 p=p->parent;P取出父结点I 在B树上删除一个关键字K,首先找到关键字所在 } 的结点N,然后在N中进行关键字K的删除操作。 } 若N不是叶子结点，设K是N中的第个关键字，则 f(p==NU儿L)严需要产生新的根结点y 将指针A,所指子树中的最大关键字（或最小关键字）K放 p=(BTNode*)malloc(sizeof(BTNode)): 在(K的位置，然后删除K,而K一定在叶子结点上。如 p->keynum=1;p->key[1]=K 图，删除关键字h,用关键字g代替h的位置，然后再从 p->ptr[0]=s1:p->ptr[1]=s2: 叶子结点中删除关键字g· 33 13 当根结点分裂时，因没有父结点，则建立一个新的 根，B_树增高一层。 例（下页）：在一个3阶B_树(2-3树)上插入结点的 过程。 ⑶ 算法实现 要实现插入，首先必须考虑结点的分裂。设待分 裂的结点是p，分裂时先开辟一个新结点，依此将结点p 中后半部分的关键字和指针移到新开辟的结点中。分裂 之后，而需要插入到父结点中的关键字在p的关键字向 量的p->keynum+1位置上。 14 f b h m (a) 一棵2-3树 f b d h m (b) 插入d后 f b d h m p 分裂 (c) 插入p后并进行分裂 h f m b d p h l f m b d p (d) 插入l后 分裂 g h l f m b d p (e) 插入g后并进行分裂 l f h m b d p p 分裂 在B_树中进行插入的过程 l f h m b d g p b d g l p h f m (f) 继续进行分裂 15 BTNode *split(BTNode *p) /* 结点p中包含m个关键字，从中分裂出一个新的结点 */ { BTNode *q ; int k, mid, j ; q=(BTNode *)malloc(sizeof( BTNode)) ; mid=(m+1)/2 ; q->ptr[0]=p->ptr[mid] ; for (j=1,k=mid+1; k<=m; k++) { q->key[j]=p->key[k] ; q->ptr[j++]=p->ptr[k] ; } /* 将p的后半部分移到新结点q中 */ q->keynum=m-mid ; p->keynum=mid-1 ; return(q) ; } 16 void insert_BTree(BTNode *T, KeyType K) /* 在B_树T中插入关键字K，*/ { BTNode *q, *s1=NULL, *s2=NULL ; int n ; if (!BT_search(T, K, p)) /* 树中不存在关键字K */ { while (p!=NULL) { p->key[0]=K ; /* 设置哨兵 */ for (n=p->keynum ; K<p->key[n] ; n--) { p->key[n+1]=p->key[n] ; p->ptr[n+1]=p->ptr[n] ; } /* 后移关键字和指针 */ p->key[n]=K ; p->ptr[n-1]=s1 ; 17 p->ptr[n+1]=s2 ; /* 置关键字K的左右指针 */ if (++(p->keynum ))<m break ; else { s2=split(p) ; s1=p ; /* 分裂结点p */ K=p->key[p->keynum+1] ; p=p->parent ; /* 取出父结点*/ } } if (p==NULL) /* 需要产生新的根结点 */ { p=(BTNode*)malloc(sizeof( BTNode)) ; p->keynum=1 ; p->key[1]=K ; p->ptr[0]=s1 ; p->ptr[1] =s2 ; } } } 18 4 B_树的删除 在B_树上删除一个关键字K ，首先找到关键字所在 的结点N，然后在N中进行关键字K的删除操作。 若N不是叶子结点，设K是N中的第i个关键字，则 将指针Ai-1所指子树中的最大关键字(或最小关键字)K’放 在(K)的位置，然后删除K’，而K’一定在叶子结点上。如 图，删除关键字h，用关键字g代替h的位置，然后再从 叶子结点中删除关键字g。 利用m阶B_树的插入操作，可从空树起，将一组 关键字依次插入到m阶B_树中，从而生成一个m阶B_ 树