B树删除 保持性质:等高、阶(上下界) 保证所删除的位置在最底层(否则,与其后继关健 下游 3)若其左右兄弟中关健码数目都处在最低限 张陪写 新。■印乡究 回國:9此命排可能件到提(,國 104.2B+树 B+树的结构定义 ■是B树的一种变形 m阶B+树的结构定义如下 在叶结点上存储信息的树 ■(1)每个结点至多有m个子结点; 所有的关键码均出现在叶结点上 (2)每个结点(除根外)至少有「m/2 个子结点 各层结点中的关键码均是下一层 相应结点中最大关键码(或最小 (3)根结点至少有两个子结点; 关键码)的复写 n(4)有k个子结点的结点必有k个关键 码 ,複 张铭帖编写 孔写 2阶B+树的例子 B+树的查找 查找应该到叶结点层 在上层已找到待查的关键码,并不停止 而是继续沿指针向下一直查到叶结点层的这 个关键码 ■B树的叶结点一般链接起来,形成一个 双链表 适合顺序检索(范围检索 B54sm” 实际应用更 的话,每一层结点也可以顺序链接 北京大息学 张铭写 权质有,印究 鑫张帖_写 1313 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 73 008 040 237 240 279 110 135 142 212 052 236 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 74 B树删除 „ 保持性质：等高、阶（上下界） „ 交换——删除——借关键码——合并 „ 1) 保证所删除的位置在最底层(否则，与其后继关键 码交换) „ 2) 若删除后，结点中关键码数目不够最低限(下溢 出)，则先看左右兄弟有无多余的关键码可借，若有则 该结点与它的一个兄弟结点的所有关键码，再加上父结 点中的分界码，当成一个结点，类似于插入算法，再分 为三部分 „ 3) 若其左右兄弟中关键码数目都处在最低限，则把该 结点和它的一个兄弟，以及父结点中它俩的分界关键码 一起合并成一个结点；(父结点中关键码数目减少一个) „ 4) 此合并过程可能传递到根(则树降低一层) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 75 10.4.2 B+树 „ 是B树的一种变形 „ 在叶结点上存储信息的树 „ 所有的关键码均出现在叶结点上 „ 各层结点中的关键码均是下一层 相应结点中最大关键码（或最小 关键码）的复写 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 76 B+树的结构定义 m阶B+树的结构定义如下： „ (1)每个结点至多有m个子结点； „ (2)每个结点(除根外)至少有 个子结点； „ (3)根结点至少有两个子结点； „ (4)有k个子结点的结点必有k个关键 码。 ⎡⎢m / 2⎤⎥ 其实，根可以为 空，或者独根 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 77 2阶B+树的例子 70 95 10 20 35 40 44 51 65 70 85 91 93 95 20 40 51 70 91 95 40 70 95 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 78 B+树的查找 „ 查找应该到叶结点层 „ 在上层已找到待查的关键码，并不停止 „ 而是继续沿指针向下一直查到叶结点层的这 个关键码 „ B+树的叶结点一般链接起来，形成一个 双链表 „ 适合顺序检索（范围检索） „ 实际应用更广 需要的话，每一层结点也可以顺序链接