第十二章 文件 ￡12.1 有关文件的基本概念 ￡12.2 顺序文件 ￡12.3 索引文件 ￡12.4 ISAM和VSAM文件

Presentation on theme: "第十二章 文件 ￡12.1 有关文件的基本概念 ￡12.2 顺序文件 ￡12.3 索引文件 ￡12.4 ISAM和VSAM文件"— Presentation transcript:

1 第十二章 文件 ￡12.1 有关文件的基本概念 ￡12.2 顺序文件 ￡12.3 索引文件 ￡12.4 ISAM和VSAM文件
第十二章 文件 ￡12.1 有关文件的基本概念 ￡12.2 顺序文件 ￡12.3 索引文件 ￡12.4 ISAM和VSAM文件 ￡ ISAM文件 ￡ VSAM文件 ￡12.5 直接存取文件（散列文件） ￡12.6 多关键字文件 ￡ 多重表文件 ￡ 倒排文件

2 第十二章 文件 ￡12.1 有关文件的基本概念 文件是大量记录的集合。习惯上称存储在主存储器（内存储
第十二章 文件 文件是大量记录的集合。习惯上称存储在主存储器（内存储 器）中的记录集合为表，称存储在二级存储器（外存储器）中的 记录集合为文件。 ￡12.1 有关文件的基本概念 （1）文件及其类别 文件（file）：是由大量性质相同的记录组成的集合。 数据项：最基本的不可分的数据单位，是文件中可使用的数据的最小单位。 属性：记录中所有非关键字的数据项，称为记录的属性。 按记录的类型不同可分成： ①操作系统的文件： 操作系统中的文件仅是一维的连续的字符序列，无结构、无解释。 ②数据库文件： 数据库中的文件是带有结构的记录的集合。这类记录是由一个或 多个数据项组成的集合，它也是文件中可存取的数据的基本单位。 按记录中关键字的多少数据库文件可分成： 1.单关键字文件：文件中的记录只有一个唯一标识记录的主 关键字。 2.多关键字文件：文件中的记录除了含有一个主关键字外， 还含有若干个次关键字。

3 物理记录和逻辑记录之间可能存在下列3种关系：
按记录含有信息的长度不同可分成： ①定长记录文件：文件中每个记录含有的信息长度相同。 ②不定长记录文件：文件中每个记录含有的信息长度不等。 （2）记录的逻辑结构和物理结构 记录的逻辑结构：是指记录在用户或应用程序员面前呈现的方式，是用 户对数据的表示和存取方式。着眼于用户使用方便。 记录的物理结构：是数据在物理存储器上存储的方式，是数据的物理表 示和组织。着眼于提高存储空间的利用率和减少存取记录的时间。 物理记录和逻辑记录之间可能存在下列3种关系： ①一个物理记录存放一个逻辑记录； ②一个物理记录包含多个逻辑记录； ③多个物理记录表示一个逻辑记录。 （3）文件的操作（运算） 文件的检索： ①顺序存取：存取下一个逻辑记录。 ②直接存取：存取第i个逻辑记录。 ① ②两种存取方式都是根据记录序号(即记录存入文件时的顺序编号)或记录的相对位置进行存取的。

4 ③按关键字存取：给定一个值，查询一个或一批关键字与给定值
相关的记录。对数据库文件可以有如下4种查询方式： 1.简单询问：查询关键字等于给定值的记录。 2.区域询问：查询关键字属某个区域内的记录。 3.函数询问：给定关键字的某个函数。 4.布尔询问：以上3种询问用布尔运算组合起来的询问。 文件的修改： 文件的修改包括插入一个记录、删除一个记录和更新一个记录3种操作。 文件的操作可以有实时和批量两种不同方式。通常实时处理对应答时间要求 严格，应在接受询问之后几秒钟内完成检索和修改，而批量的处理则不然。 例如，银行的帐户系统需实时检索，但可进行批量修改，即可以 将一天的存款和提款记录在一个事务文件上，在一天的营业之后再进 行批量处理。 （4）文件的物理结构 文件的物理结构：文件在存储介质（磁盘或磁带）上的组织方式。 文件的基本组织方式： ①顺序组织； ②随机组织； ③链组织。

