m阶B树的结构定义 2.B树的性质 (1)每个结点至多有m个子结点; ■(1)树高平衡,所有叶结点都在同一层 (2)除根结点和叶结点外,其它每个结点至少有 关键码没有重复,父结点中的关键码是 「m/21个子结点 其子结点的分界 ■(4)B树把(值接近)相关记录放在同一个 (3)根结点至少有两个子结点 磁盘页中,从而利用了访问局部性原理; 唯一例外的是根结点就是叶结点时没有子结点 此时时树只包含一个结点 ■(5)B树保证树中至少有一定比例的结点是 (4)所有的叶结点在同一层 (5)有k个子结点的非根结点恰好包含k-1个关键 这样能够改进空间的利用率 码。 减少检紫和更新操作的磁盘读取数目 张陪写 新。■印乡究 上京大学 权新有轴命 B树的结点结构 B树的查找 B树的一个包含个关键码,j1个指针的结点的一般形式 交替的两步过程 母根结点读比率查获结定的类的关 K,P1,K2,P2,…,P}1 找到则检索成功 2.否则,确定要查的关键码值是在某个K1 和K之间,于是取p所指向的结点继续查 是关键码值,K<K2<…k 找 包括K到K之间的关键码的子树的指针 如果指向外部空结点,表示检索失败 张铭帖编写 孔写 B树检索长度 B树插入 ■设B树的高度为h 注意保持性质,特别是等高和阶的 独根树高为1 ■在自顶向下检索到叶结点的过程中 1)找到最底层,插入 可能需要进行h次读盘 2)若溢出,则结点分裂,中间关键 码连同新指针插入父结点 3)若父结点也溢出,则继续分裂 分裂过程可能传达到根结点(则树升高 北京大息学 张铭 权质有,印究 张帖写 权新有:命些9 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 49 m阶B树的结构定义 „ (1) 每个结点至多有m个子结点； „ (2) 除根结点和叶结点外，其它每个结点至少有 个子结点； „ (3) 根结点至少有两个子结点 „ 唯一例外的是根结点就是叶结点时没有子结点 „ 此时B树只包含一个结点 „ (4) 所有的叶结点在同一层； „ (5) 有k个子结点的非根结点恰好包含k-1个关键 码。 ⎡ ⎤ m / 2 ⎢ ⎥ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 50 2. B树的性质 „ (1) 树高平衡，所有叶结点都在同一层； „ (2) 关键码没有重复，父结点中的关键码是 其子结点的分界； „ (4) B树把（值接近）相关记录放在同一个 磁盘页中，从而利用了访问局部性原理； „ (5) B树保证树中至少有一定比例的结点是 满的 „ 这样能够改进空间的利用率 „ 减少检索和更新操作的磁盘读取数目 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 51 B树的结点结构 B树的一个包含j个关键码，j+1个指针的结点的一般形式 为： „ 其中Ki 是关键码值，K1<K2<…<Kj ， „ Pi 是指向包括Ki 到Ki+1之间的关键码的子树的指针。 „ 还有指针吗？ P0， K1， P1， K2， P2， …， Pj-1， Kj， Pj 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 52 B树的查找 „ 交替的两步过程 „ 1. 把根结点读出来，在根结点所包含的关 键码K1，…，Kj 中查找给定的关键码值 „ 找到则检索成功 „ 2. 否则，确定要查的关键码值是在某个Ki 和Ki+1之间，于是取pi 所指向的结点继续查 找 „ 如果pi 指向外部空结点，表示检索失败 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 53 B树检索长度 „ 设B树的高度为h „ 独根树高为1 „ 在自顶向下检索到叶结点的过程中 可能需要进行 h 次读盘 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 54 B树插入 „ 注意保持性质，特别是等高和阶的 限制 „ 1) 找到最底层，插入 „ 2) 若溢出，则结点分裂，中间关键 码连同新指针插入父结点 „ 3) 若父结点也溢出，则继续分裂 „ 分裂过程可能传达到根结点(则树升高一 层)