第8章文件管理和外排序 任课教员:张铭 http://db.pku.educn/mzhang/ds zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究
第8章 文件管理和外排序 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究
为什么需要文件管理和外排序? 文件结构( file structure 对于在外存中存储的数据,其数据结构就称 为文件结构( file structure) 数据量太大不可能同时把它们放到内存中 需要把全部数据放到磁盘中 文件的各种运算 外排序是针对磁盘文件所进行的排序操作 提高文件存储效率和运算效率 北京大学信息学院 Page 2
北京大学信息学院 Page 2 为什么需要文件管理和外排序？ ◼ 文件结构( file structure ) ◼ 对于在外存中存储的数据，其数据结构就称 为文件结构( file structure ) ◼ 数据量太大不可能同时把它们放到内存中 ◼ 需要把全部数据放到磁盘中 ◼ 文件的各种运算 ◼ 外排序是针对磁盘文件所进行的排序操作 ◼ 提高文件存储效率和运算效率
本章的安排顺序 81介绍主存和外存的根本差异 82在外存中文件的组织方式 83管理缓冲池的基本方法 84外排序的基本算法 北京大学信息学院 Page 3
北京大学信息学院 Page 3 本章的安排顺序 ◼ 8.1 介绍主存和外存的根本差异 ◼ 8.2 在外存中文件的组织方式 ◼ 8.3 管理缓冲池的基本方法 ◼ 8.4 外排序的基本算法
主存储器和外存储器 n主存储器( primary memory.或者 main memory, 简称“内存”,或者“主存”) 随机访问存储器( Random Access memory,即RAM) 高速缓存( cache) 视频存储器( video memory)。 ■外存储器( peripheral storage或者 secondary storage,简称“外存”) 硬盘 软盘 磁带 北京大学信息学院 age 4
北京大学信息学院 Page 4 主存储器和外存储器 ◼ 主存储器( primary memory或者main memory ， 简称“内存”，或者“主存”) ◼ 随机访问存储器( Random Access Memory, 即RAM ) ◼ 高速缓存( cache ) ◼ 视频存储器( video memory ) 。 ◼ 外存储器(peripheral storage或者secondary storage，简称“外存”) ◼ 硬盘 ◼ 软盘 ◼ 磁带
主存储器和外存储器 之价格比较 介质2001年底2002年底200年 价格 价格 期价格 内存 1.5 硬盘0.01700130.011 软盘 12 2.5 磁带0008001100075 北京大学信息学院 Page 5
北京大学信息学院 Page 5 主存储器和外存储器 之价格比较 介质 2001年底 价格 2002年底 价格 2003年早 期价格 内存 1 1.5 1 硬盘 0.017 0.013 0.011 软盘 12 7 2.5 磁带 0.008 0.011 0.0075
外存的优缺点 ■优点:永久存储能力、便携性 缺点:访问时间长 访叵磁盘中的数据比访间内存慢五六 所以讨论在外存的数据结构及其上 的操作时,必须遵循下面这个重要 原则 尽量减少访外次数! 北京大学信息学院 Page 6
北京大学信息学院 Page 6 外存的优缺点 ◼ 优点：永久存储能力、便携性 ◼ 缺点：访问时间长 ◼ 访问磁盘中的数据比访问内存慢五六 个数量级。 ◼ 所以讨论在外存的数据结构及其上 的操作时，必须遵循下面这个重要 原则： ◼尽量减少访外次数！
磁盘的物理结构 主轴 盘片磁道 活动臂 (回转臂) 柱面 读写磁头 北京大学信息学院 Page 7
北京大学信息学院 Page 7 磁盘的物理结构
磁盘盘片的组织 扇区 扇区间 间隙 位数据(bit 北京大学信息学院 age 8
北京大学信息学院 Page 8 磁盘盘片的组织
磁盘存取步骤 选定某个盘片组 选定某个柱面 这需要把磁头移动到该柱面,这个移动过程称 为寻道(seek) 确定磁道 ■确定所要读写的数据在磁盘上的准确位置 这段时间一般称为旋转延迟( rotational delay或者 rotational1 latency) ■真正进行读写 北京大学信息学院 age 9
北京大学信息学院 Page 9 磁盘存取步骤 ◼ 选定某个盘片组 ◼ 选定某个柱面 ◼ 这需要把磁头移动到该柱面，这个移动过程称 为寻道( seek ) ◼ 确定磁道 ◼ 确定所要读写的数据在磁盘上的准确位置 ◼ 这段时间一般称为旋转延迟( rotational delay 或者rotational latency ) ◼ 真正进行读写
磁盘磁道的组织(交错法) 磁头 磁头 6 3 4 8 2 旋转 旋转 a (a)没有扇区交错;(b)以3为交错因子 北京大学信息学院 Page 10
北京大学信息学院 Page 10 磁盘磁道的组织（交错法） （a）没有扇区交错；（b）以3为交错因子