【经管类】第十二章文件.ppt

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

按记录含有信息的长度不同可分成：①定长记录文件：文件中每个记录含有的信息长度相同 ②不定长记录文件：文件中每个记录含有的信息长度不等 （2）记录的逻辑结构和物理结构记录的逻辑结构：是指记录在用户或应用程序员面前呈现的方式，是用 户对数据的表示和存取方式着眼于用户使用方便记录的物理结构：是数据在物理存储器上存储的方式，是数据的物理表 示和组织着眼于提高存储空间的利用率和减少存取记录的时间 物理记录和逻辑记录之间可能存在下列3种关系： ①一个物理记录存放一个逻辑记录； ②一个物理记录包含多个逻辑记录； ③多个物理记录表示一个逻辑记录3）文件的操作（运算） 文件的检索：①顺序存取：存取下一个逻辑记录②直接存取：存取第i个逻辑记录① ②两种存取方式都是根 据记录序号(即记录存入文 件时的顺序编号)或记录的 相对位置进行存取的③按关键字存取：给定一个值，查询一个或一批关键字与给定值 相关的记录对数据库文件可以有如下4种查询方式：1.简单询问：查询关键字等于给定值的记录2.区域询问：查询关键字属某个区域内的记录3.函数询问：给定关键字的某个函数4.布尔询问：以上3种询问用布尔运算组合起来的询问 文件的修改：文件的修改包括插入一个记录、删除一个记录和更新一个记录3种操作。

文件的操作可以有实时和批量两种不同方式通常实时处理对应答时间要求 严格，应在接受询问之后几秒钟内完成检索和修改，而批量的处理则不然例如，银行的帐户系统需实时检索，但可进行批量修改，即可以 将一天的存款和提款记录在一个事务文件上，在一天的营业之后再进 行批量处理4）文件的物理结构文件的物理结构：文件在存储介质（磁盘或磁带）上的组织方式 文件的基本组织方式：①顺序组织；②随机组织；③链组织￡12.2 顺序文件串联文件：物理记录之间的次序由指针相链表示的顺序文件1）定义顺序文件（Sequential File）：是记录按其在文件中的逻辑 顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序 和逻辑记录的顺序是一致的连续文件：次序相继的两个物理记录在存储介质上的存储位 置是相邻的顺序文件2）特点顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式它的特点是： ①存取第i个记录，必须先搜索在它之前的i－1个记录 ②插入新的记录时只能加在文件的末尾 ③若要更新文件中的某个记录，则必须将整个文件进行复制3）磁带上顺序文件的批处理主文件：待修改的原始文件 事务文件：所有的修改请求集中构成的一个文件。

磁带文件的批处理过程：首先对事务文件进行排序，然后将主文件和事务文件归并成 一个新的主文件图12.1为这个过程的示意图终端事务 文件排序有序的事务文件主文件新主文件图12.1磁带文件批处理示意图 其中，主文件、事务文件和新的主文 件分别存放中一台磁带上主文件按关键 字自小至大（或自大至小）顺序有序，事 务文件必须和主文件有相同的有序关系在归并的过程中，顺序读出主文件与事务文件中的记录，比 较它们的关键字并分别进行处理对于关键字不匹配的主文件中 的记录，则直接将其写入新主文件中更改”和“删除”记录时， 要求其关键字相匹配删去”不用写入，而“更改”则要将更改后 的新记录写入新主文件插入”时不要求关键字相匹配，可直接 将事务文件上要插入的记录写到新主文件的适当位置 算法实现：批处理的示意算法如算法12.1所示算法中用到的各符号的含义说明如下：f——主文件；g——事务文件；h——新主文件它们都按关键字递增排序事务文件的每个记录中，增设一个代码以示修改要求，其中：“I”表示插入；“D”表示删去；“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(RcdType), 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(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) 磁盘上顺序文件的批处理和磁带文件类似，只是当修改项中没 有插入，且更新时不增加记录的长度时，可以不建立新的主文件， 而直接修改原来的主文件即可显然，磁盘文件的批处理可以在一 台磁盘组上进行4)磁盘上顺序文件的批处理假设所有的输入/输出都是通过缓冲区进行的，并假设缓冲区 大小为s（个记录），则整个批处理过程中读/写外存的次数为 ：￡12.3 索引文件非稠密索引：数据文件中的记录按关键字顺序有序，则可对一 组记录建立一个索引项，这种索引表称为非稠密索引1）基本术语索引表：除了文件本身（称做数据区）之外，另建立的一 张指示逻辑记录和物理记录之间一一对应关系的表索引项：索引表中的每一项总是按关键字（或逻辑记录 号）顺序排列 索引文件：包括文件数据区和索引表两大部分的文件索引顺序文件：数据区中的记录也按关键字顺序排列的文件索引非顺序文件：数据区中的记录不按关键字顺序排列的文件稠密索引：由于数据文件中记录不按关键字顺序排列，则必须 对每个记录都建立一个索引项，如此建立的索引表称为稠密索引。

