北京大学：《数据结构与算法》课程教学资源（实验班讲义）第八章 文件管理和外排序

数据结构与算法4 为什么需要文件管理和外排序? 第8章文件管理和外排序 文件结构( Mle structure) ■对于在外存中存储的数据 数据量太大不可能同时把它们放到内存中 任课教员:张铭 需要把全部数据放到磁盘中 http:db.pku.edu.cn/mzhang/ds 文件的各种运算 外排序是针对磁盘文件所进行的排序操作 北京大学信息科学与技术学院 提高文件存储效率和运算效率 可信息系统研究所 版权所有,转载或翻印必究 张够 大纲 81主存储器和外存储器 81主存和外存的比较 ○基本概念 个82外存储器 主存和外存的价格比较 △83外存文件组织 外存的优缺点 84缓冲区和缓冲池 85外排序的基本算法 张幅写 基本概念 主存储器( primary memory或者ma memory,简称“内存”,或者“主存”) MB106B(内存 随机访问存储器( Random Access Memory ■GB109B(硬盘) ■TB1012B(磁盘阵列 高速缓存( cache) PB1015B(磁带库) 视频存储器( video memory) Google是10的多少次方? 外存储器 peripheral storage或者 简称“外存”) ■硬盘、磁带、软盘 净5 58044651张网页(2004年12

1 数据结构与算法 第8章 文件管理和外排序 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 2 为什么需要文件管理和外排序？ „ 文件结构( file structure ) „ 对于在外存中存储的数据 „ 数据量太大不可能同时把它们放到内存中 „ 需要把全部数据放到磁盘中 „ 文件的各种运算 „ 外排序是针对磁盘文件所进行的排序操作 „ 提高文件存储效率和运算效率 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 3 大 纲 „ 8.1 主存和外存的比较 „ 8.2 外存储器 „ 8.3 外存文件组织 „ 8.4 缓冲区和缓冲池 „ 8.5 外排序的基本算法 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 4 8.1 主存储器和外存储器 „ 基本概念 „ 主存和外存的价格比较 „ 外存的优缺点 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 5 基本概念 „ 主存储器( primary memory或者main memory ，简称“内存”，或者“主存”) „ 随机访问存储器( Random Access Memory, 即RAM ) „ 高速缓存( cache ) „ 视频存储器( video memory ) „ 外存储器(peripheral storage或者 secondary storage，简称“外存”) „ 硬盘、磁带 、软盘 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 6 „ MB 106B (内存) „ GB 109B(硬盘) „ TB 1012B(磁盘阵列) „ PB 1015B (磁带库) „ Google是10的多少次方？ „ 10100 „ 8,058,044,651 张网页(2004年12 月)

主存储器和外存储器 之价格比较 外存的优缺点 介质2年底12年底3m年早 ■优点:永久存储能力、便携性 缺点:访问时间长 内存 1.5 萃妟登中的勞蓊比訥子馒五六 硬盘0.0170.0130011 软盘 12 2.5 原则: 磁带00080.01100075 ■尽量减少访外次数! 北大 Page 7 张够 82外存储器 物理存储介质概览 基本存储 级冲存储器 磁盘(几十G-几百T 易失性 主存储器 磁盘访问时间估算 辅助存储 ○磁带(几个P (联机存储) 非易失 性存储 三级存储 机存储 北大敏息 张幅写 磁盘的物理结构 磁盘盘片的组织 主轴 物哥 位据(bit 写c机就有轴申务究 卖大惠

2 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 7 主存储器和外存储器 之价格比较 磁带 0.008 0.011 0.0075 软盘 12 7 2.5 硬盘 0.017 0.013 0.011 内存 1 1.5 1 2003年早 期价格 2002年底 价格 2001年底 价格 介质 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 8 外存的优缺点 „ 优点：永久存储能力、便携性 „ 缺点：访问时间长 „ 访问磁盘中的数据比访问内存慢五六 个数量级（10万到100万倍）。 „ 所以讨论在外存的数据结构及其上 的操作时，必须遵循下面这个重要 原则： „尽量减少访外次数！ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 9 8.2 外存储器 „ 磁盘(几十G - 几百T) „ 磁盘访问时间估算 „ 磁带(几个P) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 10 物理存储介质概览 基本存储 高速缓冲存储器 主存储器 快闪存储器 磁盘 光盘 磁带 非易失 性存储 三级存储 (脱机存储) 易失性 辅助存储 (联机存储) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 11 磁盘的物理结构 活动臂 （回转臂） 主 轴 盘 片 磁 道 读写磁头 柱 面 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 12 磁盘盘片的组织 扇区间 间隙 位数据（bit） 扇区

磁盘磁道的组织(交错法) 磁盘存取步骤 ■选定某个盘片 选定某个柱面 纛努誓遗头动到该柱面,这个移动过 ■确定磁道 确定所要读写的数据在磁盘上的准确位 这段时间一般称为旋转延迟( rotatio frot 真正进行读写 (a)没有扇区交错;(b)以3为交错因子 磁盘性能指标 总存取时间(1) ■容量(G) (1)数据连续存放,且给出了平均寻道时间 总存取时间=[平均寻道时间] ■磁盘旋转速度(rpm) +[第一道读取时间] ■交错因子 (总磁道数-1)×[(第二次寻道时间)+(读取整 ■寻道时间 =[平均寻道时间] +[(0.5圈延迟+交错因子)x每圈所花时间] 旋转延迟时间 (总磁道数-1) 磁道转换时间+(0.5圈延迟+交错因子x每圆 北大敏息 张幅写 总存取时间(2) (2)数据随机存放。 总存取时间=簇数x{[平均寻道时 5.3C侣布户鑫为上.每 间]+[旋转延迟]+[读一簇时间] 盘片上有1308 5个磁道,每个磁 包含256个扇区,每个扇区512 =簇数x{[平均寻道时间] 个簇8个扇区 +[0.5圈延迟x每圈所花时间] 错因子是3。磁盘 幸意 400 +{交错因子x(每簇扇区数每道扇区 积罚向平骜简延 2ms,随 数)×每圈时间 是9.5ms

3 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 13 磁盘存取步骤 „ 选定某个盘片 „ 选定某个柱面 „ 这需要把磁头移动到该柱面 ，这个移动过 程称为寻道( seek ) „ 确定磁道 „ 确定所要读写的数据在磁盘上的准确位 置 „ 这段时间一般称为旋转延迟( rotational delay 或者rotational latency ) „ 真正进行读写 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 14 磁盘磁道的组织（交错法） （a）没有扇区交错；（b）以3为交错因子 磁头 旋转 磁头 旋转 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 15 磁盘性能指标 „ 容量（G） „ 磁盘旋转速度(rpm) „ 交错因子 „ 寻道时间 „ 旋转延迟时间 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 16 总存取时间(1) （1）数据连续存放，且给出了平均寻道时间。 总存取时间 = [平均寻道时间] + [第一道读取时间] + (总磁道数–1)×[(第二次寻道时间)+(读取整 道的时间)] = [平均寻道时间] + [(0.5圈延迟+交错因子) × 每圈所花时间] + (总磁道数–1) × [磁道转换时间+(0.5圈延迟+交错因子)×每圈 所花时间] 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 17 总存取时间(2) （2）数据随机存放 。 总存取时间 = 簇数 × {[平均寻道时 间]+[旋转延迟]+[读一簇时间]} = 簇数 × {[平均寻道时间] + [0.5圈延迟×每圈所花时间] + [交错因子×（每簇扇区数/每道扇区 数）×每圈时间]} 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 18 „ 例8.1 假定一个磁盘总容为 16.8GB，分布在10个盘片上。每 个盘片上有13085个磁道，每个磁 道中包含256个扇区，每个扇区512 个字节，每个簇8个扇区。扇区的交 错因子是3。磁盘旋转速率是5400 rpm，磁道转换时间是2.2 ms，随 机访问的平均寻道时间是9.5 ms

解:我们先总结出一些共有的特性 ■如果读取一个1MB的文件,该文件 每个簇为4KB 有2048个记录,每个记录有512字 节(1个扇区)。对于以下两种情 每个磁道有32 况,估算进行文件处理的总时间。 256个扇区=256扇区+8(廟区/簇)=32个簇 每个盘片有168GB (1)假定所有记录在8个连续磁道 168GB+10=1.68GB 每转一围的时间为111ms ■(2)假定文件簇随机地散布在磁盘 xg:5圈=11m)= 上。 的拿濫消量园此下面计算公式中,所用 张够 数据连续存放,而且给出了平均寻道时间 总存取时间=[平均寻道时间] 数据随机存放 05國延迟+交错因子)x每圈所花时间 总簇数:8个磁道x32(簇/磁道)=256簇 总磁道数-1) 存取时间=簇数x{平均寻道时间] 盏所转时间+os延+交错图子)每 +[05圖延迟x每圆所花时间] [95ms(平均寻道时间)] 错因子x(每簇扇区数/每道扇区数)x每 [(05(半國旋转延迟)+3(交错因 子))×111ms =256x[95ms(平均寻道时间)] (8-1)个其他磁道 ±[0.5(半旋转延迟 [22ms磁道转换时间+(05圖延迟+3交错 因子)×11.1ms 256(0支H交图X区 =95ms+48.4ms+7x41.1ms 256×{95+5.55+1.04} 335.7ms ≈411904ms 北大敏息 张幅写 定位并读一簇时间为: 道时间]+[05圈延迟×每圈所花时间] 读一个扇区的时间 读一镤数据时间 =「95m(平均寻道)+[05(半 题51平均巴男295(湖封延 )×11.ms/圈]+104 1.1ms ≈95+5.55+104=16.09ms 读一个字节的时间 莓的时努一数据(不包括寻道定位 [9:5ms(平均寻道时间】+0.5(半圈旋转延 迟)x111ms/團]=15.05ms [3(交错因子)x×8扇区/篾/)+256(扇区/道) “一次访外操作 1ms/蘭≈1.04ms 涝一资O碘同 成乔公,通常称为

4 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 19 „ 如果读取一个1MB的文件，该文件 有2048个记录，每个记录有512字 节（1个扇区）。对于以下两种情 况，估算进行文件处理的总时间。 „ （1）假定所有记录在8个连续磁道 上； „ （2）假定文件簇随机地散布在磁盘 上。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 20 解：我们先总结出一些共有的特性 „ 每个簇为4KB „ 8个扇区 ＝ 512 byets × 8 ＝ 4KB „ 每个磁道有32簇 „ 256个扇区 ＝ 256 扇区 ÷8（扇区/簇） = 32个簇 „ 每个盘片有1.68GB „ 16.8GB ÷ 10 = 1.68GB „ 每转一圈的时间为11.1ms „ (60×1000)ms/5400圈 = 11.1（ms/圈）= 11.1（ms/道） „ 一个磁道是一个整圈，因此，下面计算公式中，所用 的单位“圈”等同于“道” 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 21 „ 数据连续存放，而且给出了平均寻道时间。 总存取时间 = [平均寻道时间] + [(0.5圈延迟+交错因子) × 每圈所花时间] + (总磁道数–1) × [磁道转换时间+(0.5圈延迟+交错因子)×每 圈所花时间] = [9.5ms（平均寻道时间）] + [(0.5（半圈旋转延迟） + 3（交错因 子）)×11.1ms/圈 +（8-1）个其他磁道 × [2.2ms磁道转换时间+(0.5圈延迟+3交错 因子)×11.1ms/圈] = 9.5ms + 48.4ms + 7 × 41.1ms = 335.7ms 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 22 „ 数据随机存放 „ 总簇数：8个磁道 × 32(簇/磁道) = 256簇 总存取时间 = 簇数 × {[平均寻道时间] + [0.5圈延迟×每圈所花时间] + [交错因子×（每簇扇区数/每道扇区数）×每 圈时间]} = 256 ×{ [9.5ms（平均寻道时间）] + [0.5（半圈旋转延迟） ×11.1ms/圈] + [3(交错因子)×8(扇区/簇 /)÷256(扇区/道) ×11.1ms/圈]} ≈ 256 × {9.5 + 5.55 + 1.04} ≈ 4119.04 ms 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 23 „ 定位并读一簇时间为： „ [平均寻道时间] + [0.5圈延迟×每圈所花时间] +读一簇数据时间 = [9.5ms(平均寻道)] + [0.5(半 圈)×11.1ms/圈]+1.04 ≈ 9.5 + 5.55 + 1.04 = 16.09ms „ 其中，只是读一簇数据（不包括寻道定位 等）的时间为 „ [3(交错因子)×8(扇区/簇/)÷256(扇区/道) ×11.1ms/圈] ≈ 1.04ms 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 24 „ 读一个扇区的时间 „ [9.5ms(平均寻道时间)]+[0.5(半圈旋转延 迟)×11.1ms/圈+[1扇区÷256(扇区/道) ×11.1ms/圈] ＝ 15.1ms „ 读一个字节的时间 „ [9.5ms(平均寻道时间)]+[0.5(半圈旋转延 迟)×11.1ms/圈] ＝ 15.05ms „ “一次访外”操作 „ 磁盘一次I/O操作访问一个扇区，通常称为 访问“一页”（page），或者“一块”(block)

磁带运行示意图 磁带 ■主要优点:使用方便、价格便 磁头 宜、容量大、所存储的信息比磁 盘和光盘更持久 磁带向前运动方向 ■缺点:速度较慢,只能进行顺序 存取 磁带卷在一个卷盘上,运行时磁带经过读 写磁头,把磁带上的信息读入计算机,或 把计算机中的信息写在磁带上 磁带发展史 83外存文件的组织 文件组织 手工阶段 ∝C++的流文件 ■自动化磁带库系统 虚拟磁带技术 张幅写 职工号姓名性别职务婚媚状况工资 文件组织 56张东男程序员未婚7800 860李珍女 逻辑文件( logical file) 510赵莉女程序员未婚6900 对高级程序语言的编程人员而言 连续的字节构成记录,记录构成逻辑文件 620周力男分析员已婚10300 物理文件( physical fi1e) 成块地分布在整个磁盘中 文件是一些记录的汇集,其中每个记录由一个或多 件管理器 操作系统的一部分 把逻辑位置映射为磁盘中具体的物理位置 上大息单 张邮写有轨串券鬼 5

5 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 25 磁带 „ 主要优点 ：使用方便、价格便 宜、容量大、所存储的信息比磁 盘和光盘更持久 „ 缺点：速度较慢，只能进行顺序 存取 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 26 磁带运行示意图 磁带卷在一个卷盘上，运行时磁带经过读 写磁头，把磁带上的信息读入计算机，或 把计算机中的信息写在磁带上。 接收盘 源盘 磁头 磁带向前运动方向 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 27 磁带发展史 „ 手工阶段 „ 自动化磁带库系统 „ 虚拟磁带技术 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 28 8.3 外存文件的组织 „ 文件组织 „ C++的流文件 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 29 620 周力 男 分析员 已婚 10300 950 陈萍 女 程序员 未婚 6200 510 赵莉 女 程序员 未婚 6900 860 李珍 女 分析员 已婚 8900 156 张东 男 程序员 未婚 7800 职工号 姓名 性别 职务 婚姻状况 工资 „ 文件是一些记录的汇集，其中每个记录由一个或多 个数据项组成。 „ 数据项有时也称为字段，或者称为属性。例如，一 个职工文件里的记录可以包含下列数据项：职工， 姓名，性别，职业，婚姻状况，工资等。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 30 文件组织 „ 逻辑文件( logical file ) „ 对高级程序语言的编程人员而言 „ 连续的字节构成记录，记录构成逻辑文件 „ 物理文件( physical file ) „ 成块地分布在整个磁盘中 „ 文件管理器 „ 操作系统的一部分 „ 把逻辑位置映射为磁盘中具体的物理位置

文件的逻辑结构 文件的存储结构 文件是记录的汇集 ■当一个文件的各个记录按照某种次序 顺序结构——顺序文件 排列起来时,各纪录间就自然地形成 了一种线性关系。 计算寻址结构——散列文件 因而,文件可看成是一种线性结 带索引的结构——带索引文件 构 张够 文件上的操作 C++的流文件 ■检索:在文件中寻找满足一定条件的记录 C++程序员对随机访问文件的逻辑视图 ■修改:是指对记录中某些数据值进行修改。若 是 的字节流,即字节数组 对关键码值进行修改,这相当于删除加插入 序员需要管理标志文件当前位置的文 ■插入:向文件中增加一个新记录 删除:从文件中删去一个记录。 符符本文件操作,都是统文 排序:对指定好的数据项,按其值的大小把文 文件指针设置到指定位置(移动文件指 件中的记录排成序列,较常用的是按关键码值 的排序 从文件的当前位置读取字节 ■向文件中的当前位置写入字节 张幅写 C十十操作二进制文件 的常用方式— fstream类 fstream类的主要函数成员 stream类提供函数操作可随机 #include//fstream=ifstreamtofstream 访问的磁盘文件中的信息。 /打开文件进行处理。 stream类的主要成员函数包括 /模式示例:ios:: in ios: binary open, close, read, write, void fstream:: open char* name, openmode mode) seekg, seekp. ∥处理结束后关闭文件。 void fstream: close:

6 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 31 文件的逻辑结构 „ 文件是记录的汇集 „ 当一个文件的各个记录按照某种次序 排列起来时，各纪录间就自然地形成 了一种线性关系。 „ 因而，文件可看成是一种线性结 构。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 32 文件的存储结构 „ 顺序结构——顺序文件 „ 计算寻址结构——散列文件 „ 带索引的结构——带索引文件 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 33 文件上的操作 „ 检索：在文件中寻找满足一定条件的记录 „ 修改：是指对记录中某些数据值进行修改。若 对关键码值进行修改，这相当于删除加插入。 „ 插入：向文件中增加一个新记录。 „ 删除：从文件中删去一个记录 。 „ 排序 ：对指定好的数据项，按其值的大小把文 件中的记录排成序列，较常用的是按关键码值 的排序。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 34 C＋＋的流文件 „ C++程序员对随机访问文件的逻辑视图 是一个单一的字节流，即字节数组。 „ 程序员需要管理标志文件当前位置的文 件指针。 „ 常见的三个基本文件操作，都是围绕文 件指针进行的： „ 把文件指针设置到指定位置（移动文件指 针） „ 从文件的当前位置读取字节 „ 向文件中的当前位置写入字节 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 35 C＋＋操作二进制文件 的常用方式——fstream类 „ fstream类提供函数操作可随机 访问的磁盘文件中的信息。 „ fstream类的主要成员函数包括 open，close，read，write， seekg，seekp。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 36 fstream类的主要函数成员 #include//fstream=ifstream+ofstream // 打开文件进行处理。 // 模式示例: ios::in | ios::binary void fstream::open(char* name, openmode mode); // 处理结束后关闭文件。 void fstream::close();

ftrean类的主要函数 成员(续1) ftrean类的主要函数成员(续2) ∥/从文件当前位置读入一些字节。 sekg和 seekp:在文件中移动当前位置, ∥/随蓍字节的读入,文件当前位置向前移动。 ∥这样就可以在文件中的任何一个位置 ∥读出或写入字节 fstream::read(char* ptr, int numbytes ∥实际上有两个当前位置 ∥-个用于读出,另一个用于写入 //向文件当前位置写入一些字节 ∥函数sekg用于改变读出位置, /(盖已经在这些位置的字节)。 ∥函数 seekp用于改变写入位量 /随着字节的写入,文件当前位置向前移动 fstream: seekg( int pos);//处理输入 fstream:: write(char* ptr, int numbtyes): fstream: seekp int pos);//处理输出 a istream: seekp(int pos, ios::end); 84缓冲区和缓冲池 缓冲 ○基本概念 目的:减少磁盘访问次数的 ○替换缓冲区的策略 方法:缓冲( buffering)或缓存 虚拟存储 caching 在内存中保留尽可能多的块 可以增加待访问的块已经在内存中的 机会 北大敏息 张幅写 缓冲区和缓冲池 替换缓冲区块的策略 ■存储在一个缓冲区中的信息经常 称为一页(page),往往是一次 新的页块申请缓冲区时,把最近 I/O的量 最不可能被再次引用的缓冲区释 放来存放新页 缓冲区合起来称为缓冲池( buffer ■“先进先出”(FIFO) pool ■“最不频繁使用”(LFU) ■“最近最少使用”(LRU

7 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 37 ftream类的主要函数 成员（续1） // 从文件当前位置读入一些字节。 // 随着字节的读入，文件当前位置向前移动。 fstream::read(char* ptr, int numbytes); // 向文件当前位置写入一些字节 // (覆盖已经在这些位置的字节)。 // 随着字节的写入，文件当前位置向前移动。 fstream::write(char* ptr, int numbtyes); 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 38 ftream类的主要函数成员（续2） // seekg和seekp：在文件中移动当前位置， // 这样就可以在文件中的任何一个位置 // 读出或写入字节。 // 实际上有两个当前位置， //一个用于读出，另一个用于写入。 // 函数seekg用于改变读出位置， // 函数seekp用于改变写入位置 fstream::seekg(int pos); // 处理输入 fstream::seekg(int pos, ios::curr); fstream::seekp(int pos); // 处理输出 fstream::seekp(int pos, ios::end); 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 39 8.4缓冲区和缓冲池 „ 基本概念 „ 替换缓冲区的策略 „ 虚拟存储 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 40 缓冲 „ 目的：减少磁盘访问次数的 „ 方法：缓冲( buffering )或缓存 ( caching ) „ 在内存中保留尽可能多的块 „ 可以增加待访问的块已经在内存中的 机会 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 41 缓冲区和缓冲池 „ 存储在一个缓冲区中的信息经常 称为一页( page )，往往是一次 I/O的量 „ 缓冲区合起来称为缓冲池( buffer pool ) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 42 替换缓冲区块的策略 新的页块申请缓冲区时，把最近 最不可能被再次引用的缓冲区释 放来存放新页 „ “先进先出”(FIFO) „ “最不频繁使用”(LFU) „ “最近最少使用”(LRU)

虚拟存储 虚拟存储 虚拟地址空闻 物理内存地址 虚拟存储( virtual memory 使得程序员能够使用比实际内存 更大的内存空间 ■磁盘中存储虚拟存储器的全部的 内容,根据存储器的访问需要把 块读入内存缓冲池。 85外排序 外排序( external sort) 基本概念 ■外存设备上(文件的排序技术 ①置换选择排序 文件很大 二路外排序 无法把整个文件的所有记录同时 调入内存中进行排序,即无法进 多路归并选择树 行内排序 ■外部排序算法的主要目标是尽量 减少读写磁盘的次数 北大敏息 张幅写 关键码索引排序 磁盘排序过程 ■索引文件( index file)中 关键码与指针一起存储 毆捷行赌排序方暮姦往槊 指针标识相应记录在原数据文件中的位置 对索引文件进行排序,所需要的I/0操作 磁盘排序过程: ■文件分成若干尽可能长的初始顺 索引文件比整个数据文件小很多。 在一个索引文件中,只针对关键码排序 ( key sort)。 逐步归并顺串归,最后形成一个 咔序的文件

8 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 43 虚拟存储 „ 虚拟存储( virtual memory ) 使得程序员能够使用比实际内存 更大的内存空间。 „ 磁盘中存储虚拟存储器的全部的 内容，根据存储器的访问需要把 块读入内存缓冲池。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 44 虚拟存储 „ 系统运行到某一时刻，虚拟地址空间中有5个页被读入到物 理内存中，现在如果需要对地址为24k-28k的页进行访 问，就必须替换掉当前物理内存中的一个页框。 0-4k 4k-8k 8k-12k 12k-16k 16k-20k 0-4k 4k-8k 8k-12k 12k-16k 16k-20k 20k-24k 24k-28k 28k-32k 32k-36k 36k-40k 虚拟地址空间 物理内存地址 1 3 0 4 2 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 45 8.5 外排序 „ 基本概念 „ 置换选择排序 „ 二路外排序 „ 多路归并-----选择树 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 46 外排序( external sort ) „ 外存设备上(文件)的排序技术 „ 文件很大 „ 无法把整个文件的所有记录同时 调入内存中进行排序，即无法进 行内排序 „ 外部排序算法的主要目标是尽量 减少读写磁盘的次数 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 47 关键码索引排序 „ 索引文件( index file )中 „ 关键码与指针一起存储 „ 指针标识相应记录在原数据文件中的位置 „ 对索引文件进行排序，所需要的I/O操作 更少 „ 索引文件比整个数据文件小很多。 „ 在一个索引文件中，只针对关键码排序 ( key sort )。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 48 磁盘排序过程 „ 顺串：用内排序方法对文件的各 段进行初始排序，并存放在外存 磁盘排序过程： „ 文件分成若干尽可能长的初始顺 串； „ 逐步归并顺串归，最后形成一个 已排序的文件

851置换选择排序 置换选择算法 ■扫描一遍 一个输入缓冲区 ■使得所生成的各个顺串更长 个输出缓冲区 减少了初始顺串的个数 一个能存放M个记录的RAM内 存块 ■目的 可以看成大小为M的连续数组 m在合并顺串时减少对数据的扫描遍数 张够 置换选择方法图示 航入齐件绕区RM拙枢轴出串文件 排序操作可以利用缓冲区,但只 能在RAM中进行 ■平均情况下,这种算法可以创建 长度为2M个记录的顺串 产生一个顺串的过程 1在RAM中把待排序记录建立 2.从输入文件读取一整块磁盘,存入输入缓冲区 3.通过置换选择排序,把合适的数据写到输出缓冲 区,缓冲区满则输出到一个磁盘块 4.输入缓冲区空时,从输入文件读取下一块磁盘 北大敏息 置换选择算法 置换选择算法(续) 重复以下步骤,直到堆为空(即LAST<0): 1.初始化堆: (a)把具有最小关键码值的记录(根结点)送到输出缓 (a)从磁盘读M个记录放到数组RAM中。 (b)设置堆末尾标准LAsT=M-1 b)设R是输入缓冲区中的下一条记录。如果R的关键 码值大于刚刚输出的关键码值 (c)建立一个最小值堆 i.那么把R放到根结点。 i.否则使用数组中LAST位置的记录代替 根结点,然后把R放到LAST位置 ELAST LASt- 1 c)黛新排列堆,筛出根结点

9 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 49 8.5.1 置换选择排序 „ 扫描一遍 „ 使得所生成的各个顺串更长 „ 减少了初始顺串的个数 „ 目的： „ 在合并顺串时减少对数据的扫描遍数 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 50 置换选择算法 „ 一个输入缓冲区 „ 一个输出缓冲区 „ 一个能存放M个记录的RAM内 存块 „ 可以看成大小为M的连续数组 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 51 „ 排序操作可以利用缓冲区，但只 能在RAM中进行 „ 平均情况下，这种算法可以创建 长度为2M个记录的顺串 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 52 置换选择方法图示 产生一个顺串的过程 1. 在RAM中把待排序记录建立堆 2. 从输入文件读取一整块磁盘，存入输入缓冲区 3. 通过置换选择排序，把合适的数据写到输出缓冲 区，缓冲区满则输出到一个磁盘块 4. 输入缓冲区空时，从输入文件读取下一块磁盘 输入文件 输入缓冲区 RAM 输出缓冲区 输出顺串文件 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 53 置换选择算法 1. 初始化堆： (a) 从磁盘读M个记录放到数组RAM中。 (b) 设置堆末尾标准LAST ＝ M － 1。 (c) 建立一个最小值堆。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 54 置换选择算法（续） 2. 重复以下步骤，直到堆为空（即LAST < 0）： (a) 把具有最小关键码值的记录(根结点)送到输出缓 冲区。 (b) 设R是输入缓冲区中的下一条记录。如果R的关键 码值大于刚刚输出的关键码值…… i. 那么把R放到根结点。 ii. 否则使用数组中LAST位置的记录代替 根结点，然后把 R放到 LAST位置。设置 LAST ＝ LAST － 1。 (c)重新排列堆，筛出根结点

置换选择示例(1) 置换选择示例(2 3( 北大 置换选择示例(3) 置换选择算法的实现 存储 //模板参数Eem代表数组中每一个元素的类型 /A是从外存读入n个元素后所存放的数组 //in和out分别是输入和输出文件名 template void replacementselection(Elem A, int n, const char *in, const char outt 北大鳥”,翰究Pa957 张幅写 Elem mval//存放最小值堆的最小值 for(int last =(n-1); last > 0F mva= H heapArray[o];//最小值 Eemr;//存放从输入缓冲区中读入的元素 sendTooutputBuffer( input, output, * inputFile;//输入、输出文件句柄 inputFile, outputFile, mval; outputFile; put read(r);//从输入缓冲区读入一个记录 Buffer input;//输入、输出 buffer if(less(r, mval) Buffer output H heapArray[o]=r;//r放到根结点 //初始化输入输出文件 ese{//ast记录代誉根结点,r放到ast位量 init Files(inputFile, outputFile in, out); H heapArray [o]= h heap Array last] nitMinHeapArry(inputFile, n, A);∥/建堆 aStI= MinHeap H(A, n, n) initInputBuffer(input, inputFile); H. SiftDown(O); //调整根结点 endup(output, inputFile, outputFile);) 10

10 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 55 置换选择示例（1） 12 19 31 25 21 5 6 40 输 入 存 储 输 出 16 19 31 25 21 5 6 40 16 29 12 16 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 56 置换选择示例（2） 2 9 1 9 31 2 5 2 1 56 40 输 入 存 储 输 出 1 9 2 1 31 2 5 2 9 56 40 1 4 1 9 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 57 置换选择示例（3） 4 0 21 31 25 29 56 14 输 入 存 储 输 出 2 1 25 31 40 29 56 14 35 21 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 58 置换选择算法的实现 //模板参数Elem代表数组中每一个元素的类型 //A是从外存读入n个元素后所存放的数组 //in和out分别是输入和输出文件名 template void replacementSelection(Elem * A, int n, const char * in, const char * out) { 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 59 Elem mval; //存放最小值堆的最小值 Elem r; //存放从输入缓冲区中读入的元素 FILE * inputFile; //输入、输出文件句柄 FILE * outputFile; Buffer input; //输入、输出buffer Buffer output; //初始化输入输出文件 initFiles(inputFile, outputFile, in, out); initMinHeapArry(inputFile, n, A); //建堆 MinHeap H(A, n, n); initInputBuffer(input, inputFile); 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 60 for(int last = (n-1); last >= 0;){ mval = H.heapArray[0]; //最小值 sendToOutputBuffer(input, output, inputFile, outputFile, mval); input.read(r); //从输入缓冲区读入一个记录 if(!less(r, mval)) H.heapArray[0] = r; // r放到根结点 else { //last记录代替根结点，r放到last位置 H.heapArray[0]= H.heapArray[last]; H.heapArray[last] = r; H.setSize(last--); } H.SiftDown(0); //调整根结点 } //for endUp(output, inputFile, outputFile); }