数据库系统实现习题答案

1、以下来自何刚同学版本，谢谢他的无私贡献。不是官方标答，仅供复习参考。第三次作业欢迎补充！目录Exercise 14.1.11Exercise 14.1.31Exercise 14.1.51Exercise 14.1.62Exercise 14.2.12Exercise 14.2.53Exercise 14.2.86Exercise 14.3.27Exercise 14.3.57Exercise 14.3.716Exercise 14.3.816Exercise 14.3.916Exercise 14.5.517Exercise 14.6.3（有误）17Exercise 14.1.1答：（a）：

2、当使用稠密索引时，因为一个索引项对应一条记录，而且索引表中每一个块有20个键值指针索引项，所以有n条记录需要个索引块，又因为每一个块中最多可以存放5条记录，所以n条记录的数据文件需要的块数为，故需要的总块数为+=。（b）：当使用稀疏索引时，因为一个索引项对应一个数据块，而且数据块个数为，所以就有个索引项，又因为一个块中最多可以存放20个索引项，因此索引项需要的块数为=，因此所需要的总块数为+=Exercise 14.1.3答：（a）：对于稠密索引而言，下一级索引必须是稀疏索引，而一级索引块数为，也就是说，上一级的键-指针对数为，以此类推，整个索引文件的块数为，其中，所以所需要的总块数为+（b）

3、：同理可得，整个索此文件的块数为，其中，所以所需要的总块数为+Exercise 14.1.5答：（a）：由题意知，当使用间接桶索引时，数据块数为。又因为间接桶索引是使用稠密索引，因此需要5000个指针，而一个记录块中可存放100个指针，所以指针块数为。从二级索引到间接桶的索引可以看出，每一个二级索引项对应间接桶中第一个键值，每10条记录（指针）有对应一个二级索引项，而一个块中可以存入20个键值指针对，同时一个二级指针可以指向10个连续的桶空间，也就是说，一个二级索引项块对应2个指针块，所以索引块数为，因此当使用间接桶时，总共所需要的块数为。当不使用间接桶时，由于使用稠密索引（ 辅助索引总是稠密

4、索引），所以索引块数为，由上知，数据块数为1000，所以当不使用间接桶进，总共所需要的块数为。（b）：当5000条记录的键值均相同时，由于间接桶与记录是根据稠密索引建立的，此时的块数没有变化，即指针块数和数据块数分别为5000/100=50和5000/5=1000，对于二级索引块，只需要一个索引项对应整个间接桶，即只需要一个索引块即可，总共的块数为50+1000+1=1051。当5000条记录的键值均不相同时，对于每一个间接桶项均需要一个索引项与之对应，所以此时达到的总块数为最多，则需要的索引块数为5000/20，因此最多的块数为50+1000+250=1300。Exercise 14.1.6

5、答：Exercise 14.2.1答：（a）（）：由于B-tree是稠密索引，所以叶子结点中的一个指针对应一条记录，又因为总记录数为100,000，数据文件所需的块数为 ；根据B-tree的特点可知，假如一个叶子结点有k个键值，则有k个指针指向记录，同时一个结点中最多的键值数为69，因此叶子结点的个数为；对于叶子结点的上一层而言，假如下一层有k个结点，那么上一层必须有k个指针，又因为一个结点中最多的指针数为70个，所以上一层结点数为<70，因此上一层只需要一个根结点即可建立整个索引，故总共所需要的结点即块数为。（）：由上知，B-tree的层数为3层，所以I/O数=4。（b）（）

6、：对于B-tree而言，即使数据文件中的记录是无序的，与有序的数据文件相比，同样需要相同数量的块数目，即总的块数为11472。（）：I/O数为4。（c）（）：对于稀疏索引的B-tree，在叶子结点中，每一个索引项对应一个块，而整个数据文件的总块数为，又叶子结点中最多的指针数为69个，所以叶子数为，上一层结点个数为，根结点个数为1，因此总共所需要的块数为。（）：I/O数为4。（d）（）：由于B-tree是稀疏索引，所以叶子结点中的一个指针对应一个块，又因为总记录数为100,000，一个块中可以存放15条记录，数据文件所需的块数为 ；根据B-tree的特点可知，假如一个叶子结点有k个键值

