目录

十三、文件结构

13.1 引言

13.1.1 顺序存取

13.1.2 随机存取

13.2 顺序文件

13.2.1 更新顺序文件

13.3 索引文件

13.4 散列文件

13.4.1 散列方法

13.4.2 冲突

13.5 目录

13.5.1 UNIX操作系统中的目录

13.6 文本文件与二进制文件

13.6.1 文本文件

13.6.2 二进制文件

十三、文件结构

13.1 引言

文件存储在辅助存储设备（二级存储设备）中，在设计一个文件时，关键问题是如何从文件中检索信息。有时需要一个接一个处理，有时需要快速存取一个特定记录。存取的方式决定了怎样检索记录：顺序或是随机。

13.1.1 顺序存取

如果需要顺序（一个接一个，从头到尾）存取记录，那么使用顺序文件结构。

13.1.2 随机存取

如果想存取某一特定记录而不用检索之前的记录，则使用随机存取的文件结构。有两种文件结构允许随机存取：索引文件、散列文件。

13.2 顺序文件

顺序文件是指记录只能按照从头到尾一个接一个地进行存取。记录按照顺序一个接一个被存储在辅助存储设备中，并在最后的记录之后加上EOF（文件末尾）标志。操作系统只知道该文件中的记录是一个接一个存取的。

顺序文件可用于需要从头到尾读取数据的应用，例如，要打印班上所有同学的信息，使用顺序文件是合理的，因为每条记录都需要被访问到。但对于需要随机存取的应用来说，顺序文件效率很低，例如，如果一个人要从银行取钱，如果银行需要按顺序检索该人的信息，将会非常耗时。

13.2.1 更新顺序文件

顺序文件必须定期更新，以反映信息的变化。

1. 需要更新的文件

和更新有关的一共有4个文件：新主文件、旧主文件、事务文件、错误报告文件。所有这些文件根据关键字值被分类。在更新完成之后，新主文件要被送到脱机存储器（辅助存储设备）中去，直到再次需要为止。当文件被更新时，主文件从脱机存储器中检索返回，成为旧主文件。

新主文件：新的永久数据文件，新主文件里包好大部分当前数据。

旧主文件：需要更新的永久文件，即使在更新后，旧主文件作为参考将继续保留。

事务文件：包含对主文件作的改变，在所有文件更新中，共有三种基本类型的改变。添加事务包含将要追加到主文件的新数据。删除事务把要从文件中删除的记录标识出来。修改事务包含对文件中特定记录的修改。要处理这些事务就需要键。键就是文件中一个或多个能唯一标识数据的字段。

错误报告文件：更新过程难免会出错，当错误发生时，应向用户报告错误。错误报告文件包括在数据更新时所发现的错误清单，并且提供给用户进行纠错。

2. 文件更新过程 

要使文件更新过程有效率，所有文件都必须按同一个键排序。更新过程要求比较事务文件和主文件中的键，在没有错误发生的情况下，更新过程如下：

如果事务文件的键小于主文件的键，事务是一个添加（A），则将事务添加到新主文件中；

事务的键等于主文件的键：如果事务是修改（C），则修改主文件数据；如果事务是删除（D），则删除主文件数据；

事务的键大于主文件的键，将旧主文件记录写入新主文件；

有几种情况可能会产生错误，错误将被记录在错误报告中：删除或修改一个主文件中不存在的记录；增加一个主文件中已经存在的记录。

13.3 索引文件

在文件中随机存取记录，需要知道记录的地址。例如，一个用户想要查询银行账户，他给出他的账号（键），通过这个账号关联到数据地址并找到数据。索引文件就是将键和地址关联起来的文件。

索引文件由数据文件组成，它是带索引的顺序文件。索引本身非常小，只占两个字段：顺序文件的键和其中记录的地址。索引将记录的键和记录的地址对应起来，这样通过键就能找到数据。存取文件中的记录需要以下步骤：

1. 整个索引文件都载入内存中（文件很小，只占用很小的内存空间）；

2. 搜索项目，用高效的算法查找目标键；

3. 检索记录的地址；

4. 按照地址，检索记录并返回给用户。

倒排文件：索引文件的好处之一就是一个记录可以有多个索引，每个索引有不同的键。例如，职员的文件可以按社会保险号或姓名来检索。这种索引文件被称为倒排文件。 

13.4 散列文件

