外排所需总的时间为： 外排所需总的时间为：
m*tIS + d*tIO + S*u*tmg = 10*tIS + 500*tIO + 4*10000*tmg
示例： 示例：
• 设有一个包含4500个对象的输入文件。现 设有一个包含4500个对象的输入文件。 个对象的输入文件 用一台其内存至多可容纳750个对象 内存至多可容纳 个对象的计 用一台其内存至多可容纳750个对象的计 算机对该文件进行排序。输入文件放在磁 算机对该文件进行排序。 盘上，磁盘每个页块可容纳250个对象 每个页块可容纳 个对象， 盘上，磁盘每个页块可容纳250个对象， 250＝ 这样全部对象可存储在 4500 / 250＝18 个 页块中。输出文件也放在磁盘上，用以存 页块中。输出文件也放在磁盘上， 放归并结果。 放归并结果。
一、外排序的基本过程
• 当对象以文件形式存放于磁盘上的时候，通常 当对象以文件形式存放于磁盘上的时候， 是按物理块存储的。 是按物理块存储的。 • 物理块也叫做页块，是磁盘存取的基本单位。 物理块也叫做页块，是磁盘存取的基本单位。
• 每个页块可以存放几个对象。操作系统按 每个页块可以存放几个对象。 页块对磁盘上的信息进行读写。 页块对磁盘上的信息进行读写。 • 本节所指的磁盘是由若干片磁盘组成的磁 盘组， 盘组，各个盘片安装在同一主轴上高速旋 转。各个盘面上半径相同的磁道构成了柱 各盘面设置一个读写磁头， 面。各盘面设置一个读写磁头，它们装在 同一动臂上， 同一动臂上，可以径向从一个柱面移到另 一个柱面上。 一个柱面上。
硬盘简介 磁盘的主要技术指标 柱面：多个盘片的同一磁道。 柱面：多个盘片的同一磁道。 目前常见的硬盘容量有 6.2GB、10GB、20GB、 、 、 、 40GB、60GB、80GB等等。 、 等等。 、 等等
第11章 章
外部排序
外排序： 外排序： 在排序过程中必须不断地在内存与 外存之间传送数据， 外存之间传送数据，这种基于外部存储 设备（或文件）的排序技术就是外排序。 设备（或文件）的排序技术就是外排序。
R1
R2
R3
R4
R5
R6
R7
R8
R9
R10
R1’
R2’
R3’
R4’
R5’
R1’’
R2’’
R3’’
R1’’’ 有序文件
R2’’’
假设在上例中每个物理块可以容纳200个 假设在上例中每个物理块可以容纳200个 200 记录，则每一趟归并需进行50 50次 记录，则每一趟归并需进行50次“读” 和“写”，4趟归并加上内部排序时所需 进行的读/写使得在外排序中进行500 500次 进行的读/写使得在外排序中进行500次 的读/ 的读/写。
• 为了访问某一页块，先寻找柱面， 为了访问某一页块，先寻找柱面， 移动臂使读写磁头移到指定柱面上： 移动臂使读写磁头移到指定柱面上： (seek)。 寻查 (seek)。 • 再根据磁道号(盘面号)选择相应读 再根据磁道号(盘面号) 写磁头， 写磁头，等待指定页块转到读写磁 头下：等待(latency)。因此, 头下：等待(latency)。因此, 在磁盘 组上存取一个页块的时间： 组上存取一个页块的时间：
两路归并排序的归并
初始 归并段 第一趟 归并结果 第二趟 归并结果 第三趟 归并结果
R1 750 R2 750 R3 750 R4 750 R5 750 R6 750
R12
1500
R34
1500
R56
1500
R1234
3000
R123456
4500
• 由于内存中可用于排序的存储区域能容 个对象, 因此内存中恰好能存3 纳750 个对象, 因此内存中恰好能存3个页 块的对象。 块的对象。 • 在外归并排序一开始，把18块对象，每3 在外归并排序一开始， 18块对象， 块对象 块一组，读入内存。 块一组，读入内存。利用某种内排序方 法进行பைடு நூலகம்排序, 形成初始归并段, 法进行内排序, 形成初始归并段, 再写回 外存。总共可得到6个初始归并段。 外存。总共可得到6个初始归并段。然后 一趟一趟进行归并排序。 一趟一趟进行归并排序。
当待排序的对象数目特别多时，在内存 当待排序的对象数目特别多时， 中不能一次处理。 中不能一次处理。必须把它们以文件的形式 存放于外存，排序时再把它们一部分一部分 存放于外存， 调入内存进行处理。 调入内存进行处理。
硬盘盘片组
硬盘构成
硬盘简介 盘片组由2 盘片组由2片、 3片、 5片、6片、8 11片 12片组成 片组成， 片、11片、12片组成，相邻片之间有 10 ～20 mm的空隙，以便悬臂磁头平行 mm的空隙 的空隙， 移动。磁盘两面都存有信息， 移动。磁盘两面都存有信息，顶部和底 部两面不存信息。读写数据时， 部两面不存信息。读写数据时，盘片高 速旋转，磁头沿着盘片径向移动。 速旋转，磁头沿着盘片径向移动。
• 第二个阶段把第一阶段生成的 初始归并段加以归并， 初始归并段加以归并，一趟趟 地扩大归并段和减少归并段个 数，直到最后归并成一个大归 并段(有序文件)为止。 并段(有序文件)为止。
例：
• 假设有一个含10000个记录的文件，首先 假设有一个含10000个记录的文件， 10000个记录的文件 通过10次内部排序得到10 10次内部排序得到10个初始归并段 通过10次内部排序得到10个初始归并段 R1～R10，其中每一段都含1000个记录。 1000个记录 R1～R10，其中每一段都含1000个记录。 然后对它们作如下图所示的两两归并， 然后对它们作如下图所示的两两归并， 直至得到一个有序文件为止。 直至得到一个有序文件为止。
• trw
：是数据传送时间，是传送一个页 是数据传送时间， 块数据所需的时间。 块数据所需的时间。
基于磁盘进行的排序多使用归并排 序方法。其排序过程主要分为两个阶段： 序方法。其排序过程主要分为两个阶段：
第一个阶段： 第一个阶段： 建立用于外排序的内存缓冲区。 建立用于外排序的内存缓冲区。
根据它们的大小将输入文件划分为若干段， 根据它们的大小将输入文件划分为若干段， 用某种内排序方法对各段进行排序。 用某种内排序方法对各段进行排序。这些经过 (Run)。 排序的段叫做初始归并段或初始顺串 (Run)。 当它们生成后就被写到外存中去。 当它们生成后就被写到外存中去。
tio＝tseek＋tlatency＋trw
tio＝tseek＋tlatency＋trw
• tseek ：是平均寻查时间，是把磁头定位 是平均寻查时间， 到要求柱面所需时间。 到要求柱面所需时间。
• tlatency ：是平均等待时间，是将磁头 是平均等待时间，
定位到指定页块所需时间。 定位到指定页块所需时间。
物理块/页块 物理块 页块
200个记录 个记录
外部排序所需总的时间 =
内部排序（产生初始归并段） 内部排序（产生初始归并段）所需时间 m*tIS + 外存信息读写的时间d*t 外存信息读写的时间 IO + 内部归并所需的时间S*u*tmg 内部归并所需的时间
tES = m*tIS + d*tIO + S*u*tmg tIS tIO u*tmg m S d
是为得到一个初始归并段进行内部排序所需时 间的均值 是进行一次外存读/ 是进行一次外存读/写时间的均值 是对u 是对u个记录进行内部归并所需时间 为经过内部排序之后得到的初始归并段的个数 为归并的趟数 为总的读/ 为总的读/写次数
上例10000个记录中 个记录中 上例
m=10 d=500 s=4 u=10000