节文件管理和外排序

1、为什么需要文件管理和外排序？为什么需要文件管理和外排序？ n文件结构文件结构( file structure ) n对于在外存中存储的数据，其数据结构就称对于在外存中存储的数据，其数据结构就称 为文件结构为文件结构( file structure ) n数据量太大不可能同时把它们放到内存中数据量太大不可能同时把它们放到内存中 n需要把全部数据放到磁盘中需要把全部数据放到磁盘中 n文件的各种运算文件的各种运算 n外排序是针对磁盘文件所进行的外排序是针对磁盘文件所进行的排序操作排序操作 n提高文件存储效率和运算效率提高文件存储效率和运算效率 本章的安排顺序本章的安排顺序 n8.1 介绍主存和外存的

2、根本差异介绍主存和外存的根本差异 n8.2 在外存中文件的组织方式在外存中文件的组织方式 n8.3 管理缓冲池的基本方法管理缓冲池的基本方法 n8.4 外排序的基本算法外排序的基本算法 主存储器和外存储器主存储器和外存储器 n主存储器主存储器( primary memory或者或者main memory ， 简称简称“内存内存”，或者，或者“主存主存”) n随机访问存储器随机访问存储器( Random Access Memory, 即即RAM ) n高速缓存高速缓存( cache ) n视频存储器视频存储器( video memory ) 。 n外存储器外存储器(peripheral stor

3、age或者或者secondary storage，简称，简称“外存外存”) n硬盘硬盘 n软盘软盘 n磁带磁带 主存储器和外存储器主存储器和外存储器 之价格比较之价格比较 介质介质 2001年底年底 价格价格 2002年底年底 价格价格 2003年早年早 期价格期价格 内存内存11.51 硬盘硬盘0.0170.0130.011 软盘软盘1272.5 磁带磁带0.0080.0110.0075 外存的优缺点外存的优缺点 n优点：优点：永久存储能力、便携性永久存储能力、便携性 n缺点：访问时间长缺点：访问时间长 n访问磁盘中的数据比访问内存慢五六访问磁盘中的数据比访问内存慢五六 个数量级个数量级。

4、n所以讨论在外存的数据结构及其上所以讨论在外存的数据结构及其上 的操作时，必须遵循下面这个重要的操作时，必须遵循下面这个重要 原则：原则： n尽量减少访外次数！尽量减少访外次数！ 磁盘的物理结构磁盘的物理结构 磁盘盘片的组织磁盘盘片的组织 磁盘存取步骤磁盘存取步骤 n选定某个盘片组选定某个盘片组 n选定某个柱面选定某个柱面 n这需要把磁头移动到该柱面这需要把磁头移动到该柱面 ，这个移动过程称这个移动过程称 为寻道为寻道( seek ) n确定磁道确定磁道 n确定所要读写的数据在磁盘上的准确位置确定所要读写的数据在磁盘上的准确位置 n这段时间一般称为旋转延迟这段时间一般称为旋转延迟( rotat

5、ional delay ( rotational delay 或者或者rotational latency )rotational latency ) n真正进行读写真正进行读写 磁盘磁道的组织磁盘磁道的组织（交错法）（交错法） （a a）没有扇区交错；（）没有扇区交错；（b b）以）以3 3为交错因子为交错因子 磁盘访问时间估算磁盘访问时间估算 n磁盘访问时间主要由磁盘访问时间主要由寻道时间、旋转延寻道时间、旋转延 迟时间和数据传输时间组成。迟时间和数据传输时间组成。 n寻道时间（寻道时间（Seek time）：是）：是移动磁盘臂，移动磁盘臂， 定位到正确磁道所需的时间。定位到正确磁道所需的

6、时间。 n旋转延迟时间：是旋转延迟时间：是等待被存取的扇区出等待被存取的扇区出 现在读写头下所需的时间。现在读写头下所需的时间。 总存取时间总存取时间(1) （1 1）数据连续存放，而且给出了平均寻道时间。）数据连续存放，而且给出了平均寻道时间。 总存取时间总存取时间 = = 平均寻道时间平均寻道时间 + + 第一道读取时间第一道读取时间 + ( + (总磁道数总磁道数1)1) (第二次寻道时间第二次寻道时间)+()+(读取整读取整 道的时间道的时间) = = 平均寻道时间平均寻道时间 + (0.5 + (0.5圈延迟圈延迟+ +交错因子交错因子) ) 每圈所花时间每圈所花时间 + ( + (

7、总磁道数总磁道数1) 1) 磁道转换时间磁道转换时间+(0.5圈延迟圈延迟+交错因子交错因子) 每圈每圈 所花时间所花时间 总存取时间总存取时间(2) （2）数据随机存放数据随机存放 。 总存取时间总存取时间 = = 簇数簇数 平均寻道时平均寻道时 间间+旋转延迟旋转延迟+读一簇时间读一簇时间 = = 簇数簇数 平均寻道时间平均寻道时间 + 0.5 + 0.5圈延迟圈延迟 每圈所花时间每圈所花时间 + 交错因子交错因子 （每簇扇区数（每簇扇区数/每道扇区数）每道扇区数） 每圈时间每圈时间 n例例8.1 假定一个磁盘总容为假定一个磁盘总容为 16.8GB，分布在，分布在10个盘片上。每个盘片上。

