Homework #6 (12.9)
1、固态硬盘(Solid State Drive,SSD)是一种基于闪存的新型存储器,它与传统磁盘的主要区别之一
是:传统磁盘的读写操作的速度相同,而 SSD 的读速度远快于写速度。同时,SSD 的读速度要远高于
磁盘,而写速度则比磁盘慢。现在我们想将传统的两阶段多路归并排序算法移植到 SSD 上。假设 SSD
上一次读块操作的时间是 t,一次写块操作的时间是 50t,磁盘上的读/写块时间是 30t。对于给定关系
R:
• R 包含 100000 个元组,即 T(R) = 100000.
• 一个磁盘块大小为 4000 bytes.
• R 的元组大小为 400 bytes,即 S(R) = 400.
• 关系 R 在磁盘上非连续存放
• 排序字段的大小为 32 bytes.
• 记录指针的大小为 8 bytes.
现在我们考虑下面一种改进的归并排序算法。原来的两阶段归并排序的第一阶段是将排序后的整
个元组写到 chunk 中,现在我们仅将排序后的 <sortingKey, recordPointer> 写出。第一阶段,我们在
内存中将记录按 <sortingKey, recordPointer> 排序,当<sortingKey, recordPointer>记录填满内存时将其
写到 chunk 中。第二阶段,读入各个 chunk 中的 <sortingKey, recordPointer>并在内存中归并。通过记
录指针(recordPointer)我们可以读取记录的其它部分(从 R 的磁盘块中),并将排好序的记录写回到外
存。请回答:
1) 如果 R 存储在磁盘上,这一改进排序算法的 I/O 代价(用 t 的表达式表示,包括最后写出到
排序文件中的代价)是多少?并解释该算法性能是否能优于原来的排序算法。
2) 如果 R 存储在 SSD 上,这一改进排序算法的 I/O 代价(用 t 的表达式表示,包括最后写出到
排序文件中的代价)是多少?并解释该算法性能是否能优于原来的排序算法。
2、我们在课本上讨论的归并排序算法是一个两趟算法。设两个连接关系为 R1 和 R2,在基于两趟归
并排序的排序连接算法中,我们要求内存 M 必须满足条件
2,1max RRM
。现在我们考查关系
R 的两趟归并排序算法,我们发现当内存 M 不满足条件
RM
时,我们仍可以采用一种多趟算法
来完成归并排序操作。请用自然语言或伪码给出这一多趟归并连接算法的简要描述和步骤,并给出当
B(R1)=10000,B(R2)=5000,M = 20 时该算法的 I/O 代价,这里我们假设 R1 和 R2 都不是连续存放的。
䑌
评论0