7、，则有k个指针指向记录，同时一个结点中最多的键值数为69，因此叶子结点的个数为；对于叶子结点的上一层而言，假如下一层有k个结点，那么上一层必须有k个指针，又因为一个结点中最多的指针数为70个，所以上一层结点数为<70，因此上一层只需要一个根结点即可建立整个索引，故总共所需要的结点即块数为。（）：由上知，B-tree的总层数为3，当查找的记录文件在主块中时所需的I/O=；当查找的记录文件在溢出块时所需的I/O=，因此平均I/O=（e）（）：根据题意知，叶子结点中没有指针，只有数据记录，而每个叶子结点中最多为7条记录，因此叶子结点个数为，倒数第二层结点数为，倒数第三层结点数为，根结点个数为1

8、，因此总共所需的块数为14286+205+3+1=14495。（）：由于记录就在叶子结点中，所以I/O=层数=3。Exercise 14.2.5答：（a）：查找操作并没有增加改变B-tree结构。（b）：查找操作并没有增加改变B-tree结构。（c）：查找操作并没有增加改变B-tree结构。（d）：查找操作并没有增加改变B-tree结构。（e）：查找操作并没有增加改变B-tree结构。（f）：插入键值为1的记录。首先以（a）的步骤进行查找键值1应所在的叶子结点，发现键值1应该放在第一个叶子结点中，但是由于第一个叶子结点键值数已经达到最大，所以需要将第一个叶子结点进行分裂，将前2个键值1和2单独

9、作为一个叶子结点，后两个键值3和5单独作为一个叶子结点，同时还需要上层指针指向这两个叶子结点，由于第二叶子结点的最小键值为3，所以将3写入到上层结点中，并将第一个指针指向键值为1和2的叶子结点，第二指针指向键值为3和5的结点，第三个指针不变，经过以上变化，所得到新的B-tree结构如下图1所示：图1 插入1时新的B-tree结构（g）：删除键值为23的记录。同样需要查找含有键值为23的叶子结点，因此可以找到第四个叶子结点含有键值23，当删除该键、该键对应的指针以及指针指向的记录后，第四个叶结点只剩下一个键值，但是至少需要两个键值，而第三个叶子结点有额外的键-指针对，因此可以将它最大的键值19及

10、相应的指针移到第四个结点中，且其父结点中的第一个键值改为19，此时得到如图2所示的新的B-tree结构：图2 删除23时新的B-tree结构（h）：（）插入键值为14到16的记录。插入14时的B-tree结构如下图所示：图3 添加14时新的B-tree结构（）：当在图3的基础上添加15时，根据图3知，由于第三个叶子结点还有一个额外的键值可写入，因此键值为15的记录可以直接写入到第三个结点中，不会影响整个B-tree结构，得到如图4所示：图4 添加15时新的B-tree结构（）：当在图4的基础上添加16时，由于第三个叶子结点已经超过最多的键值数，所以需要对其分裂成两个叶结点，因此得到如图5所示的

11、B-tree结构：图5 添加16时新的B-tree结构（i）：删除键值大于等于23的记录：同（g）描述的步骤，可以得到如图6所示的新B-tree结构：图6 删除大于等于23时新的B-tree结构Exercise 14.2.8答：根据题意知，首先只有一个包含键值为1、2和3结点，当插入键值为4的记录时，需要将这个结点进行分裂为两个叶子结点，同时还需要增加一个根结点，其键值为3，此时B-tree的层数为2。又由于根结点最多的键值数为3，最多指针数为4，而每一个叶子结点达到4个键值时将分裂成两个键值数量相同的叶子结点，所以可以得出当达到三层时，插入的键值为4+(4-1)*2=10，其中的(4-1)表

12、示根结点中剩余的指针数，2表示第个叶结点都含有2个键值，当达到四层时，插入的键值为10+(4-1)*(4-1)*2=28。Exercise 14.3.2答：（a）：简单散列表：对于插入算法，不管键值是否重复，都不需要进行修改；对于查找和删除算法，由于存在相同的键值，当查找到键值为key的记录时，还需要在同一个桶中继续查找键值为key的记录。存在的问题：如果不同的键值比较少，那么会导致溢出块的数目越来越多，也就是说，不管hash表中有多少个桶，hash表根本就没有作用。（b）：线性散列表：对于插入算法，由于存在相同的键值，需要新增桶，但是记录只是存放在已满的桶的溢出块中。对于查找和删除算法，当查