8、每 个盘片上有个盘片上有13085个磁道，每个磁个磁道，每个磁 道中包含道中包含256个扇区，每个扇区个扇区，每个扇区 512个字节，每个簇个字节，每个簇8个扇区。扇区个扇区。扇区 的交错因子是的交错因子是3。磁盘旋转速率是。磁盘旋转速率是 5400 rpm，磁道转换时间是，磁道转换时间是2.2 ms，随机访问的平均寻道时间是，随机访问的平均寻道时间是 9.5 ms。 n如果读取一个如果读取一个1MB的文件，该文件的文件，该文件 有有2048个记录，每个记录有个记录，每个记录有512字字 节（节（1个扇区）。对于以下两种情况，个扇区）。对于以下两种情况， 估算进行文件处理的总时间。估算进行文件

9、处理的总时间。 n（1）假定所有记录在）假定所有记录在8个连续磁道上；个连续磁道上； n（2）假定文件簇随机地散布在磁盘上。）假定文件簇随机地散布在磁盘上。 解：我们先总结出一些共有的特性解：我们先总结出一些共有的特性 n每个簇为每个簇为4KB n8个扇区个扇区 512 byets 8 4KB n每个磁道有每个磁道有32簇簇 n 256个扇区个扇区 256 扇区扇区 8（扇区（扇区/簇）簇） = 32个簇个簇 n每个盘片有每个盘片有1.68GB n16.8GB 10 = 1.68GB n每转一圈的时间为每转一圈的时间为11.1ms n(601000)ms/5400圈圈 = 11.1（ms/圈）

10、圈）= 11.1（ms/道）道） n一个磁道是一个整圈，因此，下面计算公式中，所一个磁道是一个整圈，因此，下面计算公式中，所 用的单位用的单位“圈圈”等同于等同于“道道” n 数据连续存放，而且给出了平均寻道时间。数据连续存放，而且给出了平均寻道时间。 总存取时间总存取时间 = 平均寻道时间平均寻道时间 + (0.5圈延迟圈延迟+交错因子交错因子) 每圈所花时间每圈所花时间 + (总磁道数总磁道数1) 磁道转换时间磁道转换时间+(0.5圈延迟圈延迟+交错因子交错因子) 每每 圈所花时间圈所花时间 = 9.5ms（平均寻道时间）（平均寻道时间） + (0.5（半圈旋转延迟）（半圈旋转延迟） +

11、3（交错因（交错因 子）子）) 11.1ms/圈圈 +（8-1）个其他磁道）个其他磁道 2.2ms磁道转换时间磁道转换时间+(0.5圈延迟圈延迟+3交错交错 因子因子) 11.1ms/圈圈 = 9.5ms + 38.9ms + 7 41.1ms = 336.1ms n 数据随机存放数据随机存放 n总簇数：总簇数：8个磁道个磁道 32(簇簇/磁道磁道) = 256簇簇 总存取时间总存取时间 = 簇数簇数 平均寻道时间平均寻道时间 + 0.5圈延迟圈延迟 每圈所花时间每圈所花时间 + 交错因子交错因子 （每簇扇区数（每簇扇区数/每道扇区数）每道扇区数） 每圈时间每圈时间 = 256 9.5ms（平

12、均寻道时间）（平均寻道时间） + 0.5（半圈旋转延迟）（半圈旋转延迟） 11.1ms/圈圈 + 3(交错因子交错因子) 8(扇区扇区/簇簇/) 256(扇区扇区/ 道道) 11.1ms/圈圈 256 9.5 + 5.55 + 1.04ms 4119.04ms n读一簇的时间读一簇的时间 n9.5ms(平均寻道时间平均寻道时间)+0.5(半圈旋转延半圈旋转延 迟迟) 11.1ms/圈圈+1扇区扇区 256(扇区扇区/道道) 11.1ms/ 圈圈 9.5 + 5.55 + 1.04= 16.09ms n定位后，实际读一簇数据的时间定位后，实际读一簇数据的时间 n3(交错因子交错因子) 8(扇区扇

13、区/簇簇/) 256(扇区扇区/道道) 11.1ms/圈圈 1.04ms n读一个字节的时间读一个字节的时间 n9.5ms(平均寻道时间平均寻道时间)+0.5(半圈旋转延半圈旋转延 迟迟) 11.1ms/圈圈 15.05ms n“一次访外一次访外”操作操作 n磁盘一次磁盘一次I/O操作访问一个扇区，通常称为访问操作访问一个扇区，通常称为访问“一一 页页”（page），或者），或者“一块一块”(block) 磁带磁带 n主要优点主要优点 ：使用方便、价格便使用方便、价格便 宜、容量大、所存储的信息比宜、容量大、所存储的信息比磁磁 盘和光盘更持久盘和光盘更持久 n缺点：缺点：速度较慢，只能进行顺序

