文件在现代计算机的应用领域中,数据处理是一个重要方面 。
数据处理是对各种类型的大批量的数据进行收集,存储,排序,检索,计算,修改,输出等分析和加工处理的过程 。 例如,用计算机进行企业管理,财务工资管理,仓库物资管理,情报检索,统计报表等都涉及到数据存放到外存储器上 。 有时,为了长期保存原始数据和加工处理过的数据,也需要将这些数据以文件的形式存放在外存上 。 学完本章读者应能掌握文件的概念,逻辑特性,物理结构和基本操作 。
文件的基本概念与文件有关的基本术语有以下几个：
数据项：数据项是文件中可使用的不可分的最小数据单位 。 一个数据项由若干个字符或数字组成,它代表某一事物的一种属性 。 数据项又称为数据域 。 例如,个人书库中的登录号,书号,书名,作者,出版社和价格等等都是数据项 。
记录：记录是由一个或多个数据项根据一定的目的而组成的数据项集合 。 例如,由登录号,书号,书名,作者,出版社和价格等数据项组成的集合是一个职工记录 。
文件：文件是大量性质相同的记录组成的集合。
关键字：是能够区别文件中各记录的域 。 通常,把能唯一标识一个记录的关键字称为主关键字；而那些不能唯一标识一个记录的关键字称为次关键字；由两个以上关键字组成的关键字称为复合关键字 。
在表 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所示的个人书库文件是按关键字登录号排序的文件,它存放到外存的连续存储区后便得到一个按关键字排序的顺序文件 。
顺序文件的基本优点是在连续存取时速度较快 。 例如,如果文件中的第 i个记录刚被存取过,而下一个要存取的记录就是第 i+1个记录,则此次存取将会很快完成 。 磁带是比较适用于这种应用的外存设备 。 存放于磁带上的文件也只能是顺序文件,这是由磁带的物理特性决定的 。 存放于磁盘上的文件,既可以是顺序文件,也可以是索引结构或其它结构类型的文件 。
当需要对磁带顺序文件进行检索时,一般是采用顺序扫描的方式来检索满足查询条件的记录 。 例如,若要检索第 i
个记录,则必须先检索前面的 i-1个记录 。 为了提高平均检索效率,可采用批量处理技术 。 如果将对文件的多个检索请求加以积累和排序,则形成一个称为待办文件 （ 或事务文件 ） 的文件 。 如果将被查询的文件称为主文件,则批量检索就是按照待办文件的要求成批地检索主文件 。 批量检索对于实时应用来说是不适宜的,因为实时查询要求响应时间快,而在很短的时间间隔内,积累的批处理文件规模太小,不能表现出它的优越性 。
在磁带顺序文件中插入记录，只能加在文件的末尾，不能插在两个原有记录之间。修改记录，即使在新旧记录等长的情况下，将新记录写在旧记录的位置上，一般不但不可能完全重合，甚至还会破坏邻近记录的信息。因此，修改一个磁带文件，需要用另一条磁带将原文件复制过来，在复制过程中进行插入、删除、修改记录的操作。为了提高效率，修改一个顺序文件，也采用成批处理技术。这种批量修改方式很适用于银行帐户结算管理系统。例如，可把一天的零星支取和存入分别作为记录收集在一起，构成为一个待办文件，在当天下班时再按照待办文件进行批量修改主文件（头天下班修改过的主文件）的工作，便得到一个新主文件。
索引文件顺序文件的查询速度很慢 。 采用索引文件可以提高检索效率 。 实际上,在前面的章节中我们已经运用了索引技术 。
索引用来表示关键字与相应记录的存储地址之间的对应关系 。 换言之,索引指出了记录在存储器中的存储地址 。
设记录 Ri的关键字为 Ki,Ri在外存中的存储地址为 Ai,则 （ Ki,Ai） 称为记录 Ri的索引项 。 索引表 （ 简称索引 ）
是索引项的集合 。 如果文件中的每个记录都有一个索引项,则这样的索引称为稠密索引 。 如果多个记录只有一个索引项,则这样的索引称为非稠密索引 。 带有索引的文件称为索引文件 。 索引也称为目录 。
索引文件在外存 （ 磁盘,磁鼓等 ） 中可分为两个存储区：索引区和记录区 （ 数据区 ） 。 索引表中的索引项顺序存放在索引区中,但为了便于检索,索引项一般按关键字的大小次序排列 。 文件中的记录按输入的先后次序存放到记录区；记录区按关键字大小次序排列的索引文件称为索引顺序文件 。 对于索引顺序文件,可以不必使用稠密索引,只为一个记录块 （ 含多个有序记录 ） 建立一个索引项 。 记录区不按关键字大小次序排列的索引文件称为索引非顺序文件,这时应使用稠密索引 。 图 10-2所示的个人书库 （ 价格 ） 索引文件,是一个索引非顺序文件 。
通常,索引项所含的数据信息比记录少得多,因而索引所需的存储空间比文件本身 （ 记录区 ） 所需要的存储空间少得多 。 在文件的记录数较少的情况下,可以为每个记录建立一个索引项 。 文件建立时,开辟一个索引区,
一般固定在某个磁盘面的一个或多个磁道上 。 写入一个记录到记录区时,在索引区相应登入一个索引项,即把该记录的关键字 （ 主关键字 ） 和记录的存储地址顺序写入索引区 。 文件建立后,将索引区中的索引读入内存的缓冲区,按关键字进行内部排序 。 最后将排序好的索引项顺序写回到磁盘上的索引区 。
根据关键字查找索引文件的记录分两步进行 。 第 1步,访问外存的索引区,将索引读入内存缓冲区,使用顺序查找或折半查找法找出所查记录在外存数据区中的地址,这一过程称为预查找 。 第 2步,如果在预查中已找到了所查记录的地址,则第 2次访问外存,根据已查到的地址,读取所查的记录 。
删除一个记录时，只需删去相应的索引项，而不必移动数据区中的记录。插入一个新记录时，将记录放到记录区的末尾，在索引区登记相应的索引项，并对索引区中的索引项重新排序。
索引顺序文件在实际应用中，索引顺序文件是被经常采用的一种文件结构。它是在顺序文件的基础上，用增加索引的办法而形成的。文件中的记录按关键字大小顺序存放在磁盘的连续或相邻的存储区中。由于记录按关键字排序，因此不必为每一个记录设立一个索引项，而把文件划分为若干个记录块，只为每块中关键字最大（或最小）
的记录设置一个索引项。这种组织文件的方法称为索引顺序存取法 ISAM（ Indexed Sequential
Access Method），用这种方法建立起来的索引文件称为 ISAM文件，它是一种专为磁盘存取设计的文件组织方式。
由于磁盘是以盘组、柱面和磁道三级地址存取的设备，
则可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。文件的记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上，对同一柱面，则应按盘面的次序顺序存放。例如图 10-3
为存放在一个磁盘组上的 ISAM文件。每个柱面建立一个磁道索引，每个磁道索引项由两部分组成：基本索引项和溢出索引项，如图 10-4所示，每一部分都包括关键字和指针两项，前者表示该磁道中最大关键字，
后者指示该磁道中第一个记录的位置，柱面索引的每一个索引项也由关键字和指针两部分组成，前者表示该柱面中最末一个记录的关键字（最大关键字），后者指示该柱面上的磁道索引位置。柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，则可建立柱面索引的索引 —— 主索引。
在 ISAM文件上检索记录时,先从主索引出发找到相应的柱面索引,再从柱面索引找到记录所在柱面的磁道索引,最后从磁道索引找到记录所在磁道的第一个记录的位置,由此出发在该磁道上进行顺序查找直到找到为止；反之,若找遍该磁道而不存在此记录,则表明该文件中无此记录 。
从图 10-3中还可以看到,每个柱面上还开辟有一个溢出区；并且,磁道索引项中有溢出索引项,
这是为插入记录所设置的 。 由于 ISAM文件中记录是按关键字顺序存放的,则在插入记录时需移动记录并将同一磁道上最后一个记录移至溢出区,同时修改磁道索引项 。 通常溢出区可有三种设置方法,（ 1） 集中存放 —— 整个文件设一个大的单一的溢出区； （ 2） 分散存放 ——
每个柱面设一个溢出区； （ 3） 集中与分散相结合 —— 溢出时记录先移至每个柱面各自的溢出区,待满之后再使用公共溢出区 。
每个柱面的基本区是顺序存储结构,而溢出区是链表结构 。 同一磁道溢出的记录由指针相链,该磁道索引的溢出索引项中的关键字指示该磁道溢出的记录的最大关键字；而指针则指示在溢出区中的第一个记录 。 图 10-5所示为插入记录和溢出处理的具体例子 。
其中 （ a） 为插入前的某一柱面上的状态； （ b） 为插入 R65时,将第二道中关键字大于 65的记录顺次后移,且使 R90溢出至溢出区的情况； （ c） 为插入 R65之后的状态,此时 2道的基本索引项的关键字改为 80,且溢出索引项的关键字改为 90,其指针指向第 4道第一个记录即 R90； （ d） 是相继插入 R95和 R83后的状态 。 在 R95插入在第 3道的第一个记录的位置而使 R145溢出 。 而由于
80<83<90,则 R83被直接插入到溢出区,作为第 2道在溢出区的第一个记录,并将它的指针指向 R90的位置,同时修改第 2道索引的溢出索引项的指针指向 R83。
ISAM文件中删除记录的操作比插入简单得多，只需找到待删除的记录，在其存储位置上作删除标记即可，而不需要移动记录或改变指针。则在经过多次的增删后，文件的结构可能变得很不合理。此时，大量得记录进入溢出区，而基本区中又浪费很多空间。因此，通常需要周期地整理 ISAM文件。把记录读入内存，重新排列，复制成一个新的 ISAM文件，填满基本区而空出溢出区。
直接存取文件直接存取文件指的是利用杂凑 （ Hash） 法进行组织的文件 。 它类似于哈希表,
即根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上,故又称散列文件 。
与哈希表不同的是,对于文件来说,磁盘上的文件记录通常是成组存放的 。
若干个记录组成一个存储单位,在散列文件中这个存储单位叫作桶 。 一个桶能存放的逻辑记录的总数称为桶的容量 。 假如一个桶能存放 m个记录,即 m个同义词的记录可以存放在同一地址的桶中,当第 m+1个同义词出现时则发生,溢出,。 处理溢出也可采用哈希表中处理冲突的各种方法；但对散列文件,主要采用链地址法 。
当发生“溢出”时，需要将第 m+1个同义词存放到另一个桶中，通常称此桶为“溢出桶”；相对地，称前 m个同义词存放的桶为“基桶”。溢出桶可以有多个，它们和基桶大小相同，相互之间用指针相链接。当在基桶中没有找到待查记录时，就顺指针所指到溢出桶中进行查找。因此，希望同一散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一柱面上。
例如，某 i文件有 18个记录，其关键字分别为 28,19,13，
93,89,14,55,69,8,9,16,21,33,81,62,11，
34,35。用除留余数法作哈希函数 H（ key） =key MOD 7。
桶的容量 m=3，基本桶数 =7，由此得到的散列文件如图
10-6所示。
桶编号 基桶 溢出桶
28 14 21 35 ^
8 ^
93 9 16 ^
^
81 11 ^
19 89 33 ^
13 55 69 62 34 ^
图 10- 6 散列文件示例在散列文件中进行查找时,首先根据给定值 k求得哈希地址 （ 即基桶号 ）,将基桶的记录读入内存进行顺序查找,若找到关键字等于 k
的记录,则检索成功；若基桶内没有填满记录或其指针域为空
（ 即无溢出桶 ） 则文件内不含有待查的记录；否则根据指针域的值的指示将溢出桶的记录读入内存继续进行顺序查找,直至检索成功或不成功 。 在散列文件中,装填因子 α=n/bm。 其中,n为文件的记录数,b为桶数,m为桶的容量 。 而存取桶数的期望值
α=1+α/2。 在散列文件中删除记录仅需要对被删除记录作一标记即可 。
总之，散列文件的优点是：插入、删除方便，存取速度比索引文件要快；不需要索引区，节省存储空间。其缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式只有简单询问；并且在经过多次的插入、删除之后，也可能造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记录。此时亦需重组文件。
多关键字文件主关键字（ With more than one key）文件的特点是，在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其他类型的询问检索。因此，对多关键字文件，
尚需建立一系列的次关键字索引。次关键字索引的主关键字索引所不同的是，每个索引项应包含次关键字、具有同一次关键字的多个记录的主关键字或或物理记录号。多重表文件和倒排文件是两种多关键字文件的组织方法。
多重表文件多重表文件 （ Multilist file） 的特点是：记录按主关键字的顺序构成一个串联文件,并建立主关键字的索引 （ 称为主索引 ） ；对每个次关键字项建立次关键字索引 （ 称为次索引 ）,所有具有同一次关键字的记录构成一个链表 。 主索引为非稠密索引
（ 一组记录建立一个索引项 ）,次索引为稠密索引 （ 每个记录建立一个索引项 ） 。
每个索引包括次关键字,头指针和链表长度 。
例如,图 10-7所示为一个多重表文件 。 其中,工号为主关键字,记录按工号顺序链接 。
对工号非稠密索引,分成 3个子链表 。 其索引如图 10-8（ b） 所示,索引项中的主关键字为各组中的最大值 。 职称,专业为两个次关键字项,它们的索引如图 10-8
（ c）,（ d） 所示 。 具有同次关键字的记录链接在同一链表中 。 有了这些次关键字索引,根据关键字值找到链表的头指针,然后从头指针出发可列出链表中所有记录 。 例如,要查询数学专业的教授,可以从,专业,索引表中查找到,数学,
的头指针和表长,从而可读取到相应的记录,再查看其中哪些记录的,职称,为
,教授,即可 。 此查询也可从,职称,索引表入手 。 显然,较好的方法是先读长度较短的链表中的记录 。
在多重表中插入一个新记录是很容易的，只要修改指针，将记录插在链表的头指针之后。但是，要删去一个记录却很繁琐，需要在每个次关键字的链表中删去该记录。
倒排文件倒排文件（ Inverted file）和多重表文件的区别在于次关键字索引的结构不同。倒排文件的次关键字索引称为倒排表。在倒排表的索引项中没有头指针和链表长度项，而直接用一项存放具有同一关键字的所有记录的物理记录号或主关键字。
值得注意的是，倒排表中具有一次关键字的记录号是有序排列的。上李文件的倒排表如图 10-8所示。
在倒排文件中检索记录较快,特别是处理多个次关键字检索 。 在处理各种次关键字的询问时,只要在次关键字索引中找出有关的指针集合,再对这些指针集合进行交,并,差等逻辑运算,就可求出符合查询条件的记录指针,然后按指针到外存去存取记录 。 如前例,
要查询数学专业的教授,只要分别在,职称,索引表上找,教授,,在,专业,索引表上找,数学,,得到指针集 A={2,6},B={2,5,9}。 由 A与 B的交集 {2}
得到指针 2,即可根据指针访问外存读取相应 2号记录 。
在插入和删除记录时,倒排表也要作相应修改,同时需移动索引项中的记录号以保持其有序排列 。
倒排文件的缺点是：各倒排表的长度不同，同一倒排表中各项长度也不同，这给文件的维护带来困难。而且倒排表需要额外存储空间。
本章小结本章主要介绍了如下一些基本概念：
数据项,数据项是文件中可使用的不可分的最小数据单位 。 一个数据项由若干个字符或数字组成,它代表某一事物的一种属性 。 数据项又称为数据域 。
记录,记录是由一个或多个数据项根据一定的目的而组成的数据项集合文件,文件是大量性质相同的记录组成的集合 。
关键字,是能够区别文件中各记录的域 。 通常,把能唯一标识一个记录的关键字称为主关键字；而那些不能唯一标识一个记录的关键字称为次关键字；由两个以上关键字组成的关键字称为复合关键字 。
文件的主要操作有：插入,删除,修改,检索等 。
文件的物理结构是指文件在外存上的组织形式。按照文件的检索方式和物理结构，文件分为顺序文件、索引文件、索引顺序文件、直接存取文件、
链接文件和多重链表文件、倒排文件。按所存放的外存设备，文件又可以分为磁带文件和磁盘文件等几类。
数据处理是对各种类型的大批量的数据进行收集,存储,排序,检索,计算,修改,输出等分析和加工处理的过程 。 例如,用计算机进行企业管理,财务工资管理,仓库物资管理,情报检索,统计报表等都涉及到数据存放到外存储器上 。 有时,为了长期保存原始数据和加工处理过的数据,也需要将这些数据以文件的形式存放在外存上 。 学完本章读者应能掌握文件的概念,逻辑特性,物理结构和基本操作 。
文件的基本概念与文件有关的基本术语有以下几个：
数据项：数据项是文件中可使用的不可分的最小数据单位 。 一个数据项由若干个字符或数字组成,它代表某一事物的一种属性 。 数据项又称为数据域 。 例如,个人书库中的登录号,书号,书名,作者,出版社和价格等等都是数据项 。
记录：记录是由一个或多个数据项根据一定的目的而组成的数据项集合 。 例如,由登录号,书号,书名,作者,出版社和价格等数据项组成的集合是一个职工记录 。
文件：文件是大量性质相同的记录组成的集合。
关键字：是能够区别文件中各记录的域 。 通常,把能唯一标识一个记录的关键字称为主关键字；而那些不能唯一标识一个记录的关键字称为次关键字；由两个以上关键字组成的关键字称为复合关键字 。
在表 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所示的个人书库文件是按关键字登录号排序的文件,它存放到外存的连续存储区后便得到一个按关键字排序的顺序文件 。
顺序文件的基本优点是在连续存取时速度较快 。 例如,如果文件中的第 i个记录刚被存取过,而下一个要存取的记录就是第 i+1个记录,则此次存取将会很快完成 。 磁带是比较适用于这种应用的外存设备 。 存放于磁带上的文件也只能是顺序文件,这是由磁带的物理特性决定的 。 存放于磁盘上的文件,既可以是顺序文件,也可以是索引结构或其它结构类型的文件 。
当需要对磁带顺序文件进行检索时,一般是采用顺序扫描的方式来检索满足查询条件的记录 。 例如,若要检索第 i
个记录,则必须先检索前面的 i-1个记录 。 为了提高平均检索效率,可采用批量处理技术 。 如果将对文件的多个检索请求加以积累和排序,则形成一个称为待办文件 （ 或事务文件 ） 的文件 。 如果将被查询的文件称为主文件,则批量检索就是按照待办文件的要求成批地检索主文件 。 批量检索对于实时应用来说是不适宜的,因为实时查询要求响应时间快,而在很短的时间间隔内,积累的批处理文件规模太小,不能表现出它的优越性 。
在磁带顺序文件中插入记录，只能加在文件的末尾，不能插在两个原有记录之间。修改记录，即使在新旧记录等长的情况下，将新记录写在旧记录的位置上，一般不但不可能完全重合，甚至还会破坏邻近记录的信息。因此，修改一个磁带文件，需要用另一条磁带将原文件复制过来，在复制过程中进行插入、删除、修改记录的操作。为了提高效率，修改一个顺序文件，也采用成批处理技术。这种批量修改方式很适用于银行帐户结算管理系统。例如，可把一天的零星支取和存入分别作为记录收集在一起，构成为一个待办文件，在当天下班时再按照待办文件进行批量修改主文件（头天下班修改过的主文件）的工作，便得到一个新主文件。
索引文件顺序文件的查询速度很慢 。 采用索引文件可以提高检索效率 。 实际上,在前面的章节中我们已经运用了索引技术 。
索引用来表示关键字与相应记录的存储地址之间的对应关系 。 换言之,索引指出了记录在存储器中的存储地址 。
设记录 Ri的关键字为 Ki,Ri在外存中的存储地址为 Ai,则 （ Ki,Ai） 称为记录 Ri的索引项 。 索引表 （ 简称索引 ）
是索引项的集合 。 如果文件中的每个记录都有一个索引项,则这样的索引称为稠密索引 。 如果多个记录只有一个索引项,则这样的索引称为非稠密索引 。 带有索引的文件称为索引文件 。 索引也称为目录 。
索引文件在外存 （ 磁盘,磁鼓等 ） 中可分为两个存储区：索引区和记录区 （ 数据区 ） 。 索引表中的索引项顺序存放在索引区中,但为了便于检索,索引项一般按关键字的大小次序排列 。 文件中的记录按输入的先后次序存放到记录区；记录区按关键字大小次序排列的索引文件称为索引顺序文件 。 对于索引顺序文件,可以不必使用稠密索引,只为一个记录块 （ 含多个有序记录 ） 建立一个索引项 。 记录区不按关键字大小次序排列的索引文件称为索引非顺序文件,这时应使用稠密索引 。 图 10-2所示的个人书库 （ 价格 ） 索引文件,是一个索引非顺序文件 。
通常,索引项所含的数据信息比记录少得多,因而索引所需的存储空间比文件本身 （ 记录区 ） 所需要的存储空间少得多 。 在文件的记录数较少的情况下,可以为每个记录建立一个索引项 。 文件建立时,开辟一个索引区,
一般固定在某个磁盘面的一个或多个磁道上 。 写入一个记录到记录区时,在索引区相应登入一个索引项,即把该记录的关键字 （ 主关键字 ） 和记录的存储地址顺序写入索引区 。 文件建立后,将索引区中的索引读入内存的缓冲区,按关键字进行内部排序 。 最后将排序好的索引项顺序写回到磁盘上的索引区 。
根据关键字查找索引文件的记录分两步进行 。 第 1步,访问外存的索引区,将索引读入内存缓冲区,使用顺序查找或折半查找法找出所查记录在外存数据区中的地址,这一过程称为预查找 。 第 2步,如果在预查中已找到了所查记录的地址,则第 2次访问外存,根据已查到的地址,读取所查的记录 。
删除一个记录时，只需删去相应的索引项，而不必移动数据区中的记录。插入一个新记录时，将记录放到记录区的末尾，在索引区登记相应的索引项，并对索引区中的索引项重新排序。
索引顺序文件在实际应用中，索引顺序文件是被经常采用的一种文件结构。它是在顺序文件的基础上，用增加索引的办法而形成的。文件中的记录按关键字大小顺序存放在磁盘的连续或相邻的存储区中。由于记录按关键字排序，因此不必为每一个记录设立一个索引项，而把文件划分为若干个记录块，只为每块中关键字最大（或最小）
的记录设置一个索引项。这种组织文件的方法称为索引顺序存取法 ISAM（ Indexed Sequential
Access Method），用这种方法建立起来的索引文件称为 ISAM文件，它是一种专为磁盘存取设计的文件组织方式。
由于磁盘是以盘组、柱面和磁道三级地址存取的设备，
则可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。文件的记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上，对同一柱面，则应按盘面的次序顺序存放。例如图 10-3
为存放在一个磁盘组上的 ISAM文件。每个柱面建立一个磁道索引，每个磁道索引项由两部分组成：基本索引项和溢出索引项，如图 10-4所示，每一部分都包括关键字和指针两项，前者表示该磁道中最大关键字，
后者指示该磁道中第一个记录的位置，柱面索引的每一个索引项也由关键字和指针两部分组成，前者表示该柱面中最末一个记录的关键字（最大关键字），后者指示该柱面上的磁道索引位置。柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，则可建立柱面索引的索引 —— 主索引。
在 ISAM文件上检索记录时,先从主索引出发找到相应的柱面索引,再从柱面索引找到记录所在柱面的磁道索引,最后从磁道索引找到记录所在磁道的第一个记录的位置,由此出发在该磁道上进行顺序查找直到找到为止；反之,若找遍该磁道而不存在此记录,则表明该文件中无此记录 。
从图 10-3中还可以看到,每个柱面上还开辟有一个溢出区；并且,磁道索引项中有溢出索引项,
这是为插入记录所设置的 。 由于 ISAM文件中记录是按关键字顺序存放的,则在插入记录时需移动记录并将同一磁道上最后一个记录移至溢出区,同时修改磁道索引项 。 通常溢出区可有三种设置方法,（ 1） 集中存放 —— 整个文件设一个大的单一的溢出区； （ 2） 分散存放 ——
每个柱面设一个溢出区； （ 3） 集中与分散相结合 —— 溢出时记录先移至每个柱面各自的溢出区,待满之后再使用公共溢出区 。
每个柱面的基本区是顺序存储结构,而溢出区是链表结构 。 同一磁道溢出的记录由指针相链,该磁道索引的溢出索引项中的关键字指示该磁道溢出的记录的最大关键字；而指针则指示在溢出区中的第一个记录 。 图 10-5所示为插入记录和溢出处理的具体例子 。
其中 （ a） 为插入前的某一柱面上的状态； （ b） 为插入 R65时,将第二道中关键字大于 65的记录顺次后移,且使 R90溢出至溢出区的情况； （ c） 为插入 R65之后的状态,此时 2道的基本索引项的关键字改为 80,且溢出索引项的关键字改为 90,其指针指向第 4道第一个记录即 R90； （ d） 是相继插入 R95和 R83后的状态 。 在 R95插入在第 3道的第一个记录的位置而使 R145溢出 。 而由于
80<83<90,则 R83被直接插入到溢出区,作为第 2道在溢出区的第一个记录,并将它的指针指向 R90的位置,同时修改第 2道索引的溢出索引项的指针指向 R83。
ISAM文件中删除记录的操作比插入简单得多，只需找到待删除的记录，在其存储位置上作删除标记即可，而不需要移动记录或改变指针。则在经过多次的增删后，文件的结构可能变得很不合理。此时，大量得记录进入溢出区，而基本区中又浪费很多空间。因此，通常需要周期地整理 ISAM文件。把记录读入内存，重新排列，复制成一个新的 ISAM文件，填满基本区而空出溢出区。
直接存取文件直接存取文件指的是利用杂凑 （ Hash） 法进行组织的文件 。 它类似于哈希表,
即根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上,故又称散列文件 。
与哈希表不同的是,对于文件来说,磁盘上的文件记录通常是成组存放的 。
若干个记录组成一个存储单位,在散列文件中这个存储单位叫作桶 。 一个桶能存放的逻辑记录的总数称为桶的容量 。 假如一个桶能存放 m个记录,即 m个同义词的记录可以存放在同一地址的桶中,当第 m+1个同义词出现时则发生,溢出,。 处理溢出也可采用哈希表中处理冲突的各种方法；但对散列文件,主要采用链地址法 。
当发生“溢出”时，需要将第 m+1个同义词存放到另一个桶中，通常称此桶为“溢出桶”；相对地，称前 m个同义词存放的桶为“基桶”。溢出桶可以有多个，它们和基桶大小相同，相互之间用指针相链接。当在基桶中没有找到待查记录时，就顺指针所指到溢出桶中进行查找。因此，希望同一散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一柱面上。
例如，某 i文件有 18个记录，其关键字分别为 28,19,13，
93,89,14,55,69,8,9,16,21,33,81,62,11，
34,35。用除留余数法作哈希函数 H（ key） =key MOD 7。
桶的容量 m=3，基本桶数 =7，由此得到的散列文件如图
10-6所示。
桶编号 基桶 溢出桶
28 14 21 35 ^
8 ^
93 9 16 ^
^
81 11 ^
19 89 33 ^
13 55 69 62 34 ^
图 10- 6 散列文件示例在散列文件中进行查找时,首先根据给定值 k求得哈希地址 （ 即基桶号 ）,将基桶的记录读入内存进行顺序查找,若找到关键字等于 k
的记录,则检索成功；若基桶内没有填满记录或其指针域为空
（ 即无溢出桶 ） 则文件内不含有待查的记录；否则根据指针域的值的指示将溢出桶的记录读入内存继续进行顺序查找,直至检索成功或不成功 。 在散列文件中,装填因子 α=n/bm。 其中,n为文件的记录数,b为桶数,m为桶的容量 。 而存取桶数的期望值
α=1+α/2。 在散列文件中删除记录仅需要对被删除记录作一标记即可 。
总之，散列文件的优点是：插入、删除方便，存取速度比索引文件要快；不需要索引区，节省存储空间。其缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式只有简单询问；并且在经过多次的插入、删除之后，也可能造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记录。此时亦需重组文件。
多关键字文件主关键字（ With more than one key）文件的特点是，在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其他类型的询问检索。因此，对多关键字文件，
尚需建立一系列的次关键字索引。次关键字索引的主关键字索引所不同的是，每个索引项应包含次关键字、具有同一次关键字的多个记录的主关键字或或物理记录号。多重表文件和倒排文件是两种多关键字文件的组织方法。
多重表文件多重表文件 （ Multilist file） 的特点是：记录按主关键字的顺序构成一个串联文件,并建立主关键字的索引 （ 称为主索引 ） ；对每个次关键字项建立次关键字索引 （ 称为次索引 ）,所有具有同一次关键字的记录构成一个链表 。 主索引为非稠密索引
（ 一组记录建立一个索引项 ）,次索引为稠密索引 （ 每个记录建立一个索引项 ） 。
每个索引包括次关键字,头指针和链表长度 。
例如,图 10-7所示为一个多重表文件 。 其中,工号为主关键字,记录按工号顺序链接 。
对工号非稠密索引,分成 3个子链表 。 其索引如图 10-8（ b） 所示,索引项中的主关键字为各组中的最大值 。 职称,专业为两个次关键字项,它们的索引如图 10-8
（ c）,（ d） 所示 。 具有同次关键字的记录链接在同一链表中 。 有了这些次关键字索引,根据关键字值找到链表的头指针,然后从头指针出发可列出链表中所有记录 。 例如,要查询数学专业的教授,可以从,专业,索引表中查找到,数学,
的头指针和表长,从而可读取到相应的记录,再查看其中哪些记录的,职称,为
,教授,即可 。 此查询也可从,职称,索引表入手 。 显然,较好的方法是先读长度较短的链表中的记录 。
在多重表中插入一个新记录是很容易的，只要修改指针，将记录插在链表的头指针之后。但是，要删去一个记录却很繁琐，需要在每个次关键字的链表中删去该记录。
倒排文件倒排文件（ Inverted file）和多重表文件的区别在于次关键字索引的结构不同。倒排文件的次关键字索引称为倒排表。在倒排表的索引项中没有头指针和链表长度项，而直接用一项存放具有同一关键字的所有记录的物理记录号或主关键字。
值得注意的是，倒排表中具有一次关键字的记录号是有序排列的。上李文件的倒排表如图 10-8所示。
在倒排文件中检索记录较快,特别是处理多个次关键字检索 。 在处理各种次关键字的询问时,只要在次关键字索引中找出有关的指针集合,再对这些指针集合进行交,并,差等逻辑运算,就可求出符合查询条件的记录指针,然后按指针到外存去存取记录 。 如前例,
要查询数学专业的教授,只要分别在,职称,索引表上找,教授,,在,专业,索引表上找,数学,,得到指针集 A={2,6},B={2,5,9}。 由 A与 B的交集 {2}
得到指针 2,即可根据指针访问外存读取相应 2号记录 。
在插入和删除记录时,倒排表也要作相应修改,同时需移动索引项中的记录号以保持其有序排列 。
倒排文件的缺点是：各倒排表的长度不同，同一倒排表中各项长度也不同，这给文件的维护带来困难。而且倒排表需要额外存储空间。
本章小结本章主要介绍了如下一些基本概念：
数据项,数据项是文件中可使用的不可分的最小数据单位 。 一个数据项由若干个字符或数字组成,它代表某一事物的一种属性 。 数据项又称为数据域 。
记录,记录是由一个或多个数据项根据一定的目的而组成的数据项集合文件,文件是大量性质相同的记录组成的集合 。
关键字,是能够区别文件中各记录的域 。 通常,把能唯一标识一个记录的关键字称为主关键字；而那些不能唯一标识一个记录的关键字称为次关键字；由两个以上关键字组成的关键字称为复合关键字 。
文件的主要操作有：插入,删除,修改,检索等 。
文件的物理结构是指文件在外存上的组织形式。按照文件的检索方式和物理结构，文件分为顺序文件、索引文件、索引顺序文件、直接存取文件、
链接文件和多重链表文件、倒排文件。按所存放的外存设备，文件又可以分为磁带文件和磁盘文件等几类。
