数据结构第十二章文件.ppt

数据结构第十二章文件,本章内容12.1 有关文件的基本概念12.2 顺序文件12.3 索引文件12.4 ISAM和VSAM文件12.5 直接存取文件12.6 多关键字文件,12-3,12.1 有关文件的基本概念,文件：是大量记录的集合。习惯上称存储在主存储器（内存储器）中的记录集合为表，称存储在二级存储器（外存储器）中的记录集合为文件。数据项：是文件中可使用的、不可分的的最小数据单位。属性：记录中所有非关键字的数据项，称为记录的属性。文件类别按记录的类型不同可分成：操作系统的文件：操作系统中的文件仅是一维的连续的字符序列，无结构、无解释。数据库文件：数据库中的文件是带有结构的记录的集合。这类记录是由一个或多个数据项组成的集合，它也是文件中可存取的数据的基本单位。按记录中关键字的多少数据库文件可分成：单关键字文件：文件中记录只有一个唯一标识记录的主关键字。多关键字文件：文件中记录除了含有一个主关键字外，还含有若干个次关键字。,12-4,12.1 有关文件的基本概念,按记录含有信息的长度不同可分成：定长记录文件：文件中每个记录含有的信息长度相同。不定长记录文件：文件中每个记录含有的信息长度不等。记录的逻辑结构和物理结构记录的逻辑结构：是指记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方式。着眼于用户使用方便。记录的物理结构：是数据在物理存储器上存储的方式，是数据的物理表示和组织。着眼于提高存储空间的利用率和减少存取记录的时间。物理记录和逻辑记录之间可能存在下列三种关系：一个物理记录存放一个逻辑记录；一个物理记录包含多个逻辑记录；多个物理记录表示一个逻辑记录。,12-5,12.1 有关文件的基本概念,记录的逻辑结构与物理结构的差别示例,12-6,12.1 有关文件的基本概念,文件的操作：主要有两类，即检索与修改文件的检索：主要有三种方式：顺序存取：存取下一个逻辑记录。直接存取：存取第i个逻辑记录。按关键字存取：给定一个值，查询一个或一批关键字与给定值相关的记录。对数据库文件可以有如下4种查询方式：简单询问：查询关键字等于给定值的记录。区域询问：查询关键字属某个区域内的记录。函数询问：给定关键字的某个函数。布尔询问：以上3种询问用布尔运算组合起来的询问。文件的修改：文件的修改包括：插入一条记录；删除一条记录更新一条记录。,12-7,12.1 有关文件的基本概念,文件的操作有实时和批量两种处理方式实时操作要求有较短的应答响应时间，在接受指令后尽可能快地完成检索或修改任务。批量的文件处理则允许较长反馈时间。用户可以根据需求选择不同的文件处理方式。批量处理方式可减少更新操作的代价例如，银行的帐户系统需实时检索，但可进行批量修改，即可以将一天的存款和提款记录在一个事务文件上，在一天的营业之后再进行批量处理。,12-8,12.1 有关文件的基本概念,文件的物理结构文件在存储介质（磁盘或磁带）上的组织方式。文件逻辑组织形式：顺序结构的定长记录；顺序结构的变长记录；按关键码存取的记录。文件物理组织方形式：顺序文件散列文件索引文件倒排文件,12-9,12.2 顺序文件,定义：顺序文件（Sequential File）：是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。连续文件：次序相继的两个物理记录在存储介质上的存储位置是相邻的顺序文件。串联文件：物理记录之间的次序由指针相链表示的顺序文件。特点：顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式。它的特点是：存取第i个记录，必须先搜索在它之前的i1个记录。插入新的记录时只能加在文件的末尾。若要更新文件中的某个记录，则必须将整个文件进行复制。,12-10,12.2 顺序文件,顺序文件的操作：一般由三种不同的方法：顺序存取是从文件的第一个记录开始依次顺序进行存取。这种方法存取效率很高。随机存取是希望对指定的记录直接进行存取。但是这种要求对于顺序文件来说，是极不方便的，存取效率很低。按关键字存取是按记录的关键字值进行存取。这种方法对于顺序文件来讲，也需要从文件的第一个记录开始进行查找，因此，在一般情况下，存取效率不高。,12-11,12.2 顺序文件,批处理算法实现批处理的示意算法如教材p310的算法12.1所示。算法中用到的各符号的含义说明如下：F：主文件；G：事务文件；H：新主文件。它们都按关键字递增排序。事务文件的每个记录中，增设一个代码以示修改要求，其中：I：表示插入；D：表示删除；U：表示更改。,12-12,12.2 顺序文件,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);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/其他均为出错情况/switch/while/MergeFile,12-13,12.2 顺序文件,分析批处理算法的时间假设主文件包含n个记录，事务文件包含m个记录。一般情况下，事务文件较小，可以进行内部排序，则时间复杂度为O(m*logm)。内部归并的时间复杂度为O(nm)，则总的内部处理时间为O(m*logmn)。假设所有的输入/输出都是通过缓冲区进行的，并假设缓冲区大小为s（个记录），则整个批处理过程中读/写外存的次数为：2m/s+(m+n)/s）,12-14,12.3 索引文件,基本术语索引表：除了文件本身（称做数据区）之外，另建立的一张指示逻辑记录和物理记录之间一一对应关系的表。索引项：索引表中的每一项。总是按关键字（或逻辑记录号）顺序排列。索引文件：包括文件数据区和索引表两大部分的文件。索引顺序文件：数据区中的记录也按关键字顺序排列的文件。索引非顺序文件：数据区中的记录不按关键字顺序排列的文件。稠密索引：由于数据文件中记录不按关键字顺序排列，则必须对每个记录都建立一个索引项，如此建立的索引表称为稠密索引。非稠密索引：数据文件中的记录按关键字顺序有序，则可对一组记录建立一个索引项，这种索引表称为非稠密索引。,12-15,12.3 索引文件,例如，下图为两个索引表的例子。,12-16,12.3 索引文件,索引文件的存储 索引文件在存储器上分为两个区：索引区和数据区。索引区存放索引表，数据区存放主文件。索引文件的建立建立索引文件的过程：按输入记录的先后次序建立数据区和索引表。其中索引表中关键字是无序的待全部记录输入完毕后对索引表进行排序，排序后的索引表和主文件一起就形成了索引文件。,12-17,12.3 索引文件,检索操作检索分两步进行：将外存上含有索引区的页块送人内存，查找所需记录的物理地址将含有该记录的页块送人内存注意：索引表不大时，索引表可一次读入内存，在索引文件中检索只需两次访问外存：一次读索引，一次读记录。由于索引表有序，对索引表的查找可用顺序查找或二分查找,12-18,12.3 索引文件,索引文件的修改删除操作：删除一个记录时，仅需删去相应的索引项；插入操作：插入一个记录时，应将记录置于数据区的末尾，同时再索引表中插入索引项；更新操作：更新记录时，应将更新后的记录置于数据区末尾，同时修改索引表中相应的索引项。多级索引：查找表：对索引表建立的索引。通常最高可有四级索引：,数据文件,多级索引是静态索引，各级索引均为顺序表结构。其结构简单，但修改很不方便，每次修改都要重组索引。因此，当数据文件在使用过程中记录变动较多时，应采用动态索引。如二叉排序树（或二叉平衡树）、B-树以及键树。,12-19,12.4 ISAM和VSAM文件,12.4.1 ISAM文件ISAM文件定义：索引顺序存取方法ISAM(Indexed Sequential Access Method)是一种专为磁盘存取设计的文件组织方式。磁盘是以盘组、柱面和磁道三级地址存取的设备，可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。磁道索引项：基本索引项：关键字：表示该磁道中最末一个记录的关键字（在此为最大关键字）。指针：指示该磁道中第一个记录的位置。溢出索引项：关键字：表示该磁道溢出的记录的最大关键字。指针：指示在溢出区中的第一个记录。,12-20,12.4 ISAM和VSAM文件,柱面索引项：关键字：表示该柱面中最末一个记录的关键字（最大关键字）。指针：指示该柱面上的磁道索引位置。ISAM文件的组成ISAM文件由多级主索引、柱面索引、磁道索引和主文件组成。文件的记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上。对同一柱面，则应按盘面的次序顺序存放。,12-22,12.4 ISAM和VSAM文件,在ISAM文件上检索记录时，先从主索引出发检索到相应的柱面索引，然后从柱面索引检索到记录所在柱面的磁道索引，最后从磁道索引检索到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至检索到为止；反之，若检索遍磁道而不存在此记录，则表明文件中无此记录。ISAM文件中删除记录比较简单，只需作删除标记而不用移动记录或改变指针。当然应该周期性地把记录读入内存重排整理ISAM文件，以尽量填满基本区而空出溢出区。,12-23,12.4 ISAM和VSAM文件,12.4.2 VSAM文件VSAM（Virtual Storage Access Method）即虚拟存储存取方法。它使用户只需考虑控制区间等逻辑存储单位，而无需考虑其物理位置以及何时对外存储器进行读写操作，给用户使用文件提供了方便。VSAM文件的结构由索引集、顺序集和数据集三部分组成。数据集存放文件的所有记录，顺序集和索引集构成一棵B+树是文件的索引部分。数据集中的一个结点称为控制区间（Control Interval）。,12-24,12.4 ISAM和VSAM文件,顺序集中的一个结点，存放着若干相邻控制区间的索引项，每个索引项由控制区间中的最大关键字和指向该控制区间的指针组成。顺序集中的一个结点连同其下层所有控制区间形成的整体称作控制区域（Control Range）。顺序集中的结点之间用指针相链接，在它们上层的结点又以它们为基础形成索引，并逐级向上建立索引，形成B+树的非终端结点。,12-25,12.4 ISAM和VSAM文件,VSAM文件的结构示意图,12-26,12.4 ISAM和VSAM文件,对VSAM文件中记录的检索，既可从最高层的索引逐层往下按关键字进行检索，又可在顺序集中沿着指针链顺序检索。VSAM文件没有专门的溢出区，但可以利用控制区间中的空隙或控制区域中的空控制区间来插入记录（即在B+树上插入记录）。而在VSAM文件中删除记录时，也需移动记录。VSAM文件占有较多的存储空间，然而它具有许多优点，如动态地分配和释放存储空间，无需像ISAM文件那样定期重排文件，并能较快地执行插入操作和保持较高的检索效率。VSAM文件通常作为组织大型索引顺序文件的标准形式。,12-27,12.4 ISAM和VSAM文件,VASM文件的特点优点：动态地分配和释放存储空间，不需要对文件进行重组，并能较快地对插入的记录进行查找，查找一个后插入记录的时间与查找一个原有记录的时间是相同的。缺点：占有较多的存储空间，一般只能保持约75的存储空间利用率。,12-28,12.5 直接存取文件(散列文件),定义：直接存取文件指的是利用杂凑（Hash）法进行组织的文件。它类似于哈希表，既根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上，故又称散列文件。与哈希表不同的是，对于文件来说，磁盘上的文件记录通常是成组存放的。溢出处理：若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶（Bucket）。假若一个桶能存放m个记录，这就是说，m个同义词的记录可以存放在同一地址的桶中，而当第m1个同义词出现时才发生“溢出”。对散列文件主要采用链地址法处理溢出。发生“溢出”时，需要将第m1个同义词存放到另一个桶中，称此桶为“溢出桶”；相对地，称前m个同义词存放的桶为“基桶”。溢出桶和基桶大小相同，相互之间用指针相链接。当在基桶中没有待查记录时，就顺指针所指到溢出桶中进行查找。因此，希望同一散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一柱面上。,12-29,12.5 直接存取文件(散列文件),例如，某一文件有18个记录，其关键字分别为278，109，063，930，589，184，505，269，008，083，164，215，330，810，620，110，384，355。桶的容量为m3，桶数b7。用除留余数法作哈希函数H(key)key MOD 7。由此得到的直接存取文件如下图所示。,直接存取文件示例,12-30,12.5 直接存取文件(散列文件),查找操作查找过程：首先根据给定值求得哈希地址（即基桶号），将基桶的记录读入内存进行顺序查找，若找到关键字等于给定值的记录，则检索成功；否则，若基桶内没有填满记录或其指针域为空，则文件内不含有待查记录；否则根据指针域的值的指示将溢出桶的记录读入内存继续进行顺序查找，直至检索成功或不成功。因此，总的查找时间为：T=a(te+ti)其中：a为存取桶数的期望值（相当于哈希表中的平均查找长度），对链地址处理溢出来说，a=1+/2；te为存取一个桶所需的时间；ti为在内存中顺序查找一个记录所需的时间。为装载因子，在散列文件中：=n/(bm)n为文件的记录数，b为桶数，m为桶的容量。,12-31,12.5 直接存取文件(散列文件),删除操作在直接存取文件中删除记录时，仅需对被删记录作一标记即可。直接存取文件的特点优点：文件随机存放，记录不需进行排序；插入、删除方便，存取速度快，不需要索引区，节省存储空间。缺点：不能进行顺序存取，只能按关键字随机存取，且询问方式限于简单询问，并且在经过多次的 插入、删除之后，也可能造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记录。此时亦需重组文件。,12-32,12.6 多关键字文件,在对文件进行检索操作是，不仅对主关键字进行简单询问，还经常需要对关键字进行其他类型的询问检索。12.6.1 多重表文件特点：多重表文件（Multilist File）的特点是：记录按主关键字的顺序构成一个串联文件，并建立主关键字的索引（称为主索引）；对每一个次关键字项建立次关键字索引（称为次索引），所有具有同一次关键字的记 录构成一个链表。主索引为非稠密索引，次索引为稠密索引。每个索引项包括次关键字、头指针和链表长度。,12-33,12.6 多关键字文件,例子：例如，下图a所示为一个多重表文件。对工号非稠密索引分成三个子链表，其索引如图b所示，索引项中的主关键字为各组中关键字的最大值。职称和专业是两个次关键字项，其索引分别如图c和d所示，具有相同次关键字值的记录链接在同一链表中。有了这些次关键字索引，根据关键字值找到链表头指针，然后从头指针出发可列出链表中所有记录。,12-34,12.6 多关键字文件,12.6.2 倒排文件倒排文件和多重表文件的区别在于次关键字索引的结构不同。通常称倒排文件中的次关键字索引为倒排表，具有相同次关键字的记录之间不设指针相链，而在倒排表中该次关键字的一项中存放这些记录的物理记录号。如图所示为上例中的倒排表。,12-35,12.6 多关键字文件,在倒排文件中可以较快地检索记录，特别是在检索多个次关键字的情况时。在处理各种次关键字的查询时，只要在次关键字索引中检索出有关的指针集合，再对这些指针集合进行交、并、差等逻辑运算，就可求出符合查询条件的记录指针，然后按指针到外存去存取记录。在插入和删除记录时，倒排表也要进行相应修改；需要移动索引项中记录号以保持其有序排列。若数据文件是索引顺序文件（如ISAM文件），倒排表中应存放记录的主关键字而不是物理记录号。倒排文件的缺点是维护困难。同一倒排表中各项长度不同，不同倒排表的长度也不同，这些都给倒排文件的维护带来一定的困难，而且倒排表需要额外存储空间。,12-36,习题,本章习题参见教师网页：http:/,