13、找到某一键值时，需要继续在该桶中查找是否还存在相同键值的记录。存在的问题：当相同的键值比较多时，某一个桶添加的溢出块会不断的增加，同时也会增加一些空桶，使其他桶没有得到充分的利用。（c）：可扩展散列表：对于插入算法，如果桶满了，则需要对桶进行分裂，同时指针数组还需要翻倍；对于查找和删除算法，由于存在相同的键值，当查找到键值为key的记录时，还需要按照前i位或后i位序列的指针继续查找键值为key的记录；存在的问题：如果相同的键值比较多，那么会导致桶不断的分裂，使大部分记录都存储在同一序列下，其他的桶没有得到很好的利用；同时，当桶满时，还会造成指针数翻倍，从而可能会由于将其他的指针替换掉，导致整个

14、性能突然下降。Exercise 14.3.5答：（a）：对键值为1111,1110,.,0000，使用可扩展hash建立hash表，此处取后i位作为桶号，hash表如图1所示： 图1使用可扩展hash建立hash表（b）：对键值为1111,1110,.,0000，使用域值为75%的线性hash建立hash表，此处取后i位作为桶号，hash表如图2所示： 图2 使用域值为75%的线性hash建立hash表（c）：对键值为0000,0001,.,1111，使用可扩展hash建立hash表，此处取后i位作为桶号，hash表如图3所示：图3使用可扩展hash建立hash表（d）：对键值为0000,00

15、01,.,1111，使用域值为100%的线性hash建立hash表，此处取后i位作为桶号，hash表如图4所示：图4使用域值为100%的线性hash建立hash表Exercise 14.3.7答：（a）：如果B=10，对于任何的整数i，i从0至9的平方对10取模后，得到的散列值分别为0，1，4，9，6，5，6，9，4，1，可以得知，2，3，7，8号桶永远也都是空闲的，而1，4，6，9号桶可以很好的利用。（b）：如果B=16，从0至9的平方对16取模后，得到的散列值为0，1，4，9，0，9，4，1，0，1，可以看出0，1，4，9号桶中记录的分配比较均匀。（c）：当B取素数时，可以使记录更平均的分

16、配到各个桶中。Exercise 14.3.8答：（a）：假设总共的块数为b，则当前块中已容纳的最多的记录数为k*b，桶中最多可容纳的记录数为n*k，因此由得（b）：设期望使用的块数为b，实际平均的记录数为，因此由得，而，所以。Exercise 14.3.9答：（a）：最少的情况下，每个桶中的记录数为100的倍数，而且总的块数为1000000/100=10000，因此每个桶中需要10000/2000=5个块，因此，最少需要10000个块存储此hash表。（b）：最多的情况下，当每1999个桶中只有一条记录时，由于每两个桶不能共享同一个块，所以这1999个桶需要1999个块，剩余的一个桶中需要存储

17、998001条记录，即9981块，故总共所需要的最多块数为1999+9981=11980。Exercise 14.5.5答：（a）：x的最小刻度为20，y的最小刻度为50，所以330<x<400之间需要划分(400-320)/20=4个区域，620<y<860之间需要划分(900-600)/50=6个区域，因此查找的桶数为4*6=24个。（b）：要查找具体的点（110，245），在左下角（100，200）和右上角（120，250）的桶中，最近的点是（115，230），距离为，查找范围为，所以还需要查找5个桶，即左下角为（80，200）的桶、左下角为（80，250）的桶、左下角为（100，250）的桶、左下角为（120，200）的桶、左下角为（120，250）的桶。Exercise 14.6.3（有误）答：（a）：如果第一级索引建立在y上，因为一个y值对应5个不同的x值，则5000条记录需要100个建立在y上的一级索引块，同时对于每一个y需要对每一个块建立二级索引，因此查找对于x=C，需要先从二级索引中查找，此时需要的I/O数为1000，再由给定的y=D，从一级索引中查找，I/O为1，因此访问一条记录并取出z值时总I/O数为1002次。（b）：如果第一级索引建立在x上，因为一个x值对应50个不同的y值，又每一个块能容纳10个键-指针对，所以，5000条