第十二章文件

1、第十二章第十二章文件文件 12.1 有关文件的基本概念有关文件的基本概念 12.2 顺序文件顺序文件 12.3 索引文件索引文件 12.4 isam和和vsam文件文件 12.4.1 isam文件文件 12.4.2 vsam文件文件 12.5 直接存取文件（散列文件）直接存取文件（散列文件） 12.6 多关键字文件多关键字文件 12.6.1 多重表文件多重表文件 12.6.2 倒排文件倒排文件 第十二章第十二章文件文件 文件是大量记录的集合。习惯上称存储在主存储器（内存储文件是大量记录的集合。习惯上称存储在主存储器（内存储 器）中的记录集合为表，称存储在二级存储器（外存储器）中的器）中的记录集

2、合为表，称存储在二级存储器（外存储器）中的 记录集合为文件。记录集合为文件。 12.1 有关文件的基本概念有关文件的基本概念 （1）文件及其类别）文件及其类别 文件文件（file）：是由大量性质相同的记录组成的集合。）：是由大量性质相同的记录组成的集合。 数据项数据项：最基本的不可分的数据单位，是文件中可使用的数据的最小单位。：最基本的不可分的数据单位，是文件中可使用的数据的最小单位。 属性属性：记录中所有非关键字的数据项，称为记录的属性。：记录中所有非关键字的数据项，称为记录的属性。 按记录的类型不同可分成：按记录的类型不同可分成： 操作系统的文件：操作系统的文件： 操作系统中的文件仅是一维

3、的连续的字符序列，无结构、无解释。操作系统中的文件仅是一维的连续的字符序列，无结构、无解释。 数据库文件：数据库文件： 数据库中的文件是带有结构的记录的集合。这类记录是由一个或数据库中的文件是带有结构的记录的集合。这类记录是由一个或 多个数据项组成的集合，它也是文件中可存取的数据的基本单位。多个数据项组成的集合，它也是文件中可存取的数据的基本单位。 按记录中关键字的多少数据库文件可分成：按记录中关键字的多少数据库文件可分成： 1.单关键字文件：文件中的记录只有一个唯一标识记录的主单关键字文件：文件中的记录只有一个唯一标识记录的主 关键字。关键字。 2.多关键字文件：文件中的记录除了含有一个主关

4、键字外，多关键字文件：文件中的记录除了含有一个主关键字外， 还含有若干个次关键字。还含有若干个次关键字。 按记录含有信息的长度不同可分成：按记录含有信息的长度不同可分成： 定长记录文件：文件中每个记录含有的信息长度相同。定长记录文件：文件中每个记录含有的信息长度相同。 不定长记录文件：文件中每个记录含有的信息长度不等。不定长记录文件：文件中每个记录含有的信息长度不等。 （2）记录的逻辑结构和物理结构）记录的逻辑结构和物理结构 记录记录的的逻辑结构逻辑结构：是指记录在用户或应用程序员面前呈现的方式，是用：是指记录在用户或应用程序员面前呈现的方式，是用 户对数据的表示和存取方式。着眼于用户使用方便

5、。户对数据的表示和存取方式。着眼于用户使用方便。 记录记录的的物理结构物理结构：是数据在物理存储器上存储的方式，是数据的物理表：是数据在物理存储器上存储的方式，是数据的物理表 示和组织。着眼于提高存储空间的利用率和减少存取记录的时间。示和组织。着眼于提高存储空间的利用率和减少存取记录的时间。 物理记录和逻辑记录之间可能存在下列物理记录和逻辑记录之间可能存在下列3种关系：种关系： 一个物理记录存放一个逻辑记录；一个物理记录存放一个逻辑记录； 一个物理记录包含多个逻辑记录；一个物理记录包含多个逻辑记录； 多个物理记录表示一个逻辑记录。多个物理记录表示一个逻辑记录。 （3）文件的操作（运算）文件的操

6、作（运算） 文件的检索：文件的检索： 顺序存取：存取下一个逻辑记录。顺序存取：存取下一个逻辑记录。 直接存取：存取第直接存取：存取第i个逻辑记录。个逻辑记录。 两种存取方式都是根两种存取方式都是根 据记录序号据记录序号(即记录存入即记录存入 文件时的顺序编号文件时的顺序编号)或记或记 录的相对位置进行存取的。录的相对位置进行存取的。 按关键字存取：给定一个值，查询一个或一批关键字与给定值按关键字存取：给定一个值，查询一个或一批关键字与给定值 相关的记录。对数据库文件可以有如下相关的记录。对数据库文件可以有如下4种查询方式：种查询方式： 1.简单询问：查询关键字等于给定值的记录。简单询问：查询关

