S9.3.2B-树 §9.3.2B-树 1景老 ■定义：一裸m(m≥3)阶的B制是清足下述性质的m叉制： ·B是一种完全平衡的多阶找，主要是作为盘文并的引组织，用于 s性质1：每个轴点至少包含下列放据媒：0，P。,K,P,K2…,K,P】 外都查找， j:keys总数，K:关输字，P:指针 ■燕本想法是增大结点来韩低树高，减少访问外存的次数 keys(Po)<K <keys(P)<K2<...<Kj<keys(P) 一操m阶B制，每个纳点量多有m个孩子，m一般为50一2000 ◆性重2所有叶子在同一展上，叶子展数为树高，叶子中的指针为空. 警宝是博二设特吃双上o音银储在于内有 ◆性质3，每个非视结点中的关输字数目满足 1个纳点 「m127-1≤j≤m-1 1000 1000个关轴字 即：每个非根的内部结点的子材数在m和「m/2之间 ◆性质4：非空的B一制中，根至少有1个关黄字。 1000 001 1000 1000 1001个结点 1,001,000个关幢字 即：根不是叶子时，子制数为：2一m之间 001 1001 1000 1000 1,002,001个结点 1,002,001,000个关字 24▣ S9.3.2B树 115 3圆334853 运算 2A10A20入 ■查找 1A20A 2A28A面囚△37△A50囚 多路查找：先在结点内查找（折半或顺序），后在子结点中查 找（读盘） d0A56 一裸包含13个关键字的阶B别 =插入和生成 平衡机制：满时插入分到结点，从叶子之根，树高可能长 一层 ■除 平衡机制：半满时测除，可能要合并结点，从叶子根 树高可能减一层 根据m阶B树的定义，结点的类型定义如下： 2B树的查找 #define M5P根据实际需要定义B树的阶数 由B树的定义可知，在其上的查找过程和二叉排序 typedef struct BTNode 树的查找相似。 {int keynum;严结点中关键字的个数*/ (1)算法思想 struct BTNode*parent;r指向父结点的指针y KeyType key[M+1];P关键字向量，key[0]床用y ①从树的根结点T开始，在T所指向的结点的关键字 向量key1..keynum]中查找给定值K(用折半查找)： struct BTNode*ptr[M+1];P子树指针向量 RecType *recptr[M+1]: 若keyd=K(1≤i≤keynum),则查找成功，返回结点 产记录指针向量，recptr[0]未用I 及关键字位置：否则，转2) ②将K与向量key[1..keynum]中的各个分量的值进 )BTNode; 行比较，以选定查找的子树： ◆若K<key1小：T-T->ptr0 1
1 1 § 9.3.2 B-树 1.概念 B-树是一种完全平衡的多阶查找树，主要是作为磁盘文件的索引组织，用于 外部查找。 基本想法是增大结点来降低树高，减少访问外存的次数 一棵m阶B-树，每个结点最多有m个孩子，m一般为50－2000 例如，1棵1001阶B-树，3层即可包含10亿以上的Keys，当根结点置于内存 时，查找任一Key至多只要访问2次外存。 1000 1000 1000 1000 1000 1000 … 1001 … 1001 … 1001 1个结点 1000个关键字 1001个结点 1,001,000个关键字 1,002,001个结点 1,002,001,000个关键字 2 § 9.3.2 B-树 定义：一棵m(m≥3)阶的B-树是满足下述性质的m叉树： 性质1：每个结点至少包含下列数据域：(j, P0, K1, P1, K2, … , Kj , Pj ) j：keys总数， Ki ：关键字， Pi ：指针 keys(P0) < K1 <keys(P1) < K2 < … < Kj < keys(Pj ) 性质2：所有叶子在同一层上，叶子层数为树高h，叶子中的指针为空。 性质3：每个非根结点中的关键字数目j满足： 即：每个非根的内部结点的子树数在m和 之间 性质4：非空的B－树中，根至少有1个关键字。 即：根不是叶子时，子树数为：2～m之间 ⎡m / 2 ⎤ − 1 ≤ j ≤ m − 1 ⎡ ⎤ m / 2 3 g f d e b c a 1 24 1 15 1 ∧ 20 ∧ 2 ∧ 28 ∧ 31 ∧ 2 ∧ 10 ∧ 20 ∧ 1 ∧ 56 ∧ 1 ∧ 37 ∧ 1 ∧ 50 ∧ 3 33 48 53 i h 一棵包含13个关键字的4阶B_树 4 § 9.3.2 B-树 运算 查找 多路查找：先在结点内查找（折半或顺序），后在子结点中查 找（读盘） 插入和生成 平衡机制：满时插入分裂结点，从叶子 根，树高可能长 一层 删除 平衡机制：半满时删除，可能要合并结点，从叶子 根， 树高可能减一层 5 根据m阶B_树的定义，结点的类型定义如下： #define M 5 /* 根据实际需要定义B_树的阶数 */ typedef struct BTNode { int keynum ; /* 结点中关键字的个数 */ struct BTNode *parent ; /* 指向父结点的指针 */ KeyType key[M+1] ; /* 关键字向量,key[0]未用 */ struct BTNode *ptr[M+1] ; /* 子树指针向量 */ RecType *recptr[M+1] ; /* 记录指针向量,recptr[0]未用 */ }BTNode ; 6 2 B_树的查找 由B_树的定义可知，在其上的查找过程和二叉排序 树的查找相似。 ⑴ 算法思想 ① 从树的根结点T开始，在T所指向的结点的关键字 向量key[1…keynum]中查找给定值K(用折半查找) ： 若key[i]=K(1≤i≤keynum)，则查找成功，返回结点 及关键字位置；否则，转⑵； ② 将K与向量key[1…keynum]中的各个分量的值进 行比较，以选定查找的子树： ◆ 若K<key[1]：T=T->ptr[0]；
◆若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树的要求。 2
2 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_树的要求
当根结点分裂时，因没有父结点，则建立一个新的 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· 3
3 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_ 树
(h 从叶子结点中删除一个关键字的情况是 除 除 (I)若结点N中的关键字个数fm21:在结点中直 接删除关键字K,如图(b)∽©所示。 (2)若结点N中的关键字个数「m21:若结点N的 a 左（右）兄弟结点中的关键字个数fm2L1,则将结点 N的左（或右）兄弟结点中的最大（或最小）关键字上移 除 除 到其父结点中，而父结点中大于（或小于）且紧靠上移 m m b 关键字的关键字下移到结点N,如图(a)。 (3)若结点N和其兄弟结点中的关键字数-21： P e P (d) 删除结点N中的关键字，再将结点N中的关键字、指 回 针与其兄弟结点以及分割二者的父结点中的某个关 在B树中进行侧除的过程 键字K,合并为一个结点，若因此使父结点中的关 键字个数「m21则依世类推.如图(d 算法实现 if(b->keynum>(m-1)/2) 严左邻兄弟有多余关键字) 在B树上删除一个关键字的操作，针对上述的(2) 和(3的情况，相应的算法如下： for (k=p->keynum;k>=0;K--) {p->keyk+1片p->key[k int BTNode MoveKey(BTNode*p) p->ptr[k+1]=p->ptr[k]: P将命的左（或右）兄弟结点中的最大（成最小）关键字上移 】严将印中关键字和指针后移 广到其父结点中，父结点中的关键字下移到中/ p->key[1]=f->key[j]: {BTNode*b,*f=p->parent;产f指向p的父结点7 f->key[j]=b->key[keynum]; int k.j; 严f仲关键字下移到卵，b中最大关键字上移到y for0片0：f>pt=p:j+)产在仲找p的位置7 p->ptr[0]=b->ptr[keynum]; f>0)IP若D有左邻兄第结点7 p->keynum++: 22 {b=f->ptf-11:Pb指向p的左邻兄弟7 b->keynum-; return(1) b->key[k]=b->key[k+1]: b->ptr[k]=b->ptr[k+1]; fG<f->keynum严若p有右邻兄弟结点y 】产将6中关键字和指针前移 {b=f->pt+1]:Pb指向p的右邻兄弟v p->keynum++; if (b->keynum>(m-1)/2) b->keynum--; 严右邻兄弟有多余关键字1 return(1); p->key[p->keynum]=f->key[j+1]; f->key1]片b-keyM1]: p->ptr[p->keynum]=b->ptr[0]: return(0); P仲关键字下移到P,b中最小关键字上移到fV 】左右兄弟中无多余关键字移动失败习 for (k=0;k<b->keynum;k++) 4
4 19 在B_树中进行删除的过程 删除q b d e g l m q h f p b d e g l p h f m 删除h (a) 删除e b d e l p g f m b e l p g f m 删除d l p g m b f (b) (c) (d) 20 从叶子结点中删除一个关键字的情况是： ⑴ 若结点N中的关键字个数>⎡m/2⎤-1：在结点中直 接删除关键字K，如图 (b)∽©所示。 ⑵ 若结点N中的关键字个数=⎡m/2⎤-1：若结点N的 左(右)兄弟结点中的关键字个数>⎡m/2⎤-1，则将结点 N的左(或右)兄弟结点中的最大(或最小)关键字上移 到其父结点中，而父结点中大于(或小于)且紧靠上移 关键字的关键字下移到结点N，如图 (a)。 ⑶ 若结点N和其兄弟结点中的关键字数=⎡m/2⎤-1： 删除结点N中的关键字，再将结点N中的关键字、指 针与其兄弟结点以及分割二者的父结点中的某个关 键字Ki ，合并为一个结点，若因此使父结点中的关 键字个数<⎡m/2⎤-1 ，则依此类推，如图 (d)。 21 算法实现 在B_树上删除一个关键字的操作，针对上述的⑵ 和⑶的情况，相应的算法如下： int BTNode MoveKey(BTNode *p) /* 将p的左(或右)兄弟结点中的最大(或最小)关键字上移 */ /* 到其父结点中,父结点中的关键字下移到p中 */ { BTNode *b , *f=p->parent ; /* f指向p的父结点 */ int k, j ; for (j=0; f->ptr[j]!=p; j++) /* 在f中找p的位置 */ if (j>0) /* 若p有左邻兄弟结点 */ { b=f->ptr[j-1] ; /* b指向p的左邻兄弟 */ 22 if (b->keynum>(m-1)/2) /* 左邻兄弟有多余关键字 */ { for (k=p->keynum; k>=0; k--) { p->key[k+1]=p->key[k]; p->ptr[k+1]=p->ptr[k]; } /* 将p中关键字和指针后移 */ p->key[1]=f->key[j]; f->key[j]=b->key[keynum] ; /* f中关键字下移到p, b中最大关键字上移到f */ p->ptr[0]= b->ptr[keynum] ; p->keynum++ ; b->keynum-- ; 23 return(1) ; } if (j<f->keynum) /* 若p有右邻兄弟结点 */ { b=f->ptr[j+1] ; /* b指向p的右邻兄弟 */ if (b->keynum>(m-1)/2) /* 右邻兄弟有多余关键字 */ { p->key[p->keynum]=f->key[j+1] ; f->key[j+1]=b->key[1]; p->ptr[p->keynum]=b->ptr[0]; /* f中关键字下移到p, b中最小关键字上移到f */ for (k=0; k<b->keynum; k++) 24 { b->key[k]=b->key[k+1]; b->ptr[k]=b->ptr[k+1]; } /* 将b中关键字和指针前移 */ p->keynum++ ; b->keynum-- ; return(1) ; } } return(0); } /* 左右兄弟中无多余关键字,移动失败 */ }
BTNode *MergeNode(BTNode *p) free(p) ”将命与其左（右）邻兄弟合并返回合并后的结点指针7 for (k=j+1;k<=f->keynum k++) BTNode *b,f=p->parent; f->key[k-1]=f->key[k] int j.k; f->ptr[k-1]=f->ptrik] for0=0:f>pt归p:jt+)严在f仲我出p的位道7 }P将仲第个关键字和指针前移制 f0>0)b=千>pt邮-小Pb指向p的左邻兄弟y f->keynum-: else{b=p;p=p->ptr+小}Pp指向p的右邻I return(他)i b->key[++b->keynum]=f->key[j] b->ptr[p->keynum]=p->ptr[0] for (k=1;k<=b->keynum k++) b->key[++b->keynum]=p->key[k] b->ptr[b->keynum]=p->ptr[k] ”将印中关键字和指针移到b中) void DeleteBTNode(BTNode*T,KeyType K) for (n=j+1:n<p->keynum;n++) BTNode 'p,*S: p->key[n-1]=p->key[n] intj.n 产从p中刷除第m个关键字) 片BT_search(T,Kp):r在T中查找K的结点7 p->keynum-: if (j==0)return(T) while (p->keynum<(m-1)/2&&p->parent) ifp>pt切 if(IMoveKey(p))p=MergeNode(p): {S=p->ptrli-11 p=p->parent: while (S->ptr[S->keynum]) S=S->ptr[S->keynum]; 】”若P中关键字树目不够按2处理7 if (p==T&&T->keynum==0) 严在子树中找包含最大关键字的结点) p->key[]=S->key[S->keynum] T=T->ptr[o]:free(p); p=S;j=S->keynum 5 B树 (3)所有的非叶子结点可以看成是索引的部分，结点 中只含有其子树的根结点中的最大（或最小）关键字。 在实际的文件系统中，基本上不使用B树，而是使 如图所示是一棵3阶B+树。 用B树的一种变体，称为m阶B树。它与B树的主要 不同是叶子结点中存储记录。在B树中，所有的非叶子 由于B树的叶子结点和非叶子结点结构上的显著区 结点可以看成是索引，而其中的关键字是作为分界关 别，因此需要一个标志域加以区分，结点结构定义如 键字”，用来界定某一关键字的记录所在的子树。一棵 下： 阶B树与m阶B树的主要差异是： 3596 ()若一个结点有n棵子树，则必含有n个关键字： 1735 587696 (②)所有叶子结点中包含了全部记录的关键字信息以 1923354149586376 798496 及这些关键字记录的指针，而且叶子结点按关键字 的大小从小到大顺序链接 一3阶B树■ 5
5 25 BTNode *MergeNode(BTNode *p) /* 将p与其左(右)邻兄弟合并,返回合并后的结点指针 */ { BTNode *b, f=p->parent ; int j, k ; for (j=0; f->ptr[j]!=p; j++) /* 在f中找出p的位置 */ if (j>0) b=f->ptr[j-1]; /* b指向p的左邻兄弟 */ else { b=p; p=p->ptr[j+1]; } /* p指向p的右邻 */ b->key[++b->keynum]=f->key[j] ; b->ptr[p->keynum]=p->ptr[0] ; for (k=1; k<=b->keynum ; k++) { b->key[++b->keynum]=p->key[k] ; b->ptr[b->keynum]=p->ptr[k] ; } /* 将p中关键字和指针移到b中 */ 26 free(p); for (k=j+1; k<=f->keynum ; k++) { f->key[k-1]=f->key[k] ; f->ptr[k-1]=f->ptr[k] ; } /* 将f中第j个关键字和指针前移 */ f->keynum-- ; return(b) ; } 27 void DeleteBTNode(BTNode *T, KeyType K) { BTNode *p, *S ; int j,n ; j=BT_search(T, K, p) ; /* 在T中查找K的结点 */ if (j==0) return(T) ; if (p->ptr[j-1]) { S=p->ptr[j-1] ; while (S->ptr[S->keynum]) S=S->ptr[S->keynum] ; /* 在子树中找包含最大关键字的结点 */ p->key[j]=S->key[S ->keynum] ; p=S ; j=S->keynum ; } 28 for (n=j+1; n<p->keynum; n++) p->key[n-1]=p->key[n] ; /* 从p中删除第m个关键字 */ p->keynum-- ; while (p->keynum<(m-1)/2&&p->parent) { if (!MoveKey(p) ) p=MergeNode(p); p=p->parent ; } /* 若p中关键字树目不够,按⑵处理 */ if (p==T&&T->keynum==0) { T=T->ptr[0] ; free(p) ; } } 29 5 B+树 在实际的文件系统中，基本上不使用B_树，而是使 用B_树的一种变体，称为m阶B+树。 它与B_树的主要 不同是叶子结点中存储记录。在B+树中，所有的非叶子 结点可以看成是索引，而其中的关键字是作为“分界关 键字”，用来界定某一关键字的记录所在的子树。一棵m 阶B+树与m阶B_树的主要差异是： ⑴ 若一个结点有n棵子树，则必含有n个关键字； ⑵ 所有叶子结点中包含了全部记录的关键字信息以 及这些关键字记录的指针，而且叶子结点按关键字 的大小从小到大顺序链接； 30 ⑶ 所有的非叶子结点可以看成是索引的部分，结点 中只含有其子树的根结点中的最大(或最小)关键字。 如图所示是一棵3阶B+树。 由于B+树的叶子结点和非叶子结点结构上的显著区 别，因此需要一个标志域加以区分，结点结构定义如 下： 一棵3阶B+树 35 96 17 35 58 76 96 5 12 17 19 23 35 41 49 58 63 76 79 84 96