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 都不是连续存放的。
䑌
