数据结构与算法 第9章文件管理和外排序 shttp://db.pku.educn/mzhang/ 三章由膨重写 http://www.ipk.pku.edu.cn/pkuipk/course/siig 张铭,三蘑蛟,赵海糞 高等散言出版社,20160“十一最”家般散材
数据结构与算法 第9章文件管理和外排序 本章由王腾蛟主写 http://db.pku.edu.cn/mzhang/DS/ http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 张铭，王腾蛟，赵海燕 高等教育出版社，2008. 6。“十一五”国家级规划教材
主要内容 口9.1生存储器和外存储器 日9.2文件的组织和管理 口9.3外排序 口9.4文件管理和外排序知识点总结 一A”0客包规划。我王,赵,《数福物易》,,B6亲滲
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 主要内容 9.1 主存储器和外存储器 9.2 文件的组织和管理 9.3 外排序 9.4 文件管理和外排序知识点总结
91主存储景和外存储器 口计算机存储器主要有两种: ■主存储器( primary memory或者 main memo 称,内行a者行 °随机访问存储器( Random Access Memory,即RAM) ·高速缓存( cache) 视频存储器( video memory) ■外存储器( peripheral storage或者 secondary storage 简称“外存”) 硬盘 软盘 磁带 一A”0客包规划。我王,赵,《数福物易》,,B6亲滲
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 9.1 主存储器和外存储器 计算机存储器主要有两种： ◼ 主存储器( primary memory或者main memory ，简 称“内存”，或者“主存”) • 随机访问存储器( Random Access Memory, 即RAM ) • 高速缓存( cache ) • 视频存储器( video memory ) ◼ 外存储器(peripheral storage或者secondary storage， 简称“外存”) • 硬盘 • 软盘 • 磁带
外存的优缺点 口优点:价格低、信息不易失、便携性 口缺点:存取速度慢 一般的内存访问存取时间的单位是纳秒(1纳秒=109 秒),而外存一次访问时间则以毫秒(1毫秒=103秒)或秒为数 量级。 口牵扯到外存的计算机程序应当尽量减少外存的访冋 和存取次数,从而减少程序执行的时间 一A”0客包规划。我王,赵,《数福物易》,,B6亲滲
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 外存的优缺点 优点：价格低、信息不易失 、便携性 缺点：存取速度慢 一般的内存访问存取时间的单位是纳秒（1纳秒 = 10-9 秒），而外存一次访问时间则以毫秒（1毫秒= 10-3秒）或秒为数 量级 。 牵扯到外存的计算机程序应当尽量减少外存的访问 和存取次数，从而减少程序执行的时间
内存的优缺点 口优点:访问速度快 口缺点:造价高、存储容量小和断电后丢 失数据 CPU直接与主存沟通,对存储在内存地 址的数据进行访问时,所需要的时间可 以看作是一个很小的常数 一A”0客包规划。我王,赵,《数福物易》,,B6亲滲
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 内存的优缺点 优点：访问速度快 缺点：造价高、存储容量小和断电后丢 失数据 CPU直接与主存沟通，对存储在内存地 址的数据进行访问时，所需要的时间可 以看作是一个很小的常数
外存数据访问方式 口外存空间被划分成长度固定的存储块 称为页(page),每一页包含一定数量的 数据单元 口作为外存的基本存储单位,数据以页块 为单位进行存取。这样可以减少外存的 定位次数,从而减少外存读写的时间耗 费 一A”0客包规划。我王,赵,《数福物易》,,B6亲滲
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 外存数据访问方式 外存空间被划分成长度固定的存储块， 称为页(page)，每一页包含一定数量的 数据单元 作为外存的基本存储单位，数据以页块 为单位进行存取，这样可以减少外存的 定位次数，从而减少外存读写的时间耗 费
92文件的组织和管理 口文件(fil是存储在外存上的数据结构,是由 大量性质相同的记录( record)组成的集合。 口所谓记录,就是具有独立逻辑意义的擞据块, 是文件的基本数据单位。 口最简单的记录可以是字符或者二进制序列,复 条的记录通常可以由若千字段或域(feld的数 据项组成。 一A”0客包规划。我王,赵,《数福物易》,,B6亲滲
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 9.2 文件的组织和管理 文件(file)是存储在外存上的数据结构，是由 大量性质相同的记录(record)组成的集合。 所谓记录，就是具有独立逻辑意义的数据块， 是文件的基本数据单位。 最简单的记录可以是字符或者二进制序列，复 杂的记录通常可以由若干字段或域(field)的数 据项组成
92文件的组织和管理 按照记录的类型,文件可以分成两种 口操作系统的文件 ∠操作系统的文件是一组连续的字待序列,这种序列没 干个逻辑记录,以便存取和使用。 口数据库文件 数据库文件是有结构的记录集合,其中每一条记录都 由一个或多个数据项组成,而每个数据项是不可再分 的基本数据单元。 一A”0客包规划。我王,赵,《数福物易》,,B6亲滲
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 9.2 文件的组织和管理 按照记录的类型，文件可以分成两种： 操作系统的文件 操作系统的文件是一组连续的字符序列，这种序列没 有明显的结构。用户也可以将文件中的信息划分成若 干个逻辑记录，以便存取和使用。 数据库文件 数据库文件是有结构的记录集合，其中每一条记录都 由一个或多个数据项组成，而每个数据项是不可再分 的基本数据单元
92文件的组织和管理 如表91所示为一个数据库文件,每个学生的信息组 成一个记录,每一条记录由6个数据项构成。 姓名 学号性别出生年月所在院系入学时间 贾由00646125 男 1988.5 数学 2006.9.1 陈醒00648308 男 19897 计算机200691 吴轲|00648230 男 1988.3 计算机20061 王子琪0048139 女 1988.2 计算机2006.91 一A”0客包规划。我王,赵,《数福物易》,,B6亲滲
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 9.2 文件的组织和管理 如表9.1所示为一个数据库文件，每个学生的信息组 成一个记录，每一条记录由6个数据项构成。 姓名 学号 性别 出生年月 所在院系 入学时间 贾由 00646125 男 1988.5 数学 2006.9.1 陈醒 00648308 男 1989.7 计算机 2006.9.1 吴轲 00648230 男 1988.3 计算机 2006.9.1 王子琪 00648139 女 1988.2 计算机 2006.9.1 …… …… …… …… …… ……
92文件的组织和管理 按照记录信息长度。文件可以分成 口定长文件 如果文件中每一条记录均含有相同的信息长 之度,那么这种文件称为定长文件。通常定长文 件处理起来比较方便。 口不定长文件 若文件中的记录不是相等长度的,则称为不定 长文件 一A”0客包规划。我王,赵,《数福物易》,,B6亲滲
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 9.2 文件的组织和管理 按照记录信息长度，文件可以分成 定长文件 如果文件中每一条记录均含有相同的信息长 度，那么这种文件称为定长文件。通常定长文 件处理起来比较方便。 不定长文件 若文件中的记录不是相等长度的，则称为不定 长文件