3B树的插入 B_树的生成也是从空树起,逐个插入关键字。插 入时不是每插入一个关键字就添加一个叶子结点,而是 首先在最低层的某个叶子结点中添加一个关键字,然后 有可能“分裂”。 (1)插入思想 ①在B_树的中查找关键字K,若找到,表明关键字 已存在,返回;否则,K的查找操作失败于某个叶子 结点,转② ②将K插入到该叶子结点中,插入时,若: ◆叶子结点的关键字数<m-1:直接插入; ◆叶子结点的关键字数=m-1:将结点“分裂”1
11 3 B_树的插入 B_树的生成也是从空树起，逐个插入关键字。插 入时不是每插入一个关键字就添加一个叶子结点，而是 首先在最低层的某个叶子结点中添加一个关键字，然后 有可能“分裂” 。 ⑴ 插入思想 ① 在B_树的中查找关键字K，若找到，表明关键字 已存在，返回；否则，K的查找操作失败于某个叶子 结点，转 ②； ② 将K插入到该叶子结点中，插入时，若： ◆ 叶子结点的关键字数<m-1：直接插入； ◆ 叶子结点的关键字数=m-1：将结点“分裂”
(2)结点“分裂”方法 设待“分裂”结点包含信息为 ,K1,A1,K2,A2 Km,Am),从其 中间位置分为两个结点: (m21,A,K1,A1,…,Km2,Am21) (m-m/21, Am/21, K- m/2+1, Am/2+1, ...,Km, Am) 并将中间关键字Km2插入到p的父结点中,以分裂 后的两个结点作为中间关键字Km2的两个子结点。 当将中间关键字Km2插入到p的父结点后,父结点 也可能不满足m阶B_树的要求(分枝数大于m),则必须 对父结点进行“分裂”,一直进行下去,直到没有父结 点或分裂后的父结点满足m阶B树的要求
12 ⑵ 结点“分裂”方法 设待“分裂”结点包含信息为： (m，A0，K1，A1，K2，A2，… ，Km，Am)，从其 中间位置分为两个结点： (m/2-1，A0，K1，A1，… ，Km/2-1 ，Am/2-1 ) (m-m/2，Am/2，Km/2+1，Am/2+1 ，… ，Km，Am ) 并将中间关键字Km/2插入到p的父结点中，以分裂 后的两个结点作为中间关键字Km/2的两个子结点。 当将中间关键字Km/2插入到p的父结点后，父结点 也可能不满足m阶B_树的要求(分枝数大于m)，则必须 对父结点进行“分裂” ，一直进行下去，直到没有父结 点或分裂后的父结点满足m阶B_树的要求
当根结点分裂时,因没有父结点,则建立一个新的 根,B_树增高一层 例(下页):在一个3阶B树(2-3树)上插入结点的 过程。 (3)算法实现 要实现插入,首先必须考虑结点的分裂。设待分 裂的结点是p,分裂时先开辟一个新结点,依此将结点p 中后半部分的关键字和指针移到新开辟的结点中。分裂 之后,而需要插入到父结点中的关键字在p的关键字向 量的p-> keynum+1位置上
13 当根结点分裂时，因没有父结点，则建立一个新的 根，B_树增高一层。 例（下页）：在一个3阶B_树(2-3树)上插入结点的 过程。 ⑶ 算法实现 要实现插入，首先必须考虑结点的分裂。设待分 裂的结点是p，分裂时先开辟一个新结点，依此将结点p 中后半部分的关键字和指针移到新开辟的结点中。分裂 之后，而需要插入到父结点中的关键字在p的关键字向 量的p->keynum+1位置上
分裂(f b(h m(b d m(bd(hmp(bd(h (a)一棵2-3树 (b)插入d后 (c)插入p后并进行分裂 分裂 fhm b d bdgghd(p b d (d)插入后 (e)插入g后并进行分裂 ( h 分裂 b d b d (继续进行分裂 在B树中进行插入的过程
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 g p 分裂 在B_树中进行插入的过程 l f h m b d g p b d g l p h f m (f) 继续进行分裂
BTNode *split(BtNode*p) /结点p中包含m个关键字,从中分裂出一个新的结点 i BtNode*q; int k, mid, j q=( BtNode )malloc(sizeof( btNode) mid=(m+1)/2, g->ptr[oFp->ptr[mid for(=1, k=mid+1; k<=m; k++) g->keyD=p->key g->ptr[++]=p->ptr[k] /将p的后半部分移到新结点q中* g->keynum=m-mid; p->keynum=mid-1 return(g)
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) ; }