北京大学信息学院2007年秋季学期《数据结构与算法A(实验班)》课程作业
张铭编写并发布 mzhang@ 第11次作业，12月17日（周一）课前提交，电子稿提交时间12月17日开课之前提交。
11.1 偶数阶的B 树插入上溢出时，中
位数有两个，需要注意采用统一的策略。例如，取第二个中位数，
即分裂后左(1)/2m −⎡⎤⎢⎥个关键码，右(1)/2m −⎢⎥⎣⎦；
或者取第一个中位数，分裂后左(1)/2m −⎢⎥⎣⎦
右(1)/2m −⎡⎤⎢⎥。请画出对右图的4阶B 树进行下来操作后的B 树。 (1) 分裂时采用第2个中位数为
分界码，请画出插入关键码113后的B 树；分析插入操作的访外次数。
(2) 分裂时采用第1个中位数为分界码，请画出插入关键码113后的B 树；分析插入操
作的访外次数。
(3) 在原树中删除关键码50；分析删除操作的访外次数（与1、2题无关，从根重新开
始操作）。
11.2 已知一组关键码为(20, 30, 50, 52, 60, 68, 70)，试依次插入关键码。
(1) 生成一棵3阶的B +树，画出插入所有关键码后B 树的结构。
(2) 画出删除50后的B + 状态，分析删除操作的访外次数。
11.3 假设一个数据文件每个记录对象需要占用128 字节（其中关键码占用4字节），且所
有记录均已按关键码有序地存储在主磁盘文件中。设磁盘页块大小为2048（= 2K ）字节，若主存中有12M 空间可以用来存储索引结构，索引项中每一个地址指针占8 字节。请简要回答以下问题（请写明你的计算过程）。
（1） 使用B 树索引，B 树的阶m 1最多可以为多少？4层m 1阶B 树，最多可以索引多
少字节的数据文件？
（2） 使用B +树索引，B +树的阶m 2最多可以为多少?
（3） 假设B +树的叶层各结点链接成双链结构，B +树的叶结点阶m 2’可以跟内部结点不
一样，则阶m 2’为多少?
（4） 在第(3)小题的基础上，计算4层B +树（内部结点为m 2阶，叶结点m 2’阶），最多
可以索引多少字节的数据文件？
（5） 假设尽量把B +树的头几层放入内存（本题规定不能超过12M ），那么给定关键码，
通过B +树查找到(4)小题中主数据文件的一个记录，最少几次访外？最多几次访
外？
11.4 对于下面两种B +树，列表给出他们在1、2、3、4和5层（独根是一层树）的不同情
况下，能够存储的最大记录数和最小记录数。
(1) 对于教材定义那样的B +树，其内部结点阶为50，叶结点阶为50。
(2) 如讲义P89那样的混合型B +树，其内部结点阶为55，叶结点阶为25（叶结点除关
键码，还索引部分记录信息）。
4阶B 树
