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

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=1075 5000/5+5000/20=1250b.最少的情况，是5000个记录都为重复值，所需块为：5000/5+5000/100+1=1051 最多的情况，是5000个记录都不相同，所需块为：5000/5+5000/100+5000/20=130014.1.6有桶情况下：5000/(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=5 b. 总块数为：1000000/20+1000000/69+(1000000/69)/70+(1000000/69)/70)/20+1= 14493+208+3+1=64705 所需I/O数：层数+1=5 c. 1000000个记录需要1000000/20=50000个存储块 总块数：50000+50000/69+(50000/69)/70+1=50737 所需I/O数:层数+1=4 d. 存储记录所需总块数：1000000/30=33334 总块数为：33334+33334/69+(33334/69)/70+1=33826 所需I/O数:层数+1=4 e. 存储记录所需总块数：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的记录，不引起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所在的节点指针指向键值13所在的叶子节点。i.新的B树如下7511235711132314.2.8题目没看懂。143.2出现重复值的情况时 删除操作，在执行完删除操作后，紧接着执行查找操作，看是否还能找到键值，若能找到则继续删除。 查询操作，可以不用改变。 插入操作，不需要修改。出现重复值，带来的问题 简单散列表，若重复值多，导致添加过多的溢出块。 线性散列表，可能导致某些桶为空，而某些桶添加过多的溢出块。 可扩展散列表，可能导致，桶数过多，而真正存储数据的桶，集中在某一桶号。14.3.5a.取低位为桶号标识 111101100 101 111111101 11110110020001101121101211111011 211001000 211101010211011001200011011211111011 310100010310000000310110011311010101310010001311003000001010011100101110111311110111311100110b.由于是线性散列故低位为桶号阀值=75% 01110111111101i=2n=3r=60011101100011111110110 i=1n=2r=3 00110001110110101011101111111011 0000011101100101010101110011111110111001100 i=2n=4r=6i=3n=5r=7 00010000011001010101011100111111101110011001011101i=3n=6r=12 0111000100000110010101010011111110111001100101110111001101110i=3n=7r=12 0111000100000110010101010011101110011000100101110101011100110111011101111111i=3n=8r=12 0000000110010010101000111011001101001100010001011101010101100110111001110111111110001000i=4n=9r=13 i=4n=10r=150000000100010010101000100011101100110100110001000101110101010110011011100111011111111000100010011001 000000000001000100100010001110110011010011000100010111010101011001101110011101111111100010001001100110101010i=4n=11r=16 d.线性散列，阀值=100% 000000010100010011i=1n=2r=400000001000100010011100010i=2n=3r=60101 00000001000001000101010100010 0110011011100111000100 0000000100010001010110001001101101110011i=2n=4r=8i=3n=5r=101001 00000001000001000110010100010 01100110111001110001001010101i=3n=6r=12 1010101100000001000001000110010100010 10100110111001110001001100101010111011100110 i=3n=7r=14 101100000001000001000110010100010 10100110011101110001001100101010111011100110111011101111111i=3n=8r= 14.3,7a.标号为2、3、7、8的散列表永远为空。b.散列表序列是有