14、速度较慢，只能进行顺序 存取存取 磁带运行示意图磁带运行示意图 磁带卷在一个卷盘上，运行时磁带经过读磁带卷在一个卷盘上，运行时磁带经过读 写磁头，把磁带上的信息读入计算机，或写磁头，把磁带上的信息读入计算机，或 把计算机中的信息写在磁带上把计算机中的信息写在磁带上。 磁带发展史磁带发展史 n手工手工阶段阶段 n自动化磁带库系统自动化磁带库系统 n虚拟磁带技术虚拟磁带技术 外存文件的组织外存文件的组织 职工号职工号姓名姓名性别性别职务职务 婚姻状况婚姻状况工资工资 156张东张东男男程序员程序员未婚未婚7800 860李珍李珍女女分析员分析员已婚已婚8900 510赵莉赵莉女女程序员程序员未婚未

15、婚6900 950陈萍陈萍女女程序员程序员未婚未婚6200 620周力周力男男分析员分析员已婚已婚10300 n文件是一些记录的汇集，其中每个记录由一个或多文件是一些记录的汇集，其中每个记录由一个或多 个数据项组成。个数据项组成。 n数据项有时也称为字段，或者称为属性。例如，一数据项有时也称为字段，或者称为属性。例如，一 个职工文件里的记录可以包含下列数据项：职工号，个职工文件里的记录可以包含下列数据项：职工号， 姓名，性别，职务，婚姻状况，工资等。姓名，性别，职务，婚姻状况，工资等。 文件组织文件组织 n逻辑文件逻辑文件 n对高级程序语言的编程人员而言，存储在磁盘中可对高级程序语言的编程人员

16、而言，存储在磁盘中可 以随机访问的文件被当作一段连续的字节，而且可以随机访问的文件被当作一段连续的字节，而且可 以把这些字节结合起来构成记录，这种文件被称为以把这些字节结合起来构成记录，这种文件被称为 逻辑文件逻辑文件( logical file )。 n物理文件物理文件 n实际存储在磁盘中的物理文件实际存储在磁盘中的物理文件( physical file )( physical file ) 通常不是一段连续的字节，而是成块地分布在整个通常不是一段连续的字节，而是成块地分布在整个 磁盘中。磁盘中。 n文件管理器文件管理器 n是操作系统的一部分，当应用程序请求从逻辑文件是操作系统的一部分，当应

17、用程序请求从逻辑文件 中读解数据时，它把这些逻辑位置映射为磁盘中具中读解数据时，它把这些逻辑位置映射为磁盘中具 体的物理位置。体的物理位置。 文件的逻辑结构文件的逻辑结构 n文件是记录的汇集文件是记录的汇集。 n当一个文件的各个记录按照某种次序当一个文件的各个记录按照某种次序 排列起来时，各纪录间就自然地形成排列起来时，各纪录间就自然地形成 了一种线性关系。了一种线性关系。 n因而，文件可看成是一种线性结构。因而，文件可看成是一种线性结构。 文件的存储结构文件的存储结构 n顺序结构顺序结构顺序文件顺序文件 n计算寻址结构计算寻址结构散列文件散列文件 n带索引的结构带索引的结构带索引文件带索引文

18、件 文件上的操作文件上的操作 n检索检索：在文件中寻找满足一定条件的记录在文件中寻找满足一定条件的记录 n修改：是指对记录中某些数据值进行修改。若修改：是指对记录中某些数据值进行修改。若 对关键码值进行修改，这相当于删除加插入。对关键码值进行修改，这相当于删除加插入。 n插入插入：向文件中增加一个新记录。向文件中增加一个新记录。 n删除：从文件中删去一个记录删除：从文件中删去一个记录 。 n排序排序 ：对指定好的数据项，按其值的大小把对指定好的数据项，按其值的大小把 文件中的记录排成序列，较常用的是按关键码文件中的记录排成序列，较常用的是按关键码 值的排序。值的排序。 C的流文件的流文件 nC

19、+程序员对随机访问文件的逻辑视图程序员对随机访问文件的逻辑视图 是一个单一的字节流，即字节数组。是一个单一的字节流，即字节数组。 n程序员需要管理标志文件当前位置的文程序员需要管理标志文件当前位置的文 件指针。件指针。 n常见的三个基本文件操作，都是围绕文常见的三个基本文件操作，都是围绕文 件指针进行的：件指针进行的： n把文件指针设置到指定位置（移动文件指针）把文件指针设置到指定位置（移动文件指针） n从文件的当前位置读取字节从文件的当前位置读取字节 n向文件中的当前位置写入字节向文件中的当前位置写入字节 C操作二进制文件的常操作二进制文件的常 用方式用方式fstream类类 nfstrea

20、m类提供函数操作可随机类提供函数操作可随机 访问的磁盘文件中的信息。访问的磁盘文件中的信息。 nfstream类的主要成员函数包括类的主要成员函数包括 open，close，read，write， seekg，seekp。 fstream类的主要函数成员类的主要函数成员 #include/fstream=ifstream+ofstream#include/fstream=ifstream+ofstream / / 打开文件进行处理。打开文件进行处理。 / / 模式示例模式示例: ios:in | ios:binary: ios:in | ios:binary void fstream:open