7、键字等于给定值的记录。 2.区域询问：查询关键字属某个区域内的记录。区域询问：查询关键字属某个区域内的记录。 3.函数询问：给定关键字的某个函数。函数询问：给定关键字的某个函数。 4.布尔询问：以上布尔询问：以上3种询问用布尔运算组合起来的询问。种询问用布尔运算组合起来的询问。 文件的修改：文件的修改： 文件的修改包括插入一个记录、删除一个记录和更新一个记录文件的修改包括插入一个记录、删除一个记录和更新一个记录3种操作。种操作。 文件的操作可以有实时和批量两种不同方式。通常实时处理对应答时间要求文件的操作可以有实时和批量两种不同方式。通常实时处理对应答时间要求 严格，应在接受询问之后几秒钟内完

8、成检索和修改，而批量的处理则不然。严格，应在接受询问之后几秒钟内完成检索和修改，而批量的处理则不然。 例如，银行的帐户系统需实时检索，但可进行批量修改，即可以例如，银行的帐户系统需实时检索，但可进行批量修改，即可以 将一天的存款和提款记录在一个事务文件上，在一天的营业之后再进将一天的存款和提款记录在一个事务文件上，在一天的营业之后再进 行批量处理。行批量处理。 （4）文件的物理结构）文件的物理结构 文件文件的的物理结构物理结构：文件在存储介质（磁盘或磁带）上的组织方式。：文件在存储介质（磁盘或磁带）上的组织方式。 文件的基本组织方式：文件的基本组织方式： 顺序组织；顺序组织； 随机组织；随机组

9、织； 链组织。链组织。 12.2 顺序文件顺序文件 串联文件串联文件：物理记录之间的次序由指针相链表示的顺序文件。：物理记录之间的次序由指针相链表示的顺序文件。 （1）定义）定义 顺序文件顺序文件（sequential file）：是记录按其在文件中的逻辑）：是记录按其在文件中的逻辑 顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序 和逻辑记录的顺序是一致的。和逻辑记录的顺序是一致的。 连续文件连续文件：次序相继的两个物理记录在存储介质上的存储位：次序相继的两个物理记录在存储介质上的存储位 置是相邻的顺序文件。置是相邻的顺序文件。

10、 （2）特点）特点 顺序文件是根据记录的序号或记录的相对位置来进行存取的文件顺序文件是根据记录的序号或记录的相对位置来进行存取的文件 组织方式。它的特点是：组织方式。它的特点是： 存取第存取第i个记录，必须先搜索在它之前的个记录，必须先搜索在它之前的i1个记录。个记录。 插入新的记录时只能加在文件的末尾。插入新的记录时只能加在文件的末尾。 若要更新文件中的某个记录，则必须将整个文件进行复制。若要更新文件中的某个记录，则必须将整个文件进行复制。 （3）磁带上顺序文件的批处理）磁带上顺序文件的批处理 主文件主文件：待修改的原始文件。：待修改的原始文件。 事务文件事务文件：所有的修改请求集中构成的一

11、个文件。：所有的修改请求集中构成的一个文件。 磁带文件的批处理过程：磁带文件的批处理过程： 首先对事务文件进行排序，然后将主文件和事务文件归并成首先对事务文件进行排序，然后将主文件和事务文件归并成 一个新的主文件。图一个新的主文件。图12.1为这个过程的示意图。为这个过程的示意图。 终端终端 事务事务 文件文件 排序排序 有序的事务文件有序的事务文件主文件主文件 新主文件新主文件 图图12.1磁带文件批处理示意图磁带文件批处理示意图 其中，主文件、事务文件和新的主文其中，主文件、事务文件和新的主文 件分别存放中一台磁带上。主文件按关键件分别存放中一台磁带上。主文件按关键 字自小至大（或自大至小

12、）顺序有序，事字自小至大（或自大至小）顺序有序，事 务文件必须和主文件有相同的有序关系。务文件必须和主文件有相同的有序关系。 在归并的过程中，顺序读出主文件与事务文件中的记录，比在归并的过程中，顺序读出主文件与事务文件中的记录，比 较它们的关键字并分别进行处理。对于关键字不匹配的主文件中较它们的关键字并分别进行处理。对于关键字不匹配的主文件中 的记录，则直接将其写入新主文件中。的记录，则直接将其写入新主文件中。“更改更改”和和“删除删除”记录时，记录时， 要求其关键字相匹配。要求其关键字相匹配。“删去删去”不用写入，而不用写入，而“更改更改”则要将更改后则要将更改后 的新记录写入新主文件。的新

13、记录写入新主文件。“插入插入”时不要求关键字相匹配，可直接时不要求关键字相匹配，可直接 将事务文件上要插入的记录写到新主文件的适当位置。将事务文件上要插入的记录写到新主文件的适当位置。 算法实现：算法实现： 批处理的示意算法如算法批处理的示意算法如算法12.1所示。算法中用到的各符号的含义说明如下：所示。算法中用到的各符号的含义说明如下： f主文件；主文件；g事务文件；事务文件；h新主文件。它们都按关键字递增新主文件。它们都按关键字递增 排序。事务文件的每个记录中，增设一个代码以示修改要求，其中：排序。事务文件的每个记录中，增设一个代码以示修改要求，其中：“i”表表 示插入；示插入；“d”表示

