9.4索引文件
索引文件由主文件和索引表构成。主文件为文件本身。索引 表指明逻辑记录和物理记录之间的对应关系。索引表由若干 索引项组成。一般索引项由主关键字和该关键字所在记录的 物理地址组成。索引表必须按主关键字有序，而主文件本身 则可以按主关键字有序或无序。 主文件按主关键字有序称索引顺序文件(Indexed Sequential File)。在ISF中，对一组记录建立一个索引项称为稀疏索引 。主文件按主关键字无序称索引非顺序文件(Indexed Non Sequential File)。必须为每个记录建立一个索引项，称为稠 密索引。将索引非顺序文件简称索引文件。索引非顺序文件 主文件无序，适合随机存取，不适合顺序存取。索引顺序文 件的主文件是有序的，适合随机存取、顺序存取。索引顺序 文件的索引是稀疏索引。索引占用空间较少，是最常用的一 种文件组织。最常用的索引顺序文件：ISAM文件和VSAM 文件。
对于字符流文件来说，查找操作是比较困难的。但管理简单 ，所以，操作不多的文件较适于采用字符流的无结构方式。 记录式的有结构文件可把文件中的记录按各种不同的方式排 列，构成不同的逻辑结构，以便用户对文件中的记录进行修 改、追加、查找和管理等操作。
文件的操作主要有两类：检索和维护 检索即在文件中查找满足给定条件的记录。文件的检索有以 下三种方式：
维护操作包括：对文件进行记录的插入、删除及修改等更新 操作。
文件的存储结构
文件的存储结构是指文件在外存上的组织方式。文件在外存 上的基本的组织方式有四种：顺序组织，索引组织，散列组 织和链组织；对应的的文件名称分别为：顺序文件、索引文 件、散列文件和多关键字文件。文件组织的各种方式往往是 这四种基本方式的结合。 选择哪一种文件组织方式，取决于对文件中记录的使用方式 和频繁程度、存取要求、外存的性质和容量。 评价一个文件组织的效率，是执行文件操作所花费的时间和 文件组织所需的存储空间。
第九章 文件
文件(File)是性质相同的记录的集合。按其记录的类型不同 而分为两类： 操作系统文件和数据库文件。
操作系统中研究的文件一种是无结构的流式文件，文件内信息不再 划分单位，由字符流构成的文件。 数据库中所研究的文件是带有结构的记录集合，每个记录可由若干 个数据项构成。
记录是文件中存取的基本单位，数据项是文件可使用的最小 单位。数据项有时也称为字段(Field)，或者称为属性 (Attribute)。其值能惟一标识一个记录的数据项或数据项的 组合称为主关键字项。
9.4索引文件
索引文件在存储器上分为两个区：索引区和数据区。索引区 存放索引表，数据区存放主文件。建立索引文件的过程为： 首先按输入记录的先后次序建立数据区和索引表。其中索引 表中关键字是无序的；然后，待全部记录输入完毕后对索引 表进行排序，排序后的索引引文件的检索：首先，将索引区的页块送人内存，查找所 需记录的物理地址。然后，将含有该记录的页块送人内存。 索引表不大时，索引表可一次读入内存，在索引文件中检索 只需两次访问外存：一次读索引，一次读记录。由于索引表 有序，对索引表的查找可用顺序查找或二分查找等方法。 索引文件的更新操作包括插入和删除等。插入操作为将插入 记录置于数据区的末尾，并在索引表中插入索引项；删除操 作删去相应的索引项；修改主关键字时要同时修改索引表。 我们也可以利用查找表建立多级索引。对索引表建立的索引 ，称为查找表。查找表的建立可以为占据多个页块的索引表 的查阅减少外存访问次数。当查找表中项目仍很多，可建立 更高一级的索引。通常最高可达四级索引： 数据文件一>索引表一>查找表一>第二查找表一>第三查找 表。
文件分类
单关键字文件和多关键字文件 定长文件和不定长文件
9.2文件的逻辑结构及物理结构
文件的逻辑结构是指文件在用户或应用程序员面前呈现的方 式，是用户对数据的表示和存取方式。选取文件的逻辑结构 应遵循下述原则：
当用户对文件信息进行修改操作时，给定的逻辑结构应能尽量减少 对已存储好的文件信息的变动。1 当用户需要对文件信息进行操作时，给定的逻辑结构应使文件系统 在尽可能短的时间内查找到需要查找的记录或基本信息单位。 应使文件信息占据最小的存储空间。 应是便于用户进行操作的。
9.3顺序文件
顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序 和物理顺序一致的文件。顺序文件分为顺序有序文件和顺序 无序文件。记录按其主关键字有序的顺序文件为顺序有序文 件。记录未按其主关键字有序排列的顺序文件为顺序无序文 件。为提高检索效率，常将顺序文件组织成有序文件。 顺序有序文件存取的查找方法很多。包括顺序查找法，分块 查找法，二分查找法等。 由于文件中的记录不能像向量空间的数据那样“移动”，故 只能通过复制整个文件的方法实现插人、删除和修改等更新 操作。我们也可以用批量处理方式实现顺序文件的更新。 顺序文件主要优点是连续存取的速度较快。顺序文件具有连 续存取特点。当文件中第i个记录刚被存取过，而下一个要 存取的是第i+1个记录，则这种存取将会很快完成。
多级索引是一种静态索引，多级索引的各级索引均为顺序表 ，结构简单，修改很不方便，每次修改都要重组索引。 当数据文件在使用过程中记录变动较多时，利用二叉排序树 (或AVL树)、B_树(或其变型)等树表结构建立的索引，为动 态索引。 树表结构建立的索引的特点为插入、删除方便，本身是层次 结构，无须建立多级索引，建立索引表的过程即为排序过程 。当记录数不很多，内存足以容纳整个索引表时，可采用二 叉排序树(或AVL树)作索引；当文件很大时，索引表(树表) 本身也在外存，查找索引时访问外存的次数恰为查找路径上 的结点数。采用m阶B-树(或其变型)作为索引表为宜。 由于访问外存的时间比内存中查找的时间大得多，所以外存 的索引表的查找性能主要着眼于访问外存的次数，即索引表 的深度。
顺序存取：存取下一个逻辑记录。 直接存取：存取第i个逻辑记录。 按关键字存取：给定一个值，查询一个或一批关键字与给定值相关 的记录。对数据库文件可以有如下四种查询方式： 简单询问：只询问单个关键字等于给定值的记录。 范围询问：只询问单个关键字属于某个范围内的所有记录。 函数询问：规定单个关键字的某个函数，询问该函数的某个值。 布尔询问：以上三种询问用布尔运算(与、或、非)组合起来的询 问。