21、(charvoid fstream:open(char* * name, openmode mode); name, openmode mode); / 处理结束后关闭文件。处理结束后关闭文件。 void fstream:close(); ftream类的主要函数成员（续类的主要函数成员（续1） / / 从文件当前位置读入一些字节。从文件当前位置读入一些字节。 / / 随着字节的读入，文件当前位置向前移动。随着字节的读入，文件当前位置向前移动。 fstream:read(charfstream:read(char* * ptr, int numbytes); ptr, int numbytes

22、); / / 向文件当前位置写入一些字节向文件当前位置写入一些字节 / (/ (覆盖已经在这些位置的字节覆盖已经在这些位置的字节) )。 / / 随着字节的写入，文件当前位置向前移动。随着字节的写入，文件当前位置向前移动。 fstream:write(charfstream:write(char* * ptr, int numbtyes); ptr, int numbtyes); ftream类的主要函数成员（续类的主要函数成员（续2） / seekg和和seekp：在文件中移动当前位置，：在文件中移动当前位置， / 这样就可以在文件中的任何一个位置这样就可以在文件中的任何一个位置 / 读出或

23、写入字节。读出或写入字节。 / 实际上有两个当前位置，实际上有两个当前位置， /一个用于读出，另一个用于写入。一个用于读出，另一个用于写入。 / 函数函数seekg用于改变读出位置，用于改变读出位置， / 函数函数seekp用于改变写入位置用于改变写入位置 fstream:seekg(int pos); / fstream:seekg(int pos); / 处理输入处理输入 fstream:seekg(int pos, ios:curr);fstream:seekg(int pos, ios:curr); fstream:seekp(int pos); / fstream:seekp(int

24、 pos); / 处理输出处理输出 fstream:seekp(int pos, ios:end); 缓冲缓冲 n目的：减少磁盘访问次数的目的：减少磁盘访问次数的 n方法：缓冲方法：缓冲( buffering )或缓存或缓存 ( caching ) n在内存中保留尽可能多的块在内存中保留尽可能多的块 n可以增加待访问的块已经在内存中的可以增加待访问的块已经在内存中的 机会，因此就不需要访问磁盘机会，因此就不需要访问磁盘 缓冲区和缓冲池缓冲区和缓冲池 n存储在一个缓冲区中的信息经常存储在一个缓冲区中的信息经常 称为一页称为一页( page )，往往是一次，往往是一次 I/O的量的量 n缓冲区合起

25、来称为缓冲池缓冲区合起来称为缓冲池 ( buffer pool ) 替换缓冲区块的策略替换缓冲区块的策略 n“先进先出先进先出”(FIFO) n“最不频繁使用最不频繁使用”(LFU) n“最近最少使用最近最少使用”(LRU) 虚拟存储虚拟存储 ( virtual memory ) n虚拟存储使得程序员能够使用比虚拟存储使得程序员能够使用比 实际内存更大的内存空间实际内存更大的内存空间。 n磁盘中存储虚拟存储器的全部的磁盘中存储虚拟存储器的全部的 内容，根据存储器的访问需要把内容，根据存储器的访问需要把 块读入内存缓冲池。块读入内存缓冲池。 虚拟存储虚拟存储 n系统运行到某一时刻，虚拟地址空间中

26、有系统运行到某一时刻，虚拟地址空间中有5个页被读入到物个页被读入到物 理内存中，现在如果需要对地址为理内存中，现在如果需要对地址为24k-28k的页进行访问，的页进行访问， 就必须替换掉当前物理内存中的一个页框。就必须替换掉当前物理内存中的一个页框。 外排序外排序 n外排序外排序( external sort ) n外存设备上外存设备上(文件文件)的排序技术的排序技术 n由于文件很大，无法把整个文件由于文件很大，无法把整个文件 的所有记录同时调入内存中进行的所有记录同时调入内存中进行 排序，即无法进行内排序排序，即无法进行内排序 n外部排序算法的主要目标是尽量外部排序算法的主要目标是尽量 减少

27、读写磁盘的次数减少读写磁盘的次数 关键码索引排序关键码索引排序 n索引文件索引文件( index file )( index file )中中 n关键码与指针一起存储关键码与指针一起存储 n指针标识相应记录在原数据文件中的位置指针标识相应记录在原数据文件中的位置 n对索引文件进行排序，所需要的对索引文件进行排序，所需要的I/OI/O操作操作 更少更少 n索引文件比整个数据文件小很多。索引文件比整个数据文件小很多。 n在一个索引文件中，只针对关键码排序在一个索引文件中，只针对关键码排序 ( key sort )( key sort )。 磁盘排序过程磁盘排序过程 n顺串：顺串：用某种有效的内排序

28、方法对文用某种有效的内排序方法对文 件的各段进行初始排序，这些经过排件的各段进行初始排序，这些经过排 序的段通常称为顺串序的段通常称为顺串( run ) ，它们生，它们生 成之后立即被写回到外存上。成之后立即被写回到外存上。 磁盘排序过程：磁盘排序过程： n文件分成若干尽可能长的初始顺串；文件分成若干尽可能长的初始顺串； n逐步归并顺串归，最后形成一个已排逐步归并顺串归，最后形成一个已排 序的文件。序的文件。 置换选择排序置换选择排序 n采用置换选择算法，在扫描一遍采用置换选择算法，在扫描一遍 的前提下，使得所生成的各个顺的前提下，使得所生成的各个顺 串有更大的长度。串有更大的长度。这样减少了