14、删去；表示删去；“u”表示更改。表示更改。 void mergefile (file *f, file *g, file *h) /由按关键字递增有序的非空顺序文件由按关键字递增有序的非空顺序文件f和和g归并得到新文件归并得到新文件h， /三个文件均已打开，其中，三个文件均已打开，其中，f和和g为只读文件，文件中各附加为只读文件，文件中各附加 /一个最大关键字记录，且一个最大关键字记录，且g文件中对该记录的操作为插入。文件中对该记录的操作为插入。 / h为只写文件。为只写文件。 fread (*fr, sizeof(rcdtype), 1, f); fread (*gr, sizeof(rcd

15、type), 1, g); 算法算法12.1如下：如下： while (!feof (f) | | !feof (g) switch case fr.key gr.key: /插入插入,函数函数p把把gr加工为加工为h的结构的结构 fwrite (p(gr), sizeof(rcdtype), 1, h); if (!feof (g) fread (*gr, sizeof(rcdtype), 1, g); break; case gr.code = = u /函数函数q将将fr和和gr归并成一个归并成一个h结构的记录结构的记录 if (!feof (f) fread (*fr, sizeof(

16、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

17、m)，则总的内部处理，则总的内部处理 时间为时间为o(m*logmn)。 磁盘上顺序文件的批处理和磁带文件类似，只是当修改项中没磁盘上顺序文件的批处理和磁带文件类似，只是当修改项中没 有插入，且更新时不增加记录的长度时，可以不建立新的主文件，有插入，且更新时不增加记录的长度时，可以不建立新的主文件， 而直接修改原来的主文件即可。显然，磁盘文件的批处理可以在一而直接修改原来的主文件即可。显然，磁盘文件的批处理可以在一 台磁盘组上进行。台磁盘组上进行。 (4)磁盘上顺序文件的批处理磁盘上顺序文件的批处理 假设所有的输入假设所有的输入/输出都是通过缓冲区进行的，并假设缓冲区输出都是通过缓冲区进行的，

18、并假设缓冲区 大小为大小为s（个记录），则整个批处理过程中读（个记录），则整个批处理过程中读/写外存的次数为写外存的次数为 ： s nm s m *2*2 12.3 索引文件索引文件 非稠密索引非稠密索引：数据文件中的记录按关键字顺序有序，则可对一：数据文件中的记录按关键字顺序有序，则可对一 组记录建立一个索引项，这种索引表称为非稠密索引。组记录建立一个索引项，这种索引表称为非稠密索引。 （1）基本术语）基本术语 索引表索引表：除了文件本身（称做数据区）之外，另建立的一：除了文件本身（称做数据区）之外，另建立的一 张指示逻辑记录和物理记录之间一一对应关系的表。张指示逻辑记录和物理记录之间一一对

19、应关系的表。 索引项索引项：索引表中的每一项。总是按关键字（或逻辑记录：索引表中的每一项。总是按关键字（或逻辑记录 号）顺序排列。号）顺序排列。 索引文件索引文件：包括文件数据区和索引表两大部分的文件。：包括文件数据区和索引表两大部分的文件。 索引顺序文件索引顺序文件：数据区中的记录也按关键字顺序排列的文件。：数据区中的记录也按关键字顺序排列的文件。 索引非顺序文件索引非顺序文件：数据区中的记录不按关键字顺序排列的文件。：数据区中的记录不按关键字顺序排列的文件。 稠密索引稠密索引：由于数据文件中记录不按关键字顺序排列，则必须：由于数据文件中记录不按关键字顺序排列，则必须 对每个记录都建立一个索

20、引项，如此建立的索引表称为稠密索引。对每个记录都建立一个索引项，如此建立的索引表称为稠密索引。 例如，图例如，图12.2为两个索引表的例子。为两个索引表的例子。 0 1 4 101 15 1 1 7 119 04 2 0(不存在不存在) 123 31 3 1 10 125 11 关键字关键字ki 物理记录号物理记录号逻辑记录号逻辑记录号 标识标识 物理记录号物理记录号 图图12.2 索引表示例索引表示例 在记录输入建立数据区的同时建立一个索引表，表中的索引在记录输入建立数据区的同时建立一个索引表，表中的索引 项按记录输入的先后次序排列，待全部记录输入完毕后再对索引项按记录输入的先后次序排列，待

21、全部记录输入完毕后再对索引 表进行排序。表进行排序。 （2）索引表的生成）索引表的生成 索引表是由系统程序自动生成的。索引表是由系统程序自动生成的。 例如，对应于图例如，对应于图12.3(a)的时间文件，其索引表如图的时间文件，其索引表如图12.3(b)， 而图而图12.3(c)为文件建立输入过程中建立的索引表。为文件建立输入过程中建立的索引表。 10129 张珊张珊 程序员程序员 . 10305 李四李四 维修员维修员 . 10402 王红王红 程序员程序员 . 10538 刘琪刘琪 穿孔员穿孔员 . 10831 . . 10943 . . 11017 . . 11248 . . 物理记录号

22、物理记录号 职工号职工号 姓名姓名 职职 务务 其他其他 (a) 文件数据区文件数据区 图图12.3 索引非顺序文件示例索引非顺序文件示例 (b) 索引表索引表(c) 输入过程中建立的索引表输入过程中建立的索引表 02 104 29 101 05 103 05 103 17 110 02 104 29 101 38 105 31 108 31 108 38 105 43 109 43 109 17 110 48 112 48 112 关键字关键字 物理记录号物理记录号关键字关键字物理记录号物理记录号 1 2 3 （3）索引文件的检索）索引文件的检索 检索方式：直接存取或按关键字（进行简单询问）

23、存取。检索方式：直接存取或按关键字（进行简单询问）存取。 检索过程：首先，查找索引表，若索引表上存在该记录，则根检索过程：首先，查找索引表，若索引表上存在该记录，则根 据索引项的指示读取外存上该记录据索引项的指示读取外存上该记录;否则说明外存上不存在该记录，否则说明外存上不存在该记录， 也就不需要访问外存。也就不需要访问外存。 由于索引项的长度比记录小得多，则通常可将索引表一次读由于索引项的长度比记录小得多，则通常可将索引表一次读 入内存，由此再索引文件中进行检索只访问外存两次，即一次读入内存，由此再索引文件中进行检索只访问外存两次，即一次读 索引，一次读记录。并且由于索引表是有序的，则查找索

24、引表时索引，一次读记录。并且由于索引表是有序的，则查找索引表时 可用折半查找法。可用折半查找法。 （4）索引文件的修改）索引文件的修改 删除操作：删除一个记录时，仅需删去相应的索引项；删除操作：删除一个记录时，仅需删去相应的索引项； 插入操作：插入一个记录时，应将记录置于数据区的末尾，同时再插入操作：插入一个记录时，应将记录置于数据区的末尾，同时再 索引表中插入索引项；索引表中插入索引项； 更新操作：更新记录时，应将更新后的记录置于数据区末尾，同时更新操作：更新记录时，应将更新后的记录置于数据区末尾，同时 修改索引表中相应的索引项。修改索引表中相应的索引项。 （5）多级索引）多级索引 查找表：

25、对索引表建立的索引。查找表：对索引表建立的索引。 例如，假设图例如，假设图12.3(b)的索引表需占的索引表需占3个物理块的外存，每一个物理块的外存，每一 个物理块容纳个物理块容纳3个索引，则建立的查找表如图个索引，则建立的查找表如图12.4所示。检索记所示。检索记 录时，先查找查找表，再查索引表，然后读取记录。录时，先查找查找表，再查索引表，然后读取记录。 图图12.4 图图12.3(b)中索引表的索引中索引表的索引 最大关键字最大关键字 物理块号物理块号 17 1 38 2 46 3 通常最高可有四级索引：通常最高可有四级索引： 第三查找表第二查找表查找表索引表数据文件 上述的多级索引是一

26、种静态索引，各级索引均为顺序表结构。其结构简上述的多级索引是一种静态索引，各级索引均为顺序表结构。其结构简 单，但修改很不方便，每次修改都要重组索引。因此，当数据文件在使用过单，但修改很不方便，每次修改都要重组索引。因此，当数据文件在使用过 程中记录变动较多时，应采用动态索引。如程中记录变动较多时，应采用动态索引。如,二叉排序树（或二叉平衡树）、二叉排序树（或二叉平衡树）、 b-树以及键树。树以及键树。 12.4 isam和和vsam文件文件 12.4.1 isam文件文件 （1）定义）定义 索引顺序存取方法索引顺序存取方法isam(indexed sequential access meth

27、od)： 是一种专为磁盘存取设计的文件组织方式。是一种专为磁盘存取设计的文件组织方式。 由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可 对磁盘上的数据文件建立盘组、柱面和磁道三级索引。对磁盘上的数据文件建立盘组、柱面和磁道三级索引。 例如，例如，图图12.5为存放一个磁盘组上的为存放一个磁盘组上的isam文件。每个柱面建立文件。每个柱面建立 一个磁道索引，每个磁道索引项由：基本索引项和溢出索引项两部一个磁道索引，每个磁道索引项由：基本索引项和溢出索引项两部 分组成，如分组成，如图图12.6所示。所示。 磁道索引项：磁道索引项： 基本索引

28、项：基本索引项： 关键字：表示该磁道中最末一个记录的关键字（在此为最关键字：表示该磁道中最末一个记录的关键字（在此为最 大关键字）。大关键字）。 指针：指示该磁道中第一个记录的位置。指针：指示该磁道中第一个记录的位置。 溢出索引项：溢出索引项： 关键字：表示该磁道溢出的记录的最大关键字。关键字：表示该磁道溢出的记录的最大关键字。 指针：指示在溢出区中的第一个记录。指针：指示在溢出区中的第一个记录。 柱面索引项：柱面索引项： 关键字：表示该柱面中最末一个记录的关键字（最大关键字）。关键字：表示该柱面中最末一个记录的关键字（最大关键字）。 指针：指示该柱面上的磁道索引位置。指针：指示该柱面上的磁道

29、索引位置。 图图12.5isam文件结构示例文件结构示例 r164 磁道索引磁道索引50 磁道索引磁道索引 柱面柱面c1 柱面索引柱面索引 主索引主索引 r14 r21 r45 r47 r50 164 164164 330 溢出区溢出区 溢出区溢出区 溢出区溢出区 柱面柱面c2 柱面柱面c3 r189r215 r330 1100 4150 4150 4150 810 330 3843 215 磁道索引磁道索引 磁道索引磁道索引 r3843 r4150 返返 回回 关键字关键字 指针指针 关键字关键字 指针指针 基本索引项基本索引项 溢出索引项溢出索引项 图图12.6磁道索引项结构磁道索引项结构

30、 柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时， 则可建立柱面索引的索引则可建立柱面索引的索引主索引主索引。 在在isam文件上检索记录的过程：文件上检索记录的过程： 先从主索引出发找到相应的柱面索引，再从柱面索引找到记录先从主索引出发找到相应的柱面索引，再从柱面索引找到记录 所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个 记录的位置，由此出发在该磁道上进行顺序查找直至找到为止；反记录的位置，由此出发在该磁道上进行顺序查找直至找到为止；反 之，若找遍该磁道而不

31、存在此记录，则表明该文件中无此记录。之，若找遍该磁道而不存在此记录，则表明该文件中无此记录。 （2）isam文件的检索文件的检索 （3）溢出区和插入操作）溢出区和插入操作 溢出区是为插入记录所设置的。每个柱面的基本区是顺序存储溢出区是为插入记录所设置的。每个柱面的基本区是顺序存储 结构，而溢出区是链表结构。同一磁道溢出的记录由指针相链。结构，而溢出区是链表结构。同一磁道溢出的记录由指针相链。 返返 回回 溢出区的设置方法：溢出区的设置方法： 集中存放：整个文件设一个大的单一的溢出区。集中存放：整个文件设一个大的单一的溢出区。 分散存放：每个柱面设一个溢出区。图分散存放：每个柱面设一个溢出区。图

32、12.5即为此设置法。即为此设置法。 集中与分散相结合：溢出时记录先移至每个柱面各自的溢出集中与分散相结合：溢出时记录先移至每个柱面各自的溢出 区，待满之后再使用公共溢出区。区，待满之后再使用公共溢出区。 例子，图例子，图12.7所示为记录和溢出处理的具体例子。所示为记录和溢出处理的具体例子。 (a) 插入前插入前 r50r60r70 r80r90 r100r120 r130 r136 r145 t2 t3 t4溢出区溢出区 基本区基本区 90 t21 145 t31 基本索引项基本索引项 溢出索引项溢出索引项 基本索引项基本索引项 溢出索引项溢出索引项 道索引道索引 说说 明明 r50 r6

33、0 r70 r80 r90 溢出区溢出区 基本区基本区 插入插入 插入记录插入记录 r65 r90 (b) 插入插入r65时记录移动的情形时记录移动的情形 80 t21 90 t41 145 t31 道索引道索引 r90 / r50r60r65 r70r80 r100r120 r130 r136 r145 t2 t3 t4溢出区溢出区 基本区基本区 (c) 插入插入r65后后 80 t21 90 t41 136 t31 145 t42 (d) 先插入先插入r95再插入再插入r83后后 r50r60r65 r70r80 r95r100 r120 r130 r136 t2 t3 t4溢出区溢出区

34、基本区基本区 r90 / r145 / r83 / 说说 明明 其中：其中：(a)为插入前的某一柱面上的状态；为插入前的某一柱面上的状态； (b)为插入为插入r65时，将第时，将第2道中关键字大于道中关键字大于65的记录顺次后移，的记录顺次后移， 且使且使r90溢出至溢出区的情况；溢出至溢出区的情况； (c)为插入为插入r65之后的状态，此时之后的状态，此时2道的基本索引项的关键字道的基本索引项的关键字 改为改为80，且溢出索引项的关键字改为，且溢出索引项的关键字改为90，其指针指向第，其指针指向第 4道第一个记录即道第一个记录即r90。 (d)是相继插入是相继插入r95和和r83后的状态，后

35、的状态，r95插入在第插入在第3道的第一个记录的位置道的第一个记录的位置 而使而使r145溢出。而由于溢出。而由于808390则则r83被直接插入道溢出区，作为第被直接插入道溢出区，作为第2 道在溢出区的第一个记录，并将它的指针指向道在溢出区的第一个记录，并将它的指针指向r90的位置，同时修改的位置，同时修改 第第2道索引的溢出索引项的指针指向道索引的溢出索引项的指针指向r83。 （4）删除操作）删除操作 isam文件中删除记录，只需找到待删除的记录，在其存储位置文件中删除记录，只需找到待删除的记录，在其存储位置 上做删除标记即可，而不需要移动记录或改变指针。但在经过多次的上做删除标记即可，而

36、不需要移动记录或改变指针。但在经过多次的 增删后，文件的结构可能变得很不合理。此时，大量的记录进入溢出增删后，文件的结构可能变得很不合理。此时，大量的记录进入溢出 区，而基本区中又浪费很大空间。由此，通常需要周期地整理区，而基本区中又浪费很大空间。由此，通常需要周期地整理isam 文件。把记录读入内存，重新排列，复制成一个新的文件。把记录读入内存，重新排列，复制成一个新的isam文件，填文件，填 满基本区而空出溢出区。满基本区而空出溢出区。 （5）柱面索引的位置）柱面索引的位置 假设文件占有假设文件占有n个柱面，柱面索引在第个柱面，柱面索引在第x柱面上，则磁头移动柱面上，则磁头移动 距离的平均

37、值为：距离的平均值为： )()( 1 11 n xi x i xiix n s 2 ) 1( ) 1( 1 2 nn xnx n 令令0 dx sd ，得到，得到 2 1 n x。这就是说，柱面索引应放在数据文件的。这就是说，柱面索引应放在数据文件的 中间位置的柱面上。中间位置的柱面上。 12.4.2 vsam文件文件 控制区域控制区域（control range）：顺序集中一个结点连同对应所）：顺序集中一个结点连同对应所 有控制区间形成的一个整体。有控制区间形成的一个整体。 （1）定义）定义 虚拟存储存取方法虚拟存储存取方法vsam（virtual storage access methed

38、）：）： 该方法利用了操作系统的虚拟存储器的功能，给用户提供方便。该方法利用了操作系统的虚拟存储器的功能，给用户提供方便。 对用户来说，文件只有控制区间和控制区域等逻辑存储单位，与对用户来说，文件只有控制区间和控制区域等逻辑存储单位，与 外存储器中柱面、磁道等具体存储单位没有必然的联系。外存储器中柱面、磁道等具体存储单位没有必然的联系。 控制区间控制区间（control interval）：它是一个）：它是一个i/o操作的基本单位，操作的基本单位， 由一组连续的存储单元组成。同一文件上控制区间的大小相同。由一组连续的存储单元组成。同一文件上控制区间的大小相同。 每个控制区间可视为一个逻辑磁道，

39、而每个控制区域可每个控制区间可视为一个逻辑磁道，而每个控制区域可 视为一个逻辑柱面。视为一个逻辑柱面。 vsam文件的结构如图文件的结构如图12.8所示。它有所示。它有3部分组成：索引集、部分组成：索引集、 顺序集和数据集。顺序集和数据集。 图图12.8 vsam文件的结构示意图文件的结构示意图 控制区间控制区间控制区域控制区域 索引集索引集 顺序集顺序集 数据集数据集 b+树树 文件的记录均存放在数据中。顺序集和索引集一起构成一棵文件的记录均存放在数据中。顺序集和索引集一起构成一棵b 树， 树， 为文件的索引部分。顺序集中存放每个控制区间的索引项。每个控制区为文件的索引部分。顺序集中存放每个

40、控制区间的索引项。每个控制区 间的索引项由两部分信息组成，即该控制区间中最大关键字和指向控制间的索引项由两部分信息组成，即该控制区间中最大关键字和指向控制 区间的指针。若干相邻控制区间的索引项形成顺序集中的一个结点，结区间的指针。若干相邻控制区间的索引项形成顺序集中的一个结点，结 点之间用指针相链结，而每个结点又在其上一层的结点中建有索引，且点之间用指针相链结，而每个结点又在其上一层的结点中建有索引，且 逐层向上建立索引。所有的索引项都由最大关键字和指针两部分信息组逐层向上建立索引。所有的索引项都由最大关键字和指针两部分信息组 成，这些高层的索引项形成成，这些高层的索引项形成b树的非终端结点。

41、因此，树的非终端结点。因此，vsam文件既文件既 可在顺序集中进行顺序存取，又可从最高层的索引（可在顺序集中进行顺序存取，又可从最高层的索引（b 树的根结点） 树的根结点） 出发进行按关键字存取。出发进行按关键字存取。 在在vsam文件中，记录可以是不定长的，则在控制区间中除文件中，记录可以是不定长的，则在控制区间中除 了存放记录本身以外，还有每个记录的控制信息和整个区间的控了存放记录本身以外，还有每个记录的控制信息和整个区间的控 制信息，控制区间的结构如图制信息，控制区间的结构如图12.9所示。在控制区间上存取一个所示。在控制区间上存取一个 记录时需从控制区间的两端出发同时向中间扫描。记录时

42、需从控制区间的两端出发同时向中间扫描。 记记 记记 未利用未利用 记录记录n 记录记录1 控制空控制空 录录 录录 的的 的的 的控制的控制 间的控间的控 1 n 空闲空间空闲空间 控制信息控制信息 信息信息 制信息制信息 图图12.9控制区间的结构示意图控制区间的结构示意图 （2）删除操作）删除操作 在在vasm文件中删除记录是，需将同一控制区间中较删除文件中删除记录是，需将同一控制区间中较删除 记录关键字大的记录向前移动，把空间留给以后插入的新记录。记录关键字大的记录向前移动，把空间留给以后插入的新记录。 若整个控制区间变空，则需修改顺序集中相应的索引项。若整个控制区间变空，则需修改顺序集

43、中相应的索引项。 （4）vasm文件的特点文件的特点 优点：动态地分配和释放存储空间，不需要对文件进行重优点：动态地分配和释放存储空间，不需要对文件进行重 组，并能较快地对插入的记录进行查找，查找一个后插入记录组，并能较快地对插入的记录进行查找，查找一个后插入记录 的时间与查找一个原有记录的时间是相同的。的时间与查找一个原有记录的时间是相同的。 缺点：占有较多的存储空间，一般只能保持约缺点：占有较多的存储空间，一般只能保持约75的存储的存储 空间利用率。空间利用率。 （3）插入操作）插入操作 vsam文件中没有溢出区，解决插入的办法是在初建文件时留有文件中没有溢出区，解决插入的办法是在初建文件

44、时留有 空间。一是每个控制区间内不填满记录，在最末一个记录和控制信息空间。一是每个控制区间内不填满记录，在最末一个记录和控制信息 之间留有孔隙；二是在每个控制区域中有一些完全空的控制区间，并之间留有孔隙；二是在每个控制区域中有一些完全空的控制区间，并 在顺序集的索引中指明这些空区间。当插入记录时，大多数的新记录在顺序集的索引中指明这些空区间。当插入记录时，大多数的新记录 能插入到相应的控制区间内，但要注意为了保持区间内记录的关键字能插入到相应的控制区间内，但要注意为了保持区间内记录的关键字 自小至大有序，则需将区间内关键字大于插入记录关键字的记录向控自小至大有序，则需将区间内关键字大于插入记录

45、关键字的记录向控 制信息的方向移动。若在若干记录插入之后控制区间已满，则在下一制信息的方向移动。若在若干记录插入之后控制区间已满，则在下一 个记录插入时要进行控制区间的分裂，既将近乎一半的记录移到同一个记录插入时要进行控制区间的分裂，既将近乎一半的记录移到同一 控制区域中全空的控制区间中，并修改顺序集中相应索引。倘若控制控制区域中全空的控制区间中，并修改顺序集中相应索引。倘若控制 区域中已经没有全空的控制区间，则要进行控制区域的分裂，此时顺区域中已经没有全空的控制区间，则要进行控制区域的分裂，此时顺 序集中的结点亦要分裂，由此尚需修改索引集中的结点信息。序集中的结点亦要分裂，由此尚需修改索引集

46、中的结点信息。 12.5 直接存取文件（散列文件）直接存取文件（散列文件） （1）定义）定义 直接存取文件直接存取文件指的是利用杂凑（指的是利用杂凑（hash）法进行组织的文件。）法进行组织的文件。 它类似于哈希表，既根据文件中关键字的特点设计一种哈希函数它类似于哈希表，既根据文件中关键字的特点设计一种哈希函数 和处理冲突的方法将记录散列到存储设备上，故又称和处理冲突的方法将记录散列到存储设备上，故又称散列文件散列文件。 与哈希表不同的是，对于文件来说，磁盘上的文件记录通常是成与哈希表不同的是，对于文件来说，磁盘上的文件记录通常是成 组存放的。组存放的。 （2）溢出处理）溢出处理 若干个记录组

47、成一个存储单位，在散列文件中，这个存储单位若干个记录组成一个存储单位，在散列文件中，这个存储单位 叫做叫做桶桶（bucket）。）。 假若一个桶能存放假若一个桶能存放m个记录，这就是说，个记录，这就是说，m个同义词的记录可以个同义词的记录可以 存放在同一地址的桶中，而当第存放在同一地址的桶中，而当第m1个同义词出现时才发生个同义词出现时才发生“溢出溢出”。 对散列文件主要采用链地址法处理溢出。对散列文件主要采用链地址法处理溢出。 当发生当发生“溢出溢出”时，需要将第时，需要将第m1个同义词存放到另一个桶中，个同义词存放到另一个桶中， 通常称此桶为通常称此桶为“溢出桶溢出桶”；相对地，称前；相对

48、地，称前m个同义词存放的桶为个同义词存放的桶为“基桶基桶”。 溢出桶和基桶大小相同，相互之间用指针相链接。当在基桶中没有待溢出桶和基桶大小相同，相互之间用指针相链接。当在基桶中没有待 查记录时，就顺指针所指到溢出桶中进行查找。因此，希望同一散列查记录时，就顺指针所指到溢出桶中进行查找。因此，希望同一散列 地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一 柱面上。柱面上。 （3）图形表示）图形表示 例如，某一文件有例如，某一文件有18个记录，其关键字分别为个记录，其关键字分别为278，109，063， 930，589，184

49、，505，269，008，083，164，215，330，810，620， 110，384，355。桶的容量为。桶的容量为m3，桶数，桶数b7。用除留余数法作哈。用除留余数法作哈 希函数希函数h(key)key mod 7。由此得到的直接存取文件如图。由此得到的直接存取文件如图12.10所所 示。示。 桶编号桶编号 基桶基桶 溢出桶溢出桶 0 063 184 1 589 505 008 330 2 3 269 164 4 109 620 5 278 215 810 110 355 6 930 083 384 图图12.10 直接存取文件示例直接存取文件示例 （4）查找操作）查找操作 其中：其中

50、：a为存取桶数的期望值（相当于哈希表中的平均查找长度），对链地址为存取桶数的期望值（相当于哈希表中的平均查找长度），对链地址 处理溢出来说，处理溢出来说，a = 1 + /2；te为存取一个桶所需的时间；为存取一个桶所需的时间；ti为在内存中顺序为在内存中顺序 查找一个记录所需的时间。查找一个记录所需的时间。 查找过程：首先根据给定值求得哈希地址（即基桶号），将查找过程：首先根据给定值求得哈希地址（即基桶号），将 基桶的记录读入内存进行顺序查找，若找到关键字等于给定值的基桶的记录读入内存进行顺序查找，若找到关键字等于给定值的 记录，则检索成功；否则，若基桶内没有填满记录或其指针域为记录，则检索

51、成功；否则，若基桶内没有填满记录或其指针域为 空，则文件内不含有待查记录；否则根据指针域的值的指示将溢空，则文件内不含有待查记录；否则根据指针域的值的指示将溢 出桶的记录读入内存继续进行顺序查找，直至检索成功或不成功。出桶的记录读入内存继续进行顺序查找，直至检索成功或不成功。 因此，总的查找时间为：因此，总的查找时间为： t = a (te + ti) 为装载因子，在散列文件中：为装载因子，在散列文件中： bm n 其中：其中：n为文件的记录数，为文件的记录数，b为桶数，为桶数，m为桶的容量。为桶的容量。 在直接存取文件中删除记录时，仅需对被删记录作一标记即可。在直接存取文件中删除记录时，仅需

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

53、而基桶内多数为被删除的记录。 此时亦需重组文件。此时亦需重组文件。 12.6 多关键字文件多关键字文件 12.6.1 多重表文件多重表文件 特点：在对文件进行检索操作是，不仅对主关键字进行简特点：在对文件进行检索操作是，不仅对主关键字进行简 单询问，还经常需要对关键字进行其他类型的询问检索。单询问，还经常需要对关键字进行其他类型的询问检索。 （1）特点）特点 多重表文件（多重表文件（multilist file）的特点是：）的特点是： 记录按主关键字的顺序构成一个串联文件，并建立主关键字的索引记录按主关键字的顺序构成一个串联文件，并建立主关键字的索引 （称为主索引）；（称为主索引）； 对每一个

54、次关键字项建立次关键字索引（称为次索引），所有具有对每一个次关键字项建立次关键字索引（称为次索引），所有具有 同一次关键字的记同一次关键字的记 录构成一个链表。录构成一个链表。 主索引为非稠密索引，次索引为稠密索引。每个索引项包括次关键字、头主索引为非稠密索引，次索引为稠密索引。每个索引项包括次关键字、头 指针和链表长度。指针和链表长度。 （2）例子）例子 例如，例如，图图12.10所示为一个多重表文件。其中，学号为主关键所示为一个多重表文件。其中，学号为主关键 字，记录按学号顺序链接，为了查找方便，分成字，记录按学号顺序链接，为了查找方便，分成3个子链表，其索个子链表，其索 引如引如图图12.10(b)所示，索引项中的主关键字为各子表中的最大值。所示，索引项中的主关键字为各子表中的最大值。 专业、已修学分和选修课目为专业、已修学分和选修课目为3个次关键字项，它们的索引如图个次关键字项，它们的索引如图 12.10(c)(e)所示，具有相同次关键字的记录链接在同一链表