在索引文件中，索引将键映射到地址。散列文件用一个数学函数来完成映射，用户给出键，通过数学函数映射为地址，最后通过地址找到记录。散列文件无额外的文件（索引），索引可以由一个数学函数来代替，但散列文件也有自己的问题，那就是会发生冲突。

13.4.1 散列方法

直接散列法：键就是记录的地址，通过键就可以直接找到记录。但这种方法很少用到，只有记录数比较少的时候可以使用。

求模法：用文件大小（最好取大于文件大小的素数，这样可以减少冲突）对键取模，并将余数+1作为地址，因为我们的记录始于1.

数字析取散列法：从键中析取数字作为地址，比如从一个6位的学号中取出第1、3、5位数字作为地址。

其他方法：平方折中法、折叠法、旋转法和伪随机法。书中都没有介绍。

13.4.2 冲突

冲突简单来说就是不同的键通过散列函数得到了相同的地址，但显然这个地址中无法存放两个记录，这时候就产生了冲突。

解决冲突的方法有：开放寻址法、链表解决法（分离链接法）和桶散列法。

这里介绍一下桶散列法（剩下两种在之前的文章中有详细介绍）。桶散列法是指一个地址能够容纳多个记录，所以散列到同一地址的记录可以存放进去，但是这样做有可能会浪费空间。

上面简单介绍了散列文件的一些概念，下面的链接是关于散列ADT的，散列文件是它的一种应用，文章中详细介绍了有关散列的一些概念以及C语言实现。

散列（哈希）_thdwx的博客-CSDN博客

分离链接法-CSDN博客

开放定址法-CSDN博客

再散列和可扩散列_thdwx的博客-CSDN博客

13.5 目录

目录是大多数操作系统提供的，用来组织文件。在大多数操作系统中，目录被表示为含有其他文件信息的一种特殊文件类型。目录不仅仅提供了索引信息，而且包含文件的其他信息：谁有访问文件的权限，文件被创建、存取和修改的日期。在大多数操作系统中，文件被组织成像树的抽象数据类型。

13.5.1 UNIX操作系统中的目录

在目录顶部的是一个称为根的目录，在与目录有关的命令中，它被输入为正斜杠(/)。每个目录可以包含子目录和文件。

1. 特殊目录

在UNIX中有四种特殊目录类型：根目录、主目录、工作目录和父目录。

根目录：是文件层次系统的最高层，它是整个文件结构的根。根目录属于系统管理员，只有管理员能够修改它。

主目录：当登陆系统时，我们使用主目录。每个用户的主目录是不同的，当进入到系统时，每个用户都使用自己的主目录。

工作目录（当前目录）：工作目录就是我们当前使用的目录。当登陆到系统时，工作目录就是主目录，当我们移动到其他目录时，工作目录就是对应目录。

父目录：父目录就是工作目录的上一级目录，根目录没有父目录。

2. 路径和路径名

文件系统中的每个目录和文件都必须有一个名字，有些不同目录下的文件有相同的名字，为了唯一地标识一个文件，我们需要指明从根目录到文件地文件路径。文件路径由它的绝对路径名来指明，它是斜线字符分割的所有目录列表。

一个文件或目录的绝对路径名就像一个人的地址。如果我们只知道这个人的名字，那么绝对不容易找到他，但如果知道他的地址，那就很容易找到。这个绝对路径名可能会很长，由于这个原因，UNIX提供了在特定情况下的短路径名，就是相对路径名，它是相对于工作目录的路径。

13.6 文本文件与二进制文件

存储在存储设备上的文件是一个位的序列，可以被应用翻译成一个文本文件或是二进制文件。

13.6.1 文本文件

文本文件是一个字符文件，在它们的内存储器格式中不能包含整数、浮点数或其他数据结构。要存储这些数据，必须将它们保存成字符格式。这是因为，文本文件显示的时候，是将位模式转换成字符显示出来，并且是一个字节一个字节转换，如果在保存文件时使用的是其他格式，那么文本文件在显示时会将对应数据的位模式转换成字符型，就会出现乱码。

一些文件只能用字符数据格式。值得注意的是用于键盘、监视器和打印机的文件流，这也是为什么需要特殊的函数来格式化上述设备的输入或输出。

13.6.2 二进制文件

二进制文件是计算机内部格式存储的数据集合，在这种定义中，数据可以是整型、浮点型或其他数据结构等。

不像文本文件，二进制文件中的数据只有被程序正确的解释（用正确的数据类型去解释位模式）时才有意义。如果数据是文本格式的，就用一个字节来表示一个字符，如果数据是数字格式的，则用两个或更多字节来表示。