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

数据结构与算法 第8章文件管理和外排序 任课教员:张铭 http://db.pku.edu.cn/mzhang/ds/ zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究

数据结构与算法 第 8章 文件管理和外排序 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究

为什么需要文件管理和外排序? n文件结构( file structure) 对于在外存中存储的数据 数据量太大不可能同时把它们放到内存中 需要把全部数据放到磁盘中 文件的各种运算 n外排序是针对磁盘文件所进行的排序操作 提高文件存储效率和运算效率 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 2

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 2 为什么需要文件管理和外排序？ „ 文件结构( file structure ) „ 对于在外存中存储的数据 „ 数据量太大不可能同时把它们放到内存中 „ 需要把全部数据放到磁盘中 „ 文件的各种运算 „ 外排序是针对磁盘文件所进行的排序操作 „ 提高文件存储效率和运算效率

大纲 81主存和外存的比较 82外存储器 83外存文件组织 84缓冲区和缓冲池 85外排序的基本算法 北京大学信息学院 张铭编写 版权所有,转载或翻印必究

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 3 大 纲 „ 8.1 主存和外存的比较 „ 8.2 外存储器 „ 8.3 外存文件组织 „ 8.4 缓冲区和缓冲池 „ 8.5 外排序的基本算法

81主存储器和外存储器 基本概念 主存和外存的价格比较 令外存的优缺点 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 4

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 4 8.1 主存储器和外存储器 „ 基本概念 „ 主存和外存的价格比较 „ 外存的优缺点

基本概念 主存储器( primary memory.或者main memory,简称“内存”,或者“主存”) 随机访问存储器( Random Access memory, 即RAM) 高速缓存( cache) 视频存储器( video memory) 外存储器( peripheral storage或者 secondary storage,简称“外存”) ■硬盘、磁带、软盘 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 5

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 5 基本概念 „ 主存储器( primary memory或者main memory ，简称“内存”，或者“主存”) „ 随机访问存储器( Random Access Memory, 即RAM ) „ 高速缓存( cache ) „ 视频存储器( video memory ) „ 外存储器(peripheral storage或者 secondary storage，简称“外存”) „ 硬盘、磁带 、软盘

MB105B(内存) GB109B(硬盘) TB1012B(磁盘阵列) nPB1015B(磁带库) Goge是10的多少次方? 10 100 8058044651张网页(2004年12 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 6

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 6 „ MB 106B (内存) „ GB 109B(硬盘) „ TB 1012B(磁盘阵列) „ PB 1015B (磁带库) „ Google是10的多少次方？ „ 10100 „ 8,058,044,651 张网页(2004年12 月)

主存储器和外存储器 之价格比较 介质2001年底202年底200年早 价格价格期价格 内存 1.5 硬盘00170.0130011 软盘 12 2.5 磁带0.008001100075 北京大学信息学院 张铭编写 版权所有,转载或翻印必究

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 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年底 价格 介质

外存的优缺点 ■优点:永久存储能力、便携性 缺点:访问时间长 访叵磁盘中的数据比访问内存慢五六 里 (10万到100万 所以讨论在外存的数据结构及其上 的操作时,必须遵循下面这个重要 原则: ■尽量减少访外次数! 北京大学信息学院 张铭编写 版权所有,转载或翻印必究

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 8 外存的优缺点 „ 优点：永久存储能力、便携性 „ 缺点：访问时间长 „ 访问磁盘中的数据比访问内存慢五六 个数量级（10万到100万倍）。 „ 所以讨论在外存的数据结构及其上 的操作时，必须遵循下面这个重要 原则： „尽量减少访外次数！

82外存储器 磁盘(几十G·几百T 令磁盘访问时间估算 令磁带(几个P 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 9

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 9 8.2 外存储器 „ 磁盘(几十G - 几百T) „ 磁盘访问时间估算 „ 磁带(几个P)

物理存储介质概览 基本存储 高速缓冲存储器 易失性 主存储器 辅助存储 快闪存储器 (联机存储) 磁盘 非易失 级存储 光盘 性存储 (脱机存储) 磁带 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 10

北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 10 物理存储介质概览 基本存储 高速缓冲存储器 主存储器 快闪存储器 磁盘 光盘 磁带 非易失 性存储 三级存储 (脱机存储) 易失性 辅助存储 (联机存储)