哈工大张岩教授讲解：文件与外部排序

"该资源是哈工大计算机科学与技术学院张岩教授关于第7章‘文件与外排序’的课程资料，涵盖了文件的基本概念、不同类型文件的组织方法、查询和更新操作，以及外部排序的详细过程和技术，特别是归并排序在磁盘和磁带文件中的应用。" 在计算机科学中，文件是存储在二级存储器，如硬盘上的记录集合，与存储在内存中的表相对。文件中的数据项是构成记录的基本单元，而属性则是记录中除关键字外的其他数据项。关键字是用于唯一标识记录的重要字段，可分为主关键字和次关键字。例如，在一个学生信息文件中，学号可能是主关键字，而姓名、性别、年龄和各科成绩则是属性。 文件的类型主要有以下几种： 1. 操作系统的文件：这些文件是无结构的字符序列，操作系统无法直接解析其内部结构。 2. 数据库文件：这些文件包含结构化的记录集合，每条记录由一个或多个数据项组成，如上述的学生信息例子。 本章主要讨论了以下内容： - **7.1 文件及文件操作**：介绍了文件的基本概念，包括文件的分类和组成。 - **7.2 顺序文件**：文件中记录按照固定的顺序存储，查询和更新操作相对简单，但效率较低。 - **7.3 索引文件**：通过索引提高查找效率，索引可以单独存储，便于快速定位记录。 - **7.4 ISAM和VSAM文件**：这两种是数据库管理系统中常见的文件组织方式，ISAM（Indexed Sequential Access Method）支持顺序和随机访问，VSAM（Virtual Storage Access Method）则提供更高效的访问机制。 - **7.5 直接存取文件（散列文件）**：通过散列函数将记录直接映射到存储位置，实现快速查找。 - **7.6 多关键字文件**：允许使用多个关键字来定位记录，提高了数据检索的灵活性。 - **7.7 磁盘文件的归并排序**：在外存空间有限的情况下，如何有效地进行大规模数据的排序，归并排序是一种常用方法。 - **7.8 磁带文件的归并排序**：磁带作为线性存储介质，其归并排序有特定的实现策略。 学习这一章，你需要掌握文件的操作，如创建、读取、修改和删除，以及如何根据不同的数据访问模式选择合适的文件结构。对于外部排序，重点在于理解其分块、排序、合并的过程，特别是如何利用有限的内存资源处理大量数据。归并排序在外部排序中的应用是解决大数据处理的关键技术之一，因为它能够有效地处理远大于内存的文件，通过多次内部排序和外部合并步骤达到整体有序。