第十二章作业
张配天-2018202180
2020 年 7 月 2 日
12.2
a
由题,假设最多有 k 个入口,则 2
0
+ 2
1
+ · · · + 2
k−1
=
n
F
, 计算得 2
k
=
n
F
+ 1,因此
k = log
n
F
+1
2
b
当总空间为 2
k
− 1 时,未被使用的最大空间为 2
k−1
− 1。
12.7
考虑硬盘读取数据的位置,最佳情况和最差情况均需要移动磁头,因此 25ms 不变,区
别在于最佳情况为要查询数据在数据区的第一个位置且无需旋转延迟,最差情况为磁盘需
要转一圈且查询数据位于最后的数据块。
• 最小时间 =25+0.25=25.25ms
• 最大时间 =25+2.5*2+0.25*100=55ms
• 平均时间 =
25.25+55
2
=40.125ms
12.12
使用二级索引可以减小平均查找开销。如果只使用一级索引,则查找的开销为 500 万,
使用二级索引,开销为 50 + 5000 = 5050,提升了访问速度。
1
评论0