文件 在现代计算机的应用领域中,数据处理是一个重要方面。 数据处理是对各种类型的大批量的数据进行收集、存 储、排序、检索、计算、修改、输出等分析和加工处 理的过程。例如,用计算机进行企业管理、财务工资 管理、仓库物资管理、情报检索、统计报表等都涉及 到数据存放到外存储器上。有时,为了长期保存原始 数据和加工处理过的数据,也需要将这些数据以文件 的形式存放在外存上。学完本章读者应能掌握文件的 概念、逻辑特性、物理结构和基本操作
文件 在现代计算机的应用领域中，数据处理是一个重要方面。 数据处理是对各种类型的大批量的数据进行收集、存 储、排序、检索、计算、修改、输出等分析和加工处 理的过程。例如，用计算机进行企业管理、财务工资 管理、仓库物资管理、情报检索、统计报表等都涉及 到数据存放到外存储器上。有时，为了长期保存原始 数据和加工处理过的数据，也需要将这些数据以文件 的形式存放在外存上。学完本章读者应能掌握文件的 概念、逻辑特性、物理结构和基本操作
文件的基本概念 与文件有关的基本术语有以下几个: 数据项:数据项是文件中可使用的不可分的最小数据单 位。一个数据项由若干个字符或数字组成,它代表某 事物的一种属性。数据项又称为数据域。例如,个 人书库中的登录号、书号、书名、作者、出版社和价 格等等都是数据项。 记录:记录是由一个或多个数据项根据一定的目的而组 成的数据项集合。例如,由登录号、书号、书名、作 者、出版社和价格等数据项组成的集合是一个职工记 录 文件:文件是大量性质相同的记录组成的集合
文件的基本概念 与文件有关的基本术语有以下几个： 数据项：数据项是文件中可使用的不可分的最小数据单 位。一个数据项由若干个字符或数字组成，它代表某 一事物的一种属性。数据项又称为数据域。例如，个 人书库中的登录号、书号、书名、作者、出版社和价 格等等都是数据项。 记录：记录是由一个或多个数据项根据一定的目的而组 成的数据项集合。例如，由登录号、书号、书名、作 者、出版社和价格等数据项组成的集合是一个职工记 录。 文件：文件是大量性质相同的记录组成的集合
关键字:是能够区别文件中各记录的域。通常,把能唯一标识一个记录的关键字称为主关键字;而那些不能唯 标识一个记录的关键字称为次关键字;由两个以上关键字组成的关键字称为复合关键字 在表10-1所给出的个人书库文件中,各个记录的结构相同,信息长度相同,因而我们将这样的记录称为定长记录 由定长记录组成的文件称为定长记录文件。除了定长记录文件之外,还有不定长记录文件。例如,在学生学 籍管理文件中,不同的年级,或者不同专业的学生,所修的课程数和课程名称都不一样。这样,反映各个学 生的学科成绩的记录长度和结构就不相同,这类记录称为不定长记录。由不定长记录组成的文件叫做不定长 记录文件。 文件的主要操作有以下几种 插入:将一个记录插入某个文件中 删除:从某个文件中删除一个或多个记录 修改:用指定值去修改满足修改条件的某个(或多个)记录中的某个(或多个)数据项的内容 检索:对文件的检索是通过对文件的各种查询来实现的。对表10-1所示的个人书库文件,有以下4种类型的查询: 查询1(Q1):这是简单查询,它规定只查询一个关键字的值。例如查询“书名为数据结构”的书有哪些?又如查 询“书号=1P1787的书是哪一个记录?过些都是简单查询。 查询2(Q2):这是范围性查询,它规定在单个关键字值的某个范围内进行查询。例如查询“价格>2200的书是 哪些记录? 查询3(Q3):这是函数性查询,它要求先规定单个关键字值的某个因数,然后对该函数的值进行查询。例如规定 某个关键字的平均值,可查询“关键字值大于这个平均值”的有哪些记录?对于个人书库文件,可查询“价 格>所有图书的平均价格”是哪些图书? 查询4(Q4):这是布尔查询,即对上述查询Q1Q3用逻辑运算符and(与)、or(或)、mot(非)组合起来进行布 尔查询。例如查询“(书名为数据结构)or(书号=TP1787)”的图书是哪些记录? 在以上的文件操作中,检索是最基本的操作,其它操作都在检索的基础之上进行。 文件的操作又可以分成实时处理和批量处理两种方式。采用实时处理方式时,对任何一类查询或更新,系统应 立即进行响应和处理,一般应在几秒钟之内作出反应。例如,对于一个飞机订票系统,必须在几秒钟之内能 给客户的查询请求输出飞机班次和座位的状况等信息,即应是一个实时检索系统。同理,飞机订票系统应采 用实时更新方式,即当某个航班一个座位被预订出后,应立即更新该航班的座位文件,以免发生差错。采用 批量处理方式,系统不必立即进行响应和处理,因为这时的响应时间不是一个重要因素。例如,对于学生学 籍管理系统来说,可在期末考试全部结束后只进行一次批量处理。 文件的物理结构是指文件在外存上的组织形式。按照文件的检索方式和物理结构,文件分为顺序文件、索引文件 索引顺序文件、直接存取文件、链接文件和多重链表文件、倒排文件。按所存放的外存设备,文件又可以分 为磁带文件和磁盘文件等几类。下面分别加以讨论
关键字：是能够区别文件中各记录的域。通常，把能唯一标识一个记录的关键字称为主关键字；而那些不能唯一 标识一个记录的关键字称为次关键字；由两个以上关键字组成的关键字称为复合关键字。 在表10-1所给出的个人书库文件中，各个记录的结构相同，信息长度相同，因而我们将这样的记录称为定长记录。 由定长记录组成的文件称为定长记录文件。除了定长记录文件之外，还有不定长记录文件。例如，在学生学 籍管理文件中，不同的年级，或者不同专业的学生，所修的课程数和课程名称都不一样。这样，反映各个学 生的学科成绩的记录长度和结构就不相同，这类记录称为不定长记录。由不定长记录组成的文件叫做不定长 记录文件。 文件的主要操作有以下几种： 插入：将一个记录插入某个文件中。 删除：从某个文件中删除一个或多个记录。 修改：用指定值去修改满足修改条件的某个（或多个）记录中的某个（或多个）数据项的内容。 检索：对文件的检索是通过对文件的各种查询来实现的。对表10-1所示的个人书库文件，有以下4种类型的查询： 查询1（Q1）：这是简单查询，它规定只查询一个关键字的值。例如查询“书名为数据结构”的书有哪些？又如查 询“书号=TP1787”的书是哪一个记录？过些都是简单查询。 查询2（Q2）：这是范围性查询，它规定在单个关键字值的某个范围内进行查询。例如查询“价格＞22.00”的书是 哪些记录？ 查询3（Q3）：这是函数性查询，它要求先规定单个关键字值的某个因数，然后对该函数的值进行查询。例如规定 某个关键字的平均值，可查询“关键字值大于这个平均值”的有哪些记录？对于个人书库文件，可查询“价 格＞所有图书的平均价格”是哪些图书？ 查询4（Q4）：这是布尔查询，即对上述查询Q1~Q3用逻辑运算符and（与）、or（或）、not（非）组合起来进行布 尔查询。例如查询“（书名为数据结构）or（书号=TP1787）”的图书是哪些记录？ 在以上的文件操作中，检索是最基本的操作，其它操作都在检索的基础之上进行。 文件的操作又可以分成实时处理和批量处理两种方式。采用实时处理方式时，对任何一类查询或更新，系统应 立即进行响应和处理，一般应在几秒钟之内作出反应。例如，对于一个飞机订票系统，必须在几秒钟之内能 给客户的查询请求输出飞机班次和座位的状况等信息，即应是一个实时检索系统。同理，飞机订票系统应采 用实时更新方式，即当某个航班一个座位被预订出后，应立即更新该航班的座位文件，以免发生差错。采用 批量处理方式，系统不必立即进行响应和处理，因为这时的响应时间不是一个重要因素。例如，对于学生学 籍管理系统来说，可在期末考试全部结束后只进行—次批量处理。 文件的物理结构是指文件在外存上的组织形式。按照文件的检索方式和物理结构，文件分为顺序文件、索引文件、 索引顺序文件、直接存取文件、链接文件和多重链表文件、倒排文件。按所存放的外存设备，文件又可以分 为磁带文件和磁盘文件等几类。下面分别加以讨论
顺序文件 顺序文件是物理结构最简单的文件,也是数据处理历史上最早使用的文件结构。顺序文件的各个记录按输入的先 后次序存放在外存中的连续存储区。为了便于检索和修改文件,文件中的记录通常按关键字的大小次序排列, 成为按关键字排序的顺序文件。表10-1所示的个人书库文件是按关键字登录号排序的文件,它存放到外存的 连续存储区后便得到一个按关键字排序的顺序文件。 顺序文件的基本优点是在连续存取时速度较快。例如,如果文件中的第个记录刚被存取过,而下一个要存取的 记录就是第计1个记录,则此次存取将会很快完成。磁带是比较适用于这种应用的外存设备。存放于磁带上的 文件也只能是顺序文件,这是由磁带的物理特性决定的。存放于磁盘上的文件,既可以是顺序文件,也可以 是索引结构或其它结构类型的文件。 当需要对磁带顺序文件进行检索时,一般是采用顺序扫描的方式来检索满足査询条件的记录。例如,若要检索第i 个记录,则必须先检索前面的计1个记录。为了提高平均检索效率,可采用批量处理技术。如果将对文件的多 个检索请求加以积累和排序,则形成一个称为待办文件(或事务文件)的文件。如果将被查询的文件称为主 文件,则批量检索就是按照待办文件的要求成批地检索主文件。批量检索对于实时应用来说是不适宜的,因 为实时查询要求响应时间快,而在很短的时间间隔内,积累的批处理文件规模太小,不能表现出它的优越性 在磁带顺序文件中插入记录,只能加在文件的末尾,不能插在两个原有记录之间。修改记录,即使在新旧记录 长的情况下,将新记录写在旧记录的位置上,一般不但不可能完全重合,甚至还会破坏邻近记录的信息。因 此,修改一个磁带文件,需要用另一条磁带将原文件复制过来,在复制过程中进行插入、删除、修改记录的 操作。为了提高效率,修改一个顺序文件,也采用成批处理技术。这种批量修改方式很适用于银行帐户结算 管理系统。例如,可把一天的零星支取和存入分别作为记录收集在一起,构成为一个待办文件,在当天下班 时再按照待办文件进行批量修改主文件(头天下班修改过的主文件)的工作,便得到一个新主文件
顺序文件 顺序文件是物理结构最简单的文件，也是数据处理历史上最早使用的文件结构。顺序文件的各个记录按输入的先 后次序存放在外存中的连续存储区。为了便于检索和修改文件，文件中的记录通常按关键字的大小次序排列， 成为按关键字排序的顺序文件。表10-1所示的个人书库文件是按关键字登录号排序的文件，它存放到外存的 连续存储区后便得到一个按关键字排序的顺序文件。 顺序文件的基本优点是在连续存取时速度较快。例如，如果文件中的第i个记录刚被存取过，而下一个要存取的 记录就是第i+1个记录，则此次存取将会很快完成。磁带是比较适用于这种应用的外存设备。存放于磁带上的 文件也只能是顺序文件，这是由磁带的物理特性决定的。存放于磁盘上的文件，既可以是顺序文件，也可以 是索引结构或其它结构类型的文件。 当需要对磁带顺序文件进行检索时，一般是采用顺序扫描的方式来检索满足查询条件的记录。例如，若要检索第i 个记录，则必须先检索前面的i-1个记录。为了提高平均检索效率，可采用批量处理技术。如果将对文件的多 个检索请求加以积累和排序，则形成一个称为待办文件（或事务文件）的文件。如果将被查询的文件称为主 文件，则批量检索就是按照待办文件的要求成批地检索主文件。批量检索对于实时应用来说是不适宜的，因 为实时查询要求响应时间快，而在很短的时间间隔内，积累的批处理文件规模太小，不能表现出它的优越性。 在磁带顺序文件中插入记录，只能加在文件的末尾，不能插在两个原有记录之间。修改记录，即使在新旧记录等 长的情况下，将新记录写在旧记录的位置上，一般不但不可能完全重合，甚至还会破坏邻近记录的信息。因 此，修改一个磁带文件，需要用另一条磁带将原文件复制过来，在复制过程中进行插入、删除、修改记录的 操作。为了提高效率，修改一个顺序文件，也采用成批处理技术。这种批量修改方式很适用于银行帐户结算 管理系统。例如，可把一天的零星支取和存入分别作为记录收集在一起，构成为一个待办文件，在当天下班 时再按照待办文件进行批量修改主文件（头天下班修改过的主文件）的工作，便得到一个新主文件
索引文件 顺序文件的査询速度很慢。采用索引文件可以提高检索效率。实际上,在前面的章节中我们已经运用了索引技术。 索引用来表示关键字与相应记录的存储地址之间的对应关系。换言之,索引指出了记录在存储器中的存储地址 设记录R的关键字为K;,R在外存中的存储地址为A,则(K,A)称为记录R的索引项。索引表(简称索引 是索引项的集合。如果文件中的每个记录都有一个索引项,则这样的索引称为稠密索引。如果多个记录只有 索引项,则这样的索引称为非稠密索引。带有索引的文件称为索引文件。索引也称为目录, 索引文件在外存(磁盘、磁鼓等)中可分为两个存储区:索引区和记录区(数据区)。索引表中的索引项顺序存 放到记录区;记录区按关键字大小次序排列的索引文件称为索引顺序文件。对于索引顺序文件,可以不必使 用稠密索引,只为一个记录块(含多个有序记录)建立一个索引项。记录区不按关键字大小次序排列的索引 文件称为索引非顺序文件,这时应使用稠密索引。图10-2所示的个人书库(价格)索引文件,是一个索引非 顺序文件。 通常,索引项所含的数据信息比记录少得多,因而索引所需的存储空间比文件本身(记录区)所需要的存储空 间少得多。在文件的记录数较少的情况下,可以为每个记录建立一个索引项。文件建立时,开辟一个索引区 般固定在某个磁盘面的一个或多个磁道上。写入一个记录到记录区时,在索引区相应登入一个索引项,即 的缓冲,接关键走行丙部排序。最后将排序好的索分项序写回到磁盘上的素 将索引区中的索引读入内 根据关键字查找索引文件的记录分两步进行。第1步,访问外存的索引区,将索引读入内存缓冲区,使用顺序查 找或折半查找法找出所查记录在外存数据区中的地址,这一过程称为预查找。第2步,如果在预查中已找到了 所查记录的地址,则第2次访问外存,根据已查到的地址,读取所查的记录 删除一个记录时,只需删去相应的索引项,而不必移动数据区中的记录。插入一个新记录时,将记录放到记录 区的末尾,在索引区登记相应的索引项,并对索引区中的索引项重新排序
索引文件 顺序文件的查询速度很慢。采用索引文件可以提高检索效率。实际上，在前面的章节中我们已经运用了索引技术。 索引用来表示关键字与相应记录的存储地址之间的对应关系。换言之，索引指出了记录在存储器中的存储地址。 设记录Ri的关键字为Ki，Ri在外存中的存储地址为Ai，则（Ki，Ai）称为记录Ri的索引项。索引表（简称索引） 是索引项的集合。如果文件中的每个记录都有一个索引项，则这样的索引称为稠密索引。如果多个记录只有 一个索引项，则这样的索引称为非稠密索引。带有索引的文件称为索引文件。索引也称为目录。 索引文件在外存（磁盘、磁鼓等）中可分为两个存储区：索引区和记录区（数据区）。索引表中的索引项顺序存 放在索引区中，但为了便于检索，索引项一般按关键字的大小次序排列。文件中的记录按输入的先后次序存 放到记录区；记录区按关键字大小次序排列的索引文件称为索引顺序文件。对于索引顺序文件，可以不必使 用稠密索引，只为一个记录块（含多个有序记录）建立一个索引项。记录区不按关键字大小次序排列的索引 文件称为索引非顺序文件，这时应使用稠密索引。图10-2所示的个人书库（价格）索引文件，是一个索引非 顺序文件。 通常，索引项所含的数据信息比记录少得多，因而索引所需的存储空间比文件本身（记录区）所需要的存储空 间少得多。在文件的记录数较少的情况下，可以为每个记录建立一个索引项。文件建立时，开辟一个索引区， 一般固定在某个磁盘面的一个或多个磁道上。写入一个记录到记录区时，在索引区相应登入一个索引项，即 把该记录的关键字（主关键字）和记录的存储地址顺序写入索引区。文件建立后，将索引区中的索引读入内 存的缓冲区，按关键字进行内部排序。最后将排序好的索引项顺序写回到磁盘上的索引区。 根据关键字查找索引文件的记录分两步进行。第1步，访问外存的索引区，将索引读入内存缓冲区，使用顺序查 找或折半查找法找出所查记录在外存数据区中的地址，这一过程称为预查找。第2步，如果在预查中已找到了 所查记录的地址，则第2次访问外存，根据已查到的地址，读取所查的记录。 删除一个记录时，只需删去相应的索引项，而不必移动数据区中的记录。插入一个新记录时，将记录放到记录 区的末尾，在索引区登记相应的索引项，并对索引区中的索引项重新排序