29、初这样减少了初 始顺串的个数，有利于在合并时始顺串的个数，有利于在合并时 减少对数据的扫描遍数。减少对数据的扫描遍数。 置换选择算法置换选择算法 n假设外排序算法可以使用一个输入缓冲假设外排序算法可以使用一个输入缓冲 区、一个输出缓冲区、一个能存放区、一个输出缓冲区、一个能存放M个个 记录的记录的RAM内存块（可以看成大小为内存块（可以看成大小为M 的连续数组）。排序操作可以利用缓冲的连续数组）。排序操作可以利用缓冲 区，但只能在区，但只能在RAM中进行。中进行。 n平均情况下，这种算法可以创建长度为平均情况下，这种算法可以创建长度为 2M2M个记录的顺串。个记录的顺串。 置换选择方法图示置换

30、选择方法图示 处理过程为：从输入文件读取记录（一整块磁盘中处理过程为：从输入文件读取记录（一整块磁盘中 所有记录），进入输入缓冲区；然后在所有记录），进入输入缓冲区；然后在RAM中放入中放入 待排序记录；记录被处理后，写回到输出缓冲区；待排序记录；记录被处理后，写回到输出缓冲区； 输出缓冲区写满的时候，把整个缓冲区写回到一个输出缓冲区写满的时候，把整个缓冲区写回到一个 磁盘块。当输入缓冲区为空时，从磁盘输入文件读磁盘块。当输入缓冲区为空时，从磁盘输入文件读 取下一块记录。取下一块记录。 置换选择算法置换选择算法 1.1. 初始化堆：初始化堆： (a)(a) 从磁盘读从磁盘读M M个记录放到数组

31、个记录放到数组RAMRAM中。中。 (b)(b) 设置堆末尾标准设置堆末尾标准LAST LAST M M 1 1。 (c)(c) 建立一个最小值堆。建立一个最小值堆。 置换选择算法（续）置换选择算法（续） 2.2. 重复以下步骤，直到堆为空（即重复以下步骤，直到堆为空（即LAST 0LAST 0）：）： (a) (a) 把具有最小关键码值的记录把具有最小关键码值的记录( (根结点根结点) )送到输出缓送到输出缓 冲区。冲区。 (b) (b) 设设R R是输入缓冲区中的下一条记录。如果是输入缓冲区中的下一条记录。如果R R的关键的关键 码值大于刚刚输出的关键码值码值大于刚刚输出的关键码值 i.

32、i. 那么把那么把R R放到根结点。放到根结点。 ii. ii. 否则使用数组中否则使用数组中LASTLAST位置的记录代替位置的记录代替 根结点，然后把根结点，然后把R R放到放到LASTLAST位置。设置位置。设置LAST LAST LAST LAST 1 1。 (c)(c)重新排列堆，筛出根结点。重新排列堆，筛出根结点。 置换选择示例（置换选择示例（1 1） 置换选择示例（置换选择示例（2 2） 置换选择示例（置换选择示例（3 3） 置换选择算法的实现置换选择算法的实现 /置换选择算法置换选择算法 /模板参数模板参数ElemElem代表数组中每一个元素的类型代表数组中每一个元素的类型 /

33、A/A是从外存读入是从外存读入n n个元素后所存放的数组，个元素后所存放的数组，n n是数组是数组 元素的个数元素的个数 /in/in和和outout分别是输入和输出文件名分别是输入和输出文件名 template template void replacementSelection(Elem void replacementSelection(Elem * * A, int n, A, int n, const char const char * * in, const char in, const char * * out) out) 置换选择算法的实现（续置换选择算法的实现（续1） Ele

34、m mval; /Elem mval; /存放最小值堆的最小值存放最小值堆的最小值 Elem r; /Elem r; /存放从输入缓冲区中读入的元素存放从输入缓冲区中读入的元素 /输入、输出文件句柄输入、输出文件句柄 FILE FILE * * inputFile; inputFile; FILE FILE * * outputFile; outputFile; /输入、输出输入、输出bufferbuffer Buffer input;Buffer input; Buffer output;Buffer output; /初始化输入输出文件初始化输入输出文件 initFiles(inputFi

35、le, outputFile, in, out);initFiles(inputFile, outputFile, in, out); 置换选择算法的实现（续置换选择算法的实现（续2） / /* * * * * * * * * * * 算法主体部分算法主体部分 * * * * * * * * * * * */ / /初始化堆的数据，初始化堆的数据， / 从磁盘文件读入从磁盘文件读入n n个数据置入数组个数据置入数组A A initMinHeapArry(inputFile, n, A);initMinHeapArry(inputFile, n, A); /建立最小值堆建立最小值堆 MinHea

