数据结构与算法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年121 数据结构与算法 第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 月)