10LsisL22l3 插入19 入19 张陪写 新。■印乡究 北京太 孔稳写 权新有轴命剑究 B树操作的访外次数 次插入操作最多读写次数 ■假设内存工作区足够大,使得在 ■总共h层,每层都需要分裂(包括根) 向下检索时读入的结点在插入后 分裂一个非根结点要向磁盘写出2个结点, 向上分裂时不必再从磁盘读入 分裂根结点(最后一次)要写出3个结点 ■读盘次数与查找相同 找插入结点向下读盘次数 最少写盘次数:一次 +分裂非根结点时写盘次数+ 不分裂,写出这个关键码所插入 +分裂根结点时写盘次数 到的结点 h+2(-1)+3=3h+1 张铭帖编写 孔写 B树的删除 B树的删除(续) 删除的关键码不在叶结点层 删除的关键码在叶结点层 删除后关键码个数不小于「m/21-1 先把此关键码与它在B树里的后继 直接删除 对换位置,然后再删除该关键码 关键码个数小于「m/2 如果兄弟结点关键码个数不等于「m/21-1 结点移若干 到该结点中来 如果兄弟结点关键码个数等于「m/21-1 北京大息学 张铭 权质有,印究 张帖写 权新有:命些 1111 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 61 插入19 20 30 21 18 33 12 48 10 15 19 24 31 45 47 50 52 23 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 62 插入19 20 30 21 18 12 48 10 15 19 24 31 45 47 50 52 33 23 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 63 B树操作的访外次数 „ 假设内存工作区足够大，使得在 向下检索时读入的结点在插入后 向上分裂时不必再从磁盘读入 „ 读盘次数与查找相同 „ 最少写盘次数：一次 „ 不分裂，写出这个关键码所插入 到的结点 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 64 一次插入操作最多读写次数 „ 总共h层，每层都需要分裂（包括根） „ 分裂一个非根结点要向磁盘写出 2 个结点， 分裂根结点（最后一次）要写出 3 个结点 = 找插入结点向下读盘次数 + + 分裂非根结点时写盘次数 + + 分裂根结点时写盘次数 = h+2(h-1)+3 = 3h+1 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 65 B树的删除 „ 删除的关键码不在叶结点层 „ 先把此关键码与它在B树里的后继 对换位置，然后再删除该关键码 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 66 B树的删除(续) „ 删除的关键码在叶结点层 „ 删除后关键码个数不小于 „ 直接删除 „ 关键码个数小于 „ 如果兄弟结点关键码个数不等于 „ 从兄弟结点移若干个关键码到该结点中来 (父结点中的一个关键码要做相应变化) „ 如果兄弟结点关键码个数等于 „ 合并 ⎡ ⎤ ⎢ ⎥ m /2 1− ⎡ ⎤ ⎢ ⎥ m /2 1− ⎡ ⎤ ⎢ ⎥ m /2 1− ⎡ ⎤ ⎢ ⎥ m /2 1−