36、p H(A, n, n); MinHeap H(A, n, n); 置换选择算法的实现（续置换选择算法的实现（续3） /初始化初始化input bufferinput buffer，读入一部分数据，读入一部分数据 initInputBuffer(input, inputFile); for(int last = (n-1); last = 0;)for(int last = (n-1); last = 0;) /堆不为空，就做这个循环堆不为空，就做这个循环 mval = H.heapArray0; /mval = H.heapArray0; /堆的最小值堆的最小值 /把把mvalmval送到输

37、出缓冲区，送到输出缓冲区， /同时处理因缓冲区空或满造成的各种情形同时处理因缓冲区空或满造成的各种情形 sendToOutputBuffer(input, output, inputFile, sendToOutputBuffer(input, output, inputFile, outputFile, mval);outputFile, mval); 置换选择算法的实现（续置换选择算法的实现（续4） input.read(r); /从输入缓冲区读入一个记录从输入缓冲区读入一个记录 if(!less(r, mval) /若若r的关键码值大于等于刚才输出缓冲区记录的关键码值，的关键码值大于等于

38、刚才输出缓冲区记录的关键码值， /把把r放到根结点放到根结点 H.heapArray0 = r; else /否则用否则用last位置的记录代替根结点，把位置的记录代替根结点，把r放到放到last位置位置 H.heapArray0 = H.heapArraylast; H.heapArraylast = r; H.setSize(last); last-; 置换选择算法的实现（续置换选择算法的实现（续5） H.SiftDown(0); /把根结点记录下降到合适把根结点记录下降到合适 的位置的位置 /for /for /算法结束工作：算法结束工作： /处理输出缓冲区，输入处理输出缓冲区，输入/

39、/输出文件输出文件 endUp(output, inputFile, outputFile);endUp(output, inputFile, outputFile); 置换选择算法的效果置换选择算法的效果 如果堆的大小是如果堆的大小是M n一个顺串的最小长度就是一个顺串的最小长度就是M个记录个记录 n至少原来在堆中的那些记录将成为顺至少原来在堆中的那些记录将成为顺 串的一部分串的一部分 n最好的情况下，例如输入已经被排最好的情况下，例如输入已经被排 序，有可能一次就把整个文件生成序，有可能一次就把整个文件生成 为一个顺串。为一个顺串。 扫雪机模型扫雪机模型 n扫雪机模型显示扫雪机在环绕一圈过

40、程中的行为扫雪机模型显示扫雪机在环绕一圈过程中的行为。根根 据据“扫雪机扫雪机”模型的分析，可以预计平均情况下顺串模型的分析，可以预计平均情况下顺串 总长度是数组长度的两倍。总长度是数组长度的两倍。 二路外排序二路外排序 n归并原理：归并原理：把第一阶段所生成的把第一阶段所生成的 顺串加以合并顺串加以合并(例如通过若干次例如通过若干次 二路合并二路合并)，直至变为一个顺串，直至变为一个顺串 为止，即形成一个已排序的文件。为止，即形成一个已排序的文件。 二路归并外排序二路归并外排序 多路归并多路归并 三路归并三路归并 选择树选择树 n在在K路归并中，最直接的方法就是作路归并中，最直接的方法就是作

41、K-1 次比较来找出所要的记录，但这样做花次比较来找出所要的记录，但这样做花 的代价较大，我们采用选择树的方法来的代价较大，我们采用选择树的方法来 实现实现K路归并。路归并。 n选择树是完全二叉树，有两种类型：赢选择树是完全二叉树，有两种类型：赢 者树和败方树。者树和败方树。 赢者树赢者树 n叶子节点用数组叶子节点用数组L L表示表示 n代表各顺串在合并过程中的当前记录（图中标代表各顺串在合并过程中的当前记录（图中标 出了它们各自的关键码值）；出了它们各自的关键码值）； n分支节点用数组分支节点用数组B B表示表示 n每个分支节点代表其两个儿子结点中的赢者每个分支节点代表其两个儿子结点中的赢者

42、 ( (关键码值较小的关键码值较小的) )所对应数组所对应数组L L的索引。的索引。 n因此，根结点是树中的最终赢者的索引，因此，根结点是树中的最终赢者的索引， 即为下一个要输出的记录结点。即为下一个要输出的记录结点。 赢者树示例（赢者树示例（1） 根结点所指向的根结点所指向的L4记录具有最小的关键码值记录具有最小的关键码值6，它所指的记，它所指的记 录是顺串录是顺串4的当前记录，该记录即为下一个要输出的记录。的当前记录，该记录即为下一个要输出的记录。 赢者树示例（赢者树示例（2） 重构后的赢者树，改动的节点用较粗的框显示出来重构后的赢者树，改动的节点用较粗的框显示出来。为了重构这为了重构这

43、颗树，只须沿着从结点颗树，只须沿着从结点L4到根结点的路径重新进行比赛。到根结点的路径重新进行比赛。 赢者树赢者树ADT template class WinerTree public: Create(); /创建一个空的赢者树创建一个空的赢者树 Iitialize(T a, int n); /返回比赛的赢者返回比赛的赢者 Replay(i); /选手选手i变化时，重建赢者树变化时，重建赢者树 ; 赢者树与数组的对应关系赢者树与数组的对应关系 外部节点的数目为外部节点的数目为n，LowExt代表最底层的外部节点数目代表最底层的外部节点数目 ； offset代表最底层外部节点之上的所有节点数目代

44、表最底层外部节点之上的所有节点数目 。每一个外每一个外 部节点部节点Li所对应的内部节点所对应的内部节点Bp，i和和p之间存在如下的关之间存在如下的关 系：系： p = LowExtinLowExti LowExtioffseti 2/) 1( 2/)( 赢者树的类定义赢者树的类定义 template class WinnerTree private: int MaxSize; /允许的最大选手数允许的最大选手数 int n; /当前大小当前大小 int LowExt; /最低层的外部节点数最低层的外部节点数 int offset; /2s+11 int * B; /内部节点数组内部节点数组

45、T * L; /外部节点数组外部节点数组 void Play(int p, int lc, int rc, int(* winner)(T A, int b, int c); 赢者树的类定义（续）赢者树的类定义（续） public: WinnerTree(int Treesize = MAX); WinnerTree()delete B; void Initialize(T A, int size,int (*winner)(T A, int b, int c); /初始化赢者树初始化赢者树 int Winner();/返回最终胜者的索引返回最终胜者的索引 void RePlay(int i,

46、 int(*winner)(T A, int b, int c); /位置位置i的外部选手改变后重的外部选手改变后重构赢者树构赢者树 ; 败方树败方树 n所谓败方树就是在选择所谓败方树就是在选择 (比赛比赛)树树 中，每个非叶结点均存放其两个中，每个非叶结点均存放其两个 子结点中的败方所对应叶子节点子结点中的败方所对应叶子节点 的索引值。的索引值。 n此外，还另加进一个结点，即结此外，还另加进一个结点，即结 点点B0，以代表比赛的全局获胜，以代表比赛的全局获胜 者的索引值者的索引值。 败方树比赛过程败方树比赛过程 n将新进入树的结点与其父结点进行将新进入树的结点与其父结点进行 比赛比赛 n把败

47、者存放在父结点中把败者存放在父结点中 n而把胜者再与上一级的父结点进行比而把胜者再与上一级的父结点进行比 赛赛 n这样的比赛不断进行，直到结点这样的比赛不断进行，直到结点B1 处比完处比完 n把败者的索引放在结点把败者的索引放在结点B1 n把胜者的索引放到结点把胜者的索引放到结点B0 败方树示例（败方树示例（1） 败方树示例（败方树示例（2）：）： L4节点节点15进入进入 后做重构后做重构 败方树败方树 ADT template class LoserTree private: int MaxSize; /最大选手数最大选手数 int n; /当前选手数当前选手数 int LowExt;/最

48、底层外部节点数最底层外部节点数 int offset;/最底层外部节点之上的节点总数最底层外部节点之上的节点总数 int * B;/赢者树数组，实际存放的是下标赢者树数组，实际存放的是下标 T * L; /元素数组元素数组 void Play(int p, int lc, int rc, int(* winner)(T A, int b, int c); 败方树败方树ADT（续）（续） public: LoserTree(int Treesize = MAX); LoserTree()delete B; void Initialize(T A, int size,int (*winner)(T

49、 A, int b, int c), int(*loser)(T A, int b, int c); /初始化败方树初始化败方树 int Winner(); /返回最终胜者索引返回最终胜者索引 /位置位置i的选手改变后重构败方树的选手改变后重构败方树 void RePlay(int i, int(*winner)(T A, int b, int c), int (*loser)(T A, int b, int c); 败方树的实现败方树的实现 /构造函数构造函数 template LoserTree:LoserTree(int TreeSize) MaxSize = TreeSize; B =

50、 new intMaxSize; n = 0; /析构函数析构函数 template LoserTree:LoserTree() delete B; 败方树的实现（续败方树的实现（续1） /成员函数成员函数Winner，返回最终胜者的索引，返回最终胜者的索引 /在败方树中这个索引存放在在败方树中这个索引存放在B0中中 template int LoserTree:Winner() return (n)?B0:0; 败方树的实现（续败方树的实现（续2） /成员函数成员函数Initilalize负责初始化败方树负责初始化败方树 template void LoserTree:Initialize(

51、T A, int size, int(*winner)(T A, int b, int c), int(*loser)(T A, int b, int c) /能否处理能否处理size个选手的数组个选手的数组a if(size MaxSize | size 2) coutBad Input!endlendl; return; 败方树的实现（续败方树的实现（续3） /初始化成员变量初始化成员变量 n = size; L = A; /计算计算s=2log(n-1) int i,s; for(s = 1; 2*s = n-1; s+=s); LowExt = 2*(n-s); offset = 2*

52、s-1; 败方树的实现（续败方树的实现（续4） /最底层外部结点的比赛最底层外部结点的比赛 for(i = 2; i = LowExt; i+=2) Play(offset+i)/2, i-1, i, winner, loser); /处理其余外部结点处理其余外部结点 if(n%2)/n为奇数，内部结点和外部结点比赛为奇数，内部结点和外部结点比赛 /这里用这里用LLowExt+1和它的父结点比赛和它的父结点比赛 /因为此时它的父结点中存放的是因为此时它的父结点中存放的是 /其兄弟结点处的比赛胜者索引其兄弟结点处的比赛胜者索引 Play(n/2, B(n-1)/2, LowExt+1, winn

53、er, loser); i = LowExt+3; else i = LowExt+2; 败方树的实现（续败方树的实现（续5） /剩余外部结点的比赛剩余外部结点的比赛 for(; i=n; i+=2) Play(i-LowExt+n-1)/2, i-1, i, winner, loser); 败方树的实现（续败方树的实现（续6） /成员函数成员函数Play负责在内部结点负责在内部结点Bp处开始比赛处开始比赛 template void LoserTree:Play(int p, int lc, int rc, int(* winner)(T A, int b, int c), int(* lo

54、ser)(T A, int b, int c) Bp = loser(L, lc, rc);/败者索引放在败者索引放在Bp中中 int temp1, temp2; temp1 = winner(L, lc, rc);/p处的胜者索引处的胜者索引 败方树的实现（续败方树的实现（续7） while(p1 /败者索引放入败者索引放入Bp/2 Bp/2 = loser(L, temp1, Bp/2); temp1 = temp2; p/=2; /while 败方树的实现（续败方树的实现（续8） /结束循环结束循环(Bp是左孩子，或者是左孩子，或者B1)之后，之后， /在在Bp的父结点写入胜者索引的父结

55、点写入胜者索引 Bp/2 = temp1; 败方树的实现（续败方树的实现（续9） /成员函数成员函数RePlay负责选手负责选手i的值改变后重新开始比赛的值改变后重新开始比赛 template void LoserTree:RePlay(int i, int (*winner)(T A, int b, int c), int (*loser)(T A, int b, int c) if(i n) coutOut of Bounds!endlendl; return; 败方树的实现（续败方树的实现（续10） int p; /确定父结点的位置确定父结点的位置 if(i =1; p/=2) int

56、temp;/临时存放赢者的索引临时存放赢者的索引 temp = winner(L,Bp/2, B0); Bp/2 = loser(L,Bp/2, B0); B0 = temp; 利用败方树的多路归并排序算法利用败方树的多路归并排序算法 /输入参数分别是：输入参数分别是： / lt败方树，败方树，racer最初的竞赛者，最初的竞赛者， / bufferPool缓冲池，缓冲池，f输入输入/输出文件句柄数组输出文件句柄数组 /这里输出文件句柄是这里输出文件句柄是f0，输入文件句柄是，输入文件句柄是f1到到 /fMAX，MAX为输入文件的数目为输入文件的数目 /NO_MEANING宏代表一个极大值宏代

57、表一个极大值 template void multiMerge(LoserTree /最终胜者索引最终胜者索引 T read;/读出的数据置放在里面读出的数据置放在里面 利用败方树的多路归并排序算法利用败方树的多路归并排序算法 （续（续1 1） /初始化败方树初始化败方树 lt.Initialize(racer, MAX, Winner, Loser); /以下处理以下处理f1到到fMAX所代表的所代表的 /MAX个输入顺串，个输入顺串， /并把结果输出到并把结果输出到f0所代表的输出顺串中所代表的输出顺串中 /取得最终胜者索引取得最终胜者索引 winner = lt.Winner(); 利用

58、败方树的多路归并排序算法利用败方树的多路归并排序算法 （续（续2 2） while(racerwinner != NO_MEANING) /循环退出时胜者为循环退出时胜者为NO_MEANING， /所有的输入顺串都已经处理完毕所有的输入顺串都已经处理完毕 /把胜者插入到输出缓冲区中把胜者插入到输出缓冲区中 /输出缓冲区满，输出缓冲区满，flush到磁盘文件去到磁盘文件去 if(bufferPool0.isFull() bufferPool0.flush(f0); bufferPool0.insert(racerwinner); 利用败方树的多路归并排序算法利用败方树的多路归并排序算法 （续（续

59、3 3） /从输入缓冲区读入一个新的竞赛者从输入缓冲区读入一个新的竞赛者 if(bufferPoolwinner.isEmpty()=false) /输入缓冲区不为空输入缓冲区不为空 /从缓冲区读入值放进从缓冲区读入值放进racerwinner bufferPoolwinner.read(racerwinner); else/输入缓冲区为空输入缓冲区为空 if(!feof(fwinner) /如果对应的输入文件还有数据如果对应的输入文件还有数据 /从输入文件从输入文件读入一批数据到输入缓冲区读入一批数据到输入缓冲区 fillBuffer(fwinner, bufferPoolwinner);

60、利用败方树的多路归并排序算法利用败方树的多路归并排序算法 （续（续4 4） /从缓冲区读数据放进从缓冲区读数据放进racerwinner bufferPoolwinner.read(racerwinner); /if else/对应的输入文件没有数据对应的输入文件没有数据 /在在racerwinner位置放位置放NO_MEANING racerwinner = NO_MEANING; /else /else 利用败方树的多路归并排序算法利用败方树的多路归并排序算法 （续（续5 5） /重新进行比赛，取得胜者索引重新进行比赛，取得胜者索引 lt.RePlay(winner, Winner, Lo