数据库系统实现第14章课后答案.doc

1、14.1.1稠密索引：n/20+n;稀疏索引：n/100+n14.1.3稠密索引：2n+n/5+n/(5*20*i)(i=1,i+,(5*20*i)=20)稀疏索引：n+2n/5+n/(5*20*i)(i=1,i+,(5*20*i)=20)14.1.5a.5000/5+5000/100+(5000/10)/20=10755000/5+5000/20=1250b.最少的情况，是 5000 个记录都为重复值，所需块为：5000/5+5000/100+1=1051最多的情况，是 5000 个记录都不相同，所需块为：5000/5+5000/100+5000/20=130014.1.6有桶情况下：500

2、0/(10*20)+1+20=38无桶情况下：5000/20+12=16214.2.1a.总块数为：1000000/20+1000000/69+(1000000/69)/70+(1000000/69)/70)/20+1= 14493+208+3+1=64705所需 I/O 数：层数+1=5b. 总块数为：1000000/20+1000000/69+(1000000/69)/70+(1000000/69)/70)/20+1= 14493+208+3+1=64705所需 I/O 数：层数+1=5c. 1000000 个记录需要 1000000/20=50000 个存储块总块数：50000+5000

3、0/69+(50000/69)/70+1=50737所需 I/O 数:层数+1=4d. 存储记录所需总块数：1000000/30=33334总块数为：33334+33334/69+(33334/69)/70+1=33826所需 I/O 数:层数+1=4e. 存储记录所需总块数：1000000/7=142858总块数：142858+142858/70+(142858/70)/70+1=143481所需 I/O 数:层数+1=414.2.5a.未找到，不引起 B 树的变化。b.找到，不引起 B 树的变化。c.查找所有小于 30 的记录，不引起 B 树的变化。d.查找所有大于 30 的记录，不引起

4、B 树的变化。e.查找介于 20 和 30 之间的记录，不引起 B 树的变化。f.插入键值为 1 的节点，在叶子节点中添加一个新的节点，将 1，2 写入，并将 3 写到上一层的对应节点中，指针指向第一个叶子节点。g.删除记录值为 23 的节点，将键值为 13 的指针提前到前一个叶子节点，键值为 29 的指针也提前到前一个节点，删除叫键值 23 所在的叶子节点。删除上一层中 23 的指针，将31 下的指针指向 17 开头的节点。h.插入 14 到 16 中的所有的数，插入新的叶子节点存放 16、17、19 三个键值，将14、15 插入到键值 13 所在的节点中，并将 13 插入到上层键值 7 所

5、在的节点指针指向键值13 所在的叶子节点。i.新的 B 树如下714.2.8题目没看懂。 。 。143.2出现重复值的情况时 删除操作，在执行完删除操作后，紧接着执行查找操作，看是否还能找到键值，若能找到则继续删除。 查询操作，可以不用改变。 插入操作，不需要修改。出现重复值，带来的问题 简单散列表，若重复值多，导致添加过多的溢出块。 线性散列表，可能导致某些桶为空，而某些桶添加过多的溢出块。 可扩展散列表，可能导致，桶数过多，而真正存储数据的桶，集中在某一桶号。14.3.5a.取低位为桶号标识1111011001111111015 112 3 5 7 11 13 23101111101100

6、200011011211001000200011011211012111110112111010102110110012111110113100000003000001010011100101110111311110111b.由于是线性散列故低位为桶号阀值=75% i=1n=2r=3 i=2n=4r=6310100010310110011 311010101310010001311003111001100 11101 11111101i=2n=3r=600 1110110001 111111011000110001110110 1010111011 11111011000001 1101100

7、1010 10101110011 11111011100 1100i=3n=5r=7000 1000i=3n=6r=12i=3n=7r=12001 1001010 10101110011 11111011100 1100101 11010111000 1000001 1001010 1010011 11111011100 1100101 1101110 011011100111000 1000i=3n=8r=12001 1001010 1010011 1011100 11000100101 11010101110 01101110111 0111111100000001 10010010 10

8、100011 101100110100 110001000101 110101010110 011011100111 011111111000 1000i=4n=9r=13i=4n=10r=1500000001 00010010 101000100011 101100110100 110001000101 110101010110 011011100111 011111111000 10001001 1001i=4n=11r=160000 00000001 00010010 00100011 101100110100 110001000101 110101010110 011011100111

9、 011111111000 10001001 10011010 1010d.线性散列，阀值=100% 0 000000101 00010011i=1n=2r=400 0000010001 0001001110 0010i=2n=3r=60101000 00001000001 00010101010 00100110011 01110011100 010000 0000010001 0001010110 0010011011 01110011i=2n=4r=8i=3n=5r=101001000 00001000001 00011001010 00100110011 01110011100 010

10、0101 0101i=3n=6r=12 10101011000 00001000001 00011001010 00101010011 01110011100 010014.3,7a.标号为 2、3、7、8 的散列表永远为空。b.散列表序列是有规律排列的 1、4、9、0 、9、4、1、0 反复。c.B 为素数时有用。14.3.8a.n=r/ck.b.n=(r*e-xxr/r!)/ck14.3.9最少：1000000/100=10000 （块）每个桶对应五个块最多：。 。 。无想法14.5.5a.5+7=12b.（100,250）和（120,200）1100101 01011101110 0110i=3n=7r=141011000 00001000001 00011001010 00101010011 00111011100 01001100101 01011101110 01101110111 01111111i=3n=8r=