数据结构与算法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 ) 成块地分布在整个磁盘中 文件管理器 操作系统的一部分 把逻辑位置映射为磁盘中具体的物理位置