例如，图12.2为两个索引表的例子0 1 4 101 15 1 1 7 119 04 2 0(不存在) 123 31 3 1 10 125 11关键字ki 物理记录号逻辑记录号 标识 物理记录号图12.2 索引表示例在记录输入建立数据区的同时建立一个索引表，表中的索引 项按记录输入的先后次序排列，待全部记录输入完毕后再对索引 表进行排序2）索引表的生成索引表是由系统程序自动生成的例如，对应于图12.3(a)的时间文件，其索引表如图12.3(b)， 而图12.3(c)为文件建立输入过程中建立的索引表10129 张珊 程序员 .10305 李四 维修员 .10402 王红 程序员 .10538 刘琪 穿孔员 .10831 . .10943 . .11017 . .11248 . . 物理记录号 职工号 姓名 职 务 其他(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 关键字 物理记录号关键字物理记录号 123（3）索引文件的检索检索方式：直接存取或按关键字（进行简单询问）存取。

检索过程：首先，查找索引表，若索引表上存在该记录，则根 据索引项的指示读取外存上该记录;否则说明外存上不存在该记录， 也就不需要访问外存 由于索引项的长度比记录小得多，则通常可将索引表一次读 入内存，由此再索引文件中进行检索只访问外存两次，即一次读 索引，一次读记录并且由于索引表是有序的，则查找索引表时 可用折半查找法4）索引文件的修改 ①删除操作：删除一个记录时，仅需删去相应的索引项； ②插入操作：插入一个记录时，应将记录置于数据区的末尾，同时再索引表中插入索引项； ③更新操作：更新记录时，应将更新后的记录置于数据区末尾，同时修改索引表中相应的索引项 （5）多级索引查找表：对索引表建立的索引例如，假设图12.3(b)的索引表需占3个物理块的外存，每一 个物理块容纳3个索引，则建立的查找表如图12.4所示检索记 录时，先查找查找表，再查索引表，然后读取记录图12.4 图12.3(b)中索引表的索引 最大关键字 物理块号 17 1 38 2 46 3通常最高可有四级索引： 上述的多级索引是一种静态索引，各级索引均为顺序表结构。

其结构简 单，但修改很不方便，每次修改都要重组索引因此，当数据文件在使用过 程中记录变动较多时，应采用动态索引如,二叉排序树（或二叉平衡树）、 B-树以及键树￡12.4 ISAM和VSAM文件 ￡12.4.1 ISAM文件（1）定义索引顺序存取方法ISAM(Indexed Sequential Access Method)： 是一种专为磁盘存取设计的文件组织方式由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可 对磁盘上的数据文件建立盘组、柱面和磁道三级索引例如，图12.5为存放一个磁盘组上的ISAM文件每个柱面建立 一个磁道索引，每个磁道索引项由：基本索引项和溢出索引项两部 分组成，如图12.6所示 ①磁道索引项：基本索引项： 关键字：表示该磁道中最末一个记录的关键字（在此为最大关键字） 指针：指示该磁道中第一个记录的位置溢出索引项： 关键字：表示该磁道溢出的记录的最大关键字 指针：指示在溢出区中的第一个记录。