5 ￡12.2 顺序文件 （1）定义 顺序文件（Sequential File）：是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。 连续文件：次序相继的两个物理记录在存储介质上的存储位置是相邻的顺序文件。 串联文件：物理记录之间的次序由指针相链表示的顺序文件。 （2）特点 顺序文件是根据记录的序号或记录的相对位置来进行存取的文件 组织方式。它的特点是： ①存取第i个记录，必须先搜索在它之前的i－1个记录。 ②插入新的记录时只能加在文件的末尾。 ③若要更新文件中的某个记录，则必须将整个文件进行复制。 （3）磁带上顺序文件的批处理 主文件：待修改的原始文件。 事务文件：所有的修改请求集中构成的一个文件。

6 磁带文件的批处理过程： 首先对事务文件进行排序，然后将主文件和事务文件归并成 一个新的主文件。图12.1为这个过程的示意图。 终端 事务 文件 排序 有序的事务文件 主文件 新主文件 其中，主文件、事务文件和新的主文 件分别存放中一台磁带上。主文件按关键 字自小至大（或自大至小）顺序有序，事 务文件必须和主文件有相同的有序关系。 图12.1 磁带文件批处理示意图

7 在归并的过程中，顺序读出主文件与事务文件中的记录，比
较它们的关键字并分别进行处理。对于关键字不匹配的主文件中 的记录，则直接将其写入新主文件中。“更改”和“删除”记录时， 要求其关键字相匹配。“删去”不用写入，而“更改”则要将更改后 的新记录写入新主文件。“插入”时不要求关键字相匹配，可直接 将事务文件上要插入的记录写到新主文件的适当位置。 算法实现： 批处理的示意算法如算法12.1所示。算法中用到的各符号的含义说明如下： f——主文件；g——事务文件；h——新主文件。它们都按关键字递增 排序。事务文件的每个记录中，增设一个代码以示修改要求，其中：“I”表 示插入；“D”表示删去；“U”表示更改。 算法12.1如下： void MergeFile (FILE *f, FILE *g, FILE *h) { //由按关键字递增有序的非空顺序文件f和g归并得到新文件h， //三个文件均已打开，其中，f和g为只读文件，文件中各附加 //一个最大关键字记录，且g文件中对该记录的操作为插入。 // h为只写文件。 fread (*fr, sizeof(RcdType), 1, f); fread (*gr, sizeof(RcdType), 1, g);

8 while (!feof (f) | | !feof (g)) {
switch { case fr.key < gr.key: //复制“旧”主文件中记录 fwrite (*fr, sizeof(RcdType), 1, h); if (!feof (f)) fread (*fr, sizeof(RcdType), 1, f); break; case gr.code = = ‘D’ && fr.key = = gr.key: //删除”旧”主文件中记录,不复制 if (!feof (g)) fread (*gr, sizeof(RcdType), 1, g); case gr.code = = ‘I’ && fr.key > gr.key: //插入,函数P把gr加工为h的结构 fwrite (P(gr), sizeof(RcdType), 1, h);

9 case gr.code = = ‘U’ && fr.key = = gr.key:
//更改”旧”主文件中记录 fwrite (Q(fr, gr), sizeof(RcdType), 1, h); //函数Q将fr和gr归并成一个h结构的记录 if (!feof (f)) fread (*fr, sizeof(RcdType), 1, f); if (!feof (g)) fread (*gr, sizeof(RcdType), 1, g); break; default ERROR(); //其他均为出错情况 } // switch } // while } // MergeFile 分析批处理算法的时间： 假设主文件包含n个记录，事务文件包含m个记录。一般情况 下，事务文件较小，可以进行内部排序，则时间复杂度为 O(m*logm)。内部归并的时间复杂度为O(n＋m)，则总的内部处理 时间为O(m*logm＋n)。

10 假设所有的输入/输出都是通过缓冲区进行的，并假设缓冲区
大小为s（个记录），则整个批处理过程中读/写外存的次数为 ： (4)磁盘上顺序文件的批处理 磁盘上顺序文件的批处理和磁带文件类似，只是当修改项中没 有插入，且更新时不增加记录的长度时，可以不建立新的主文件， 而直接修改原来的主文件即可。显然，磁盘文件的批处理可以在一 台磁盘组上进行。

11 ￡12.3 索引文件 （1）基本术语 索引表：除了文件本身（称做数据区）之外，另建立的一 张指示逻辑记录和物理记录之间一一对应关系的表。
索引项：索引表中的每一项。总是按关键字（或逻辑记录 号）顺序排列。 索引文件：包括文件数据区和索引表两大部分的文件。 索引顺序文件：数据区中的记录也按关键字顺序排列的文件。 索引非顺序文件：数据区中的记录不按关键字顺序排列的文件。 稠密索引：由于数据文件中记录不按关键字顺序排列，则必须 对每个记录都建立一个索引项，如此建立的索引表称为稠密索引。 非稠密索引：数据文件中的记录按关键字顺序有序，则可对一 组记录建立一个索引项，这种索引表称为非稠密索引。

12 例如，图12.2为两个索引表的例子。 (不存在) 关键字ki 物理记录号 逻辑记录号 标识 物理记录号 图 索引表示例 （2）索引表的生成 索引表是由系统程序自动生成的。 在记录输入建立数据区的同时建立一个索引表，表中的索引 项按记录输入的先后次序排列，待全部记录输入完毕后再对索引 表进行排序。

13 例如，对应于图12.3(a)的时间文件，其索引表如图12.3(b)，
而图12.3(c)为文件建立输入过程中建立的索引表。 张珊 程序员 . 李四 维修员 . 王红 程序员 . 刘琪 穿孔员 . 物理记录号 职工号 姓名 职 务 其他 (a) 文件数据区

14 关键字 物理记录号 关键字 物理记录号 1 2 3 (b) 索引表 (c) 输入过程中建立的索引表 图 索引非顺序文件示例 （3）索引文件的检索 检索方式：直接存取或按关键字（进行简单询问）存取。 检索过程：首先，查找索引表，若索引表上存在该记录，则根 据索引项的指示读取外存上该记录;否则说明外存上不存在该记录， 也就不需要访问外存。

15 由于索引项的长度比记录小得多，则通常可将索引表一次读 入内存，由此再索引文件中进行检索只访问外存两次，即一次读
索引，一次读记录。并且由于索引表是有序的，则查找索引表时 可用折半查找法。 （4）索引文件的修改 ①删除操作：删除一个记录时，仅需删去相应的索引项； ②插入操作：插入一个记录时，应将记录置于数据区的末尾，同时再 索引表中插入索引项； ③更新操作：更新记录时，应将更新后的记录置于数据区末尾，同时 修改索引表中相应的索引项。 （5）多级索引 查找表：对索引表建立的索引。 例如，假设图12.3(b)的索引表需占3个物理块的外存，每一 个物理块容纳3个索引，则建立的查找表如图12.4所示。检索记 录时，先查找查找表，再查索引表，然后读取记录。 最大关键字 物理块号 图 图12.3(b)中索引表的索引

16 通常最高可有四级索引： 上述的多级索引是一种静态索引，各级索引均为顺序表结构。其结构简 单，但修改很不方便，每次修改都要重组索引。因此，当数据文件在使用过 程中记录变动较多时，应采用动态索引。如,二叉排序树（或二叉平衡树）、 B-树以及键树。

17 ￡12.4 ISAM和VSAM文件 ￡12.4.1 ISAM文件 （1）定义
索引顺序存取方法ISAM(Indexed Sequential Access Method)： 是一种专为磁盘存取设计的文件组织方式。 由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可 对磁盘上的数据文件建立盘组、柱面和磁道三级索引。 例如，图12.5为存放一个磁盘组上的ISAM文件。每个柱面建立 一个磁道索引，每个磁道索引项由：基本索引项和溢出索引项两部 分组成，如图12.6所示。 ①磁道索引项： 基本索引项： 关键字：表示该磁道中最末一个记录的关键字（在此为最 大关键字）。 指针：指示该磁道中第一个记录的位置。 溢出索引项： 关键字：表示该磁道溢出的记录的最大关键字。 指针：指示在溢出区中的第一个记录。 ②柱面索引项： 关键字：表示该柱面中最末一个记录的关键字（最大关键字）。 指针：指示该柱面上的磁道索引位置。

18 磁道索引 50 柱面索引 主索引 溢出区 图12.5 ISAM文件结构示例 返 回 磁道索引 柱面C1 164 330 柱面C2 柱面C3
R164 磁道索引 50 磁道索引 柱面C1 柱面索引 主索引 R14 R21 R45 R47 R50 164 330 溢出区 柱面C2 柱面C3 R189 R215 R330 1100 4150 810 3843 215 R3843 R4150 图12.5 ISAM文件结构示例 返 回

19 关键字 指针 关键字 指针 基本索引项 溢出索引项 返 回 图12.6 磁道索引项结构 柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时， 则可建立柱面索引的索引——主索引。 （2）ISAM文件的检索 在ISAM文件上检索记录的过程： 先从主索引出发找到相应的柱面索引，再从柱面索引找到记录 所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个 记录的位置，由此出发在该磁道上进行顺序查找直至找到为止；反 之，若找遍该磁道而不存在此记录，则表明该文件中无此记录。 （3）溢出区和插入操作 溢出区是为插入记录所设置的。每个柱面的基本区是顺序存储 结构，而溢出区是链表结构。同一磁道溢出的记录由指针相链。

20 ①集中存放：整个文件设一个大的单一的溢出区。 ②分散存放：每个柱面设一个溢出区。图12.5即为此设置法。
溢出区的设置方法： ①集中存放：整个文件设一个大的单一的溢出区。 ②分散存放：每个柱面设一个溢出区。图12.5即为此设置法。 ③集中与分散相结合：溢出时记录先移至每个柱面各自的溢出 区，待满之后再使用公共溢出区。 例子，图12.7所示为记录和溢出处理的具体例子。 T2’ T3’1 基本索引项 溢出索引项 基本索引项 溢出索引项 道索引 R50 R60 R R80 R90 R100 R120 R R136 R145 T2 T3 T4 溢出区 基本区 (a) 插入前 说 明

21 R R60 R R80 R90 溢出区 基本区 插入 插入记录 R65 R90 (b) 插入R65时记录移动的情形 T2’ T4’ T3’1 道索引 R / R50 R60 R R70 R80 R100 R120 R R136 R145 T2 T3 T4 溢出区 基本区 (c) 插入R65后 T2’ T4’ T3’ T4’2 R50 R60 R R70 R80 R95 R100 R R130 R136 T2 T3 T4 溢出区 基本区 R / R / R / (d) 先插入R95再插入R83后 说 明

22 其中：(a)为插入前的某一柱面上的状态；
(b)为插入R65时，将第2道中关键字大于65的记录顺次后移， 且使R90溢出至溢出区的情况； (c)为插入R65之后的状态，此时2道的基本索引项的关键字 改为80，且溢出索引项的关键字改为90，其指针指向第 4道第一个记录即R90。 (d)是相继插入R95和R83后的状态，R95插入在第3道的第一个记录的位置 而使R145溢出。而由于80<83<90则R83被直接插入道溢出区，作为第2 道在溢出区的第一个记录，并将它的指针指向R90的位置，同时修改 第2道索引的溢出索引项的指针指向R83。 （4）删除操作 ISAM文件中删除记录，只需找到待删除的记录，在其存储位置 上做删除标记即可，而不需要移动记录或改变指针。但在经过多次的 增删后，文件的结构可能变得很不合理。此时，大量的记录进入溢出 区，而基本区中又浪费很大空间。由此，通常需要周期地整理ISAM 文件。把记录读入内存，重新排列，复制成一个新的ISAM文件，填 满基本区而空出溢出区。

23 （5）柱面索引的位置 假设文件占有n个柱面，柱面索引在第x柱面上，则磁头移动 距离的平均值为： 令 ，得到 。这就是说，柱面索引应放在数据文件的 中间位置的柱面上。

24 ￡12.4.2 VSAM文件 （1）定义 虚拟存储存取方法VSAM（Virtual Storage Access Methed）：
该方法利用了操作系统的虚拟存储器的功能，给用户提供方便。 对用户来说，文件只有控制区间和控制区域等逻辑存储单位，与 外存储器中柱面、磁道等具体存储单位没有必然的联系。 控制区间（Control Interval）：它是一个I/O操作的基本单位，由一组连续的存储单元组成。同一文件上控制区间的大小相同。 控制区域（Control Range）：顺序集中一个结点连同对应所 有控制区间形成的一个整体。 每个控制区间可视为一个逻辑磁道，而每个控制区域可 视为一个逻辑柱面。

25 VSAM文件的结构如图12.8所示。它有3部分组成：索引集、
顺序集和数据集。 控制区间 控制区域 索引集 顺序集 数据集 B+树 图12.8 VSAM文件的结构示意图 文件的记录均存放在数据中。顺序集和索引集一起构成一棵B＋树， 为文件的索引部分。顺序集中存放每个控制区间的索引项。每个控制区 间的索引项由两部分信息组成，即该控制区间中最大关键字和指向控制 区间的指针。若干相邻控制区间的索引项形成顺序集中的一个结点，结 点之间用指针相链结，而每个结点又在其上一层的结点中建有索引，且 逐层向上建立索引。所有的索引项都由最大关键字和指针两部分信息组 成，这些高层的索引项形成B＋树的非终端结点。因此，VSAM文件既 可在顺序集中进行顺序存取，又可从最高层的索引（B＋树的根结点） 出发进行按关键字存取。

26 在VSAM文件中，记录可以是不定长的，则在控制区间中除
了存放记录本身以外，还有每个记录的控制信息和整个区间的控 制信息，控制区间的结构如图12.9所示。在控制区间上存取一个 记录时需从控制区间的两端出发同时向中间扫描。 记 记 未利用 记录n 记录1 控制空 录 录 的 的 的控制 间的控 n 空闲空间 控制信息 信息 制信息 图12.9 控制区间的结构示意图 （2）删除操作 在VASM文件中删除记录是，需将同一控制区间中较删除 记录关键字大的记录向前移动，把空间留给以后插入的新记录。 若整个控制区间变空，则需修改顺序集中相应的索引项。

27 （3）插入操作 VSAM文件中没有溢出区，解决插入的办法是在初建文件时留有 空间。一是每个控制区间内不填满记录，在最末一个记录和控制信息 之间留有孔隙；二是在每个控制区域中有一些完全空的控制区间，并 在顺序集的索引中指明这些空区间。当插入记录时，大多数的新记录 能插入到相应的控制区间内，但要注意为了保持区间内记录的关键字 自小至大有序，则需将区间内关键字大于插入记录关键字的记录向控 制信息的方向移动。若在若干记录插入之后控制区间已满，则在下一 个记录插入时要进行控制区间的分裂，既将近乎一半的记录移到同一 控制区域中全空的控制区间中，并修改顺序集中相应索引。倘若控制 区域中已经没有全空的控制区间，则要进行控制区域的分裂，此时顺 序集中的结点亦要分裂，由此尚需修改索引集中的结点信息。 （4）VASM文件的特点 优点：动态地分配和释放存储空间，不需要对文件进行重组，并能较快地对插入的记录进行查找，查找一个后插入记录的时间与查找一个原有记录的时间是相同的。 缺点：占有较多的存储空间，一般只能保持约75％的存储 空间利用率。

28 ￡12.5 直接存取文件（散列文件） （1）定义 直接存取文件指的是利用杂凑（Hash）法进行组织的文件。
它类似于哈希表，既根据文件中关键字的特点设计一种哈希函数 和处理冲突的方法将记录散列到存储设备上，故又称散列文件。 与哈希表不同的是，对于文件来说，磁盘上的文件记录通常是成 组存放的。 （2）溢出处理 若干个记录组成一个存储单位，在散列文件中，这个存储单位 叫做桶（Bucket）。 假若一个桶能存放m个记录，这就是说，m个同义词的记录可以 存放在同一地址的桶中，而当第m＋1个同义词出现时才发生“溢出”。 对散列文件主要采用链地址法处理溢出。 当发生“溢出”时，需要将第m＋1个同义词存放到另一个桶中， 通常称此桶为“溢出桶”；相对地，称前m个同义词存放的桶为“基桶”。 溢出桶和基桶大小相同，相互之间用指针相链接。当在基桶中没有待 查记录时，就顺指针所指到溢出桶中进行查找。因此，希望同一散列 地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一 柱面上。

29 （3）图形表示 例如，某一文件有18个记录，其关键字分别为278，109，063， 930，589，184，505，269，008，083，164，215，330，810，620， 110，384，355。桶的容量为m＝3，桶数b＝7。用除留余数法作哈 希函数H(key)＝key MOD 7。由此得到的直接存取文件如图12.10所 示。 桶编号 基桶 溢出桶 2 图 直接存取文件示例

30 （4）查找操作 查找过程：首先根据给定值求得哈希地址（即基桶号），将 基桶的记录读入内存进行顺序查找，若找到关键字等于给定值的 记录，则检索成功；否则，若基桶内没有填满记录或其指针域为 空，则文件内不含有待查记录；否则根据指针域的值的指示将溢 出桶的记录读入内存继续进行顺序查找，直至检索成功或不成功。 因此，总的查找时间为： T = a (te + ti) 其中：a为存取桶数的期望值（相当于哈希表中的平均查找长度），对链地址 处理溢出来说，a = 1 + α/2；te为存取一个桶所需的时间；ti为在内存中顺序 查找一个记录所需的时间。 α为装载因子，在散列文件中： 其中：n为文件的记录数，b为桶数，m为桶的容量。 （5）删除操作 在直接存取文件中删除记录时，仅需对被删记录作一标记即可。

31 （6）直接存取文件的特点 优点：文件随机存放，记录不需进行排序；插入、删除方便， 存取速度快，不需要索引区，节省存储空间。 缺点：不能进行顺序存取，只能按关键字随机存取，且询问 方式限于简单询问，并且在经过多次的 插入、删除之后，也可能 造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记录。 此时亦需重组文件。

32 ￡12.6 多关键字文件 ￡12.6.1 多重表文件 特点：在对文件进行检索操作是，不仅对主关键字进行简
单询问，还经常需要对关键字进行其他类型的询问检索。 ￡ 多重表文件 （1）特点 多重表文件（Multilist File）的特点是： ①记录按主关键字的顺序构成一个串联文件，并建立主关键字的索引 （称为主索引）； ②对每一个次关键字项建立次关键字索引（称为次索引），所有具有 同一次关键字的记 录构成一个链表。 主索引为非稠密索引，次索引为稠密索引。每个索引项包括次关键字、头 指针和链表长度。 （2）例子 例如，图12.10所示为一个多重表文件。其中，学号为主关键 字，记录按学号顺序链接，为了查找方便，分成3个子链表，其索 引如图12.10(b)所示，索引项中的主关键字为各子表中的最大值。 专业、已修学分和选修课目为3个次关键字项，它们的索引如图 12.10(c)~(e)所示，具有相同次关键字的记录链接在同一链表中。

33 01 王 雯 软件 丙 02 丁 03 马小雁 软件 甲 04 丙 03 03 阮 森 计算机 ^ 乙 05 丙 04 丁 05 苏明明 ^ 应用 甲 06 丙 08 05 田 永 计算机 ^ 乙 07 丁 09 06 杨 青 应用 甲 07 薛平平 软件 ^ 甲 08 乙 ^ 崔子健 ^ 软件 ^ 甲 09 丙 ^ 09 王 洪 应用 甲 10 丁 ^ 10 刘 倩 ^ 应用 ^ 甲 ^ 记录号 姓名 学 号 专 业 已修学分 选 修 课 程 (a) 数据文件 主关键字 头指针 次关键字 头指针 长度 软 件 计算机 应 用 (b) 主关键字索引 (c) “专业”索引 返 回

34 次关键字 头指针 长度 甲 乙 丙 丁 次关键字 头指针 长度 350~ 400~ (d) “已修学分”索引 (e) “选修课目”索引 图 多重表文件示例 返 回

35 ￡12.6.2 倒排文件 倒排文件和多重表文件的区别在于次关键字索引的结构不 同。通常称倒排文件中的次关键字索引为倒排表，具有相同次
关键字的记录之间不设指针相链，而在倒排表中该次关键字的 一项中存放这些记录的物理记录号。 例如，上例文件的倒排表如图12.11所示。 软 件 01，02，07，08 计算机 ，05 应 用 04，06，09，10 (a) 专业倒排表 350~ ，05，06，07，09，10 400~ ，03，04，08 (b) 已修学分倒排表

36 甲 ，04，06，07，08，09，10 乙 ，05，07 丙 ，02，03，04，08 丁 01，03，05，09 (c) 选修课目倒排表 图 倒排文件索引示例 倒排表作索引的好处在于检索记录较快。特别是对某些询问，不 用读取记录，就可得到解答，入询问“软件”专业的学生中有否选课程 “乙”的，则只要将“软件”索引中的记录号和“乙”索引中的记录号作求 “交”的集合元素即可。 在插入和删除记录时，倒排表也要作相应的修改，值得注意的是 倒排表中具有同一次关键字的记录号是有序排列的，则修改时要作相 应移动。

37 若数据文件非串链文件，而是索引顺序文件（如ISAM文件），
则倒排表中应存放记录的主关键字而不是物理记录号。 倒排文件的缺点是维护困难。在同一索引表中，不同的关键字 其记录数不同，各倒排表的长度不等，同一倒排表中各项长度也不 等。