最新【考研计算机专业课】武汉大学数据结构PPT课件 第12章文件(共40张PPT课件).pptx

《最新【考研计算机专业课】武汉大学数据结构PPT课件 第12章文件(共40张PPT课件).pptx》由会员分享，可在线阅读，更多相关《最新【考研计算机专业课】武汉大学数据结构PPT课件 第12章文件(共40张PPT课件).pptx（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第12章章 文文 件件 本章本章(bn zhn)小结小结12.1 文件文件(wnjin)的基本概念的基本概念12.2 顺序顺序(shnx)文件文件12.4 哈希文件哈希文件12.3 索引文件索引文件12.5 多关键字文件多关键字文件第一页，共四十页。12.1 文件的基本概念文件的基本概念12.1.1 什么是文件什么是文件 文件文件是性质相同的记录的集合。文件的数据量通常很大是性质相同的记录的集合。文件的数据量通常很大,它被它被放置在外存上。放置在外存上。 数据结构中所讨论的文件主要是数据库意义数据结构中所讨论的文件主要是数据库意义(yy)上的文件上的文件,而不而不是操作系统意义是操作系统意义

2、(yy)上的文件。操作系统中研究的文件是一维的无上的文件。操作系统中研究的文件是一维的无结构连续字符序列结构连续字符序列,数据库中所研究的文件是带有结构的记录集合数据库中所研究的文件是带有结构的记录集合,每个记录可由若干个数据项构成。每个记录可由若干个数据项构成。 第二页，共四十页。 记录记录是文件中存取的基本单位是文件中存取的基本单位,数据项数据项是文件可使用的最小单位。是文件可使用的最小单位。数据项有时数据项有时(yush)也称为也称为字段字段。其值能惟一标识一个记录的数据项或数。其值能惟一标识一个记录的数据项或数据项的组合称为据项的组合称为主关键字项主关键字项,其他不能惟一标识一个记录的

3、数据项则其他不能惟一标识一个记录的数据项则称为称为次关键字项次关键字项,主关键字项主关键字项(或次关键字项或次关键字项)的值称为的值称为主关键字主关键字(或或次关次关键字键字)。 为讨论方便起见为讨论方便起见,我们仍不严格区分关键字项和关键字我们仍不严格区分关键字项和关键字,即在不易混即在不易混淆时淆时,将主将主(或次或次)关键字项简称为主关键字项简称为主(或次或次)关键字关键字,并且假定主关键字项只并且假定主关键字项只含一个数据项含一个数据项。 第三页，共四十页。 文件可以文件可以(ky)按照记录中关键字的多少按照记录中关键字的多少,分成分成单关键字文件单关键字文件和和多多关键字文件关键字文

4、件。若文件中的记录只有一个惟一标识记录的主关键字。若文件中的记录只有一个惟一标识记录的主关键字,则称其则称其为为单关键字文件单关键字文件；若文件中的记录除了含有一个主关键字外；若文件中的记录除了含有一个主关键字外,还含有还含有若干个次关键字若干个次关键字,则称为则称为多关键字文件多关键字文件。 文件又可分成定长文件和不定长文件。若文件中记录含有的信息文件又可分成定长文件和不定长文件。若文件中记录含有的信息长度相同长度相同,则称这类记录为定长记录则称这类记录为定长记录,由这种定长记录组成的文件称做由这种定长记录组成的文件称做定长文件定长文件；若文件中记录含有的信息长度不等；若文件中记录含有的信息

5、长度不等,则称做则称做不定长文件不定长文件。 第四页，共四十页。12.1.2 文件的逻辑结构及操作文件的逻辑结构及操作 文件中各记录之间存在着逻辑关系文件中各记录之间存在着逻辑关系,当一个文件的各个记录当一个文件的各个记录按照某种次序排列起来时按照某种次序排列起来时(这种排列的次序可以是记录中关键字这种排列的次序可以是记录中关键字的大小的大小,也可以是各个记录存入该文件的时间先后等等也可以是各个记录存入该文件的时间先后等等),各记录之各记录之间就自然地形成了一种线性关系。在这种次序下间就自然地形成了一种线性关系。在这种次序下,文件中每个记文件中每个记录最多只有录最多只有(zhyu)一个后继记录

6、和一个前驱记录一个后继记录和一个前驱记录,而文件的第一个而文件的第一个记录只有记录只有(zhyu)后继没有前驱后继没有前驱,文件的最后一个记录只有文件的最后一个记录只有(zhyu)前驱前驱而没有后继。因此而没有后继。因此,文件可看成是一种线性结构文件可看成是一种线性结构。 文件上的操作主要有两类：检索和维护。文件上的操作主要有两类：检索和维护。第五页，共四十页。12.1.3 文件的存储结构文件的存储结构 文件的存储结构是指文件在外存上的组织方式。采用不同的文件的存储结构是指文件在外存上的组织方式。采用不同的组织方式就得到不同的存储结构。基本的组织方式有四种：顺序组织方式就得到不同的存储结构。基

7、本的组织方式有四种：顺序组织、索引组织、哈希组织和链组织。文件组织的各种方式往往组织、索引组织、哈希组织和链组织。文件组织的各种方式往往是这四种基本方式的结合。是这四种基本方式的结合。 几种常用的文件组织方式：顺序文件、索引文件、哈希文件和多几种常用的文件组织方式：顺序文件、索引文件、哈希文件和多关键字文件。选择关键字文件。选择(xunz)哪一种文件组织方式哪一种文件组织方式,取决于对文件中记录的取决于对文件中记录的使用方式和频繁程度、存取要求、外存的性质和容量。使用方式和频繁程度、存取要求、外存的性质和容量。 第六页，共四十页。12.2 顺序文件顺序文件 顺序文件顺序文件是指按记录进入文件的

8、先后顺序存放、其逻辑顺序跟是指按记录进入文件的先后顺序存放、其逻辑顺序跟物理顺序一致的文件。若顺序文件中的记录按其主关键字有序物理顺序一致的文件。若顺序文件中的记录按其主关键字有序,则则称此顺序文件为称此顺序文件为顺序有序文件顺序有序文件；否则称为；否则称为顺序无序文件顺序无序文件。为了提高检。为了提高检索效率索效率,常常将顺序文件组织成有序文件。常常将顺序文件组织成有序文件。 顺序文件的结构特点：顺序文件的结构特点： 记录在文件中的排列顺序是由记录进入存储介质的次序记录在文件中的排列顺序是由记录进入存储介质的次序(cx)决定的决定的, 即文即文件物理结构中记录的排列顺序和文件的逻辑结构中记录

9、的排列顺序一致。件物理结构中记录的排列顺序和文件的逻辑结构中记录的排列顺序一致。第七页，共四十页。 顺序文件的操作特点：顺序文件的操作特点： (1)便于进行顺序存取；便于进行顺序存取； (2)不便于进行直接存取不便于进行直接存取,为取第为取第i个记录个记录,必须先读出前必须先读出前i-1个记个记录录,对于磁盘上的等长记录的连续文件可以进行折半查找；对于磁盘上的等长记录的连续文件可以进行折半查找； (3)插入插入(ch r)新的记录只能加在文件的末尾；新的记录只能加在文件的末尾； (4)删除记录时删除记录时,只作标记；只作标记； (5)更新记录必须生成新的文件。更新记录必须生成新的文件。第八页，

10、共四十页。12.3 索引文件索引文件 用索引的方法组织文件时用索引的方法组织文件时,通常是在文件本身通常是在文件本身(称为主文件称为主文件)之之外外,另外建立一张表另外建立一张表,它指明逻辑记录和物理记录之间的一一对应关它指明逻辑记录和物理记录之间的一一对应关系系,这张表就叫做索引表这张表就叫做索引表,它和主文件一起构成它和主文件一起构成(guchng)的文件称作索的文件称作索引文件。引文件。 索引表中的每一项称作索引表中的每一项称作索引项索引项,一般索引项都是由一般索引项都是由主关键字和该主关键字和该关键字所在记录的物理地址组成关键字所在记录的物理地址组成的。显然的。显然,索引表必须按主关键

11、字有索引表必须按主关键字有序序,而主文件本身则可以按主关键字有序或无序而主文件本身则可以按主关键字有序或无序,前者称为前者称为索引顺序文索引顺序文件件,后者称为后者称为索引非顺序文件索引非顺序文件。 第九页，共四十页。 对于索引非顺序文件对于索引非顺序文件,由于由于(yuy)主文件中记录是无序的主文件中记录是无序的,则必则必须为每个记录建立一个索引项须为每个记录建立一个索引项,这样建立的索引表称为这样建立的索引表称为稠密索引稠密索引。 对于索引顺序文件对于索引顺序文件,由于主文件中记录按关键字有序由于主文件中记录按关键字有序,则可对则可对一组记录建立一个索引项一组记录建立一个索引项,例如例如,

12、让文件中每个页块对应一个索引让文件中每个页块对应一个索引项项,这种索引表称之为这种索引表称之为稀疏索引稀疏索引。 通常可将索引非顺序文件简称为索引文件通常可将索引非顺序文件简称为索引文件,本节只讨论这种本节只讨论这种文件。文件。 第十页，共四十页。 索引文件在存储器上分为两个索引文件在存储器上分为两个(lin )区：索引区和数据区区：索引区和数据区,前者前者存放索引表存放索引表,后者存放主文件。在建立文件过程中后者存放主文件。在建立文件过程中,按输入记录的先按输入记录的先后次序建立数据区和索引表后次序建立数据区和索引表,这样的索引表其关键字是无字的这样的索引表其关键字是无字的,待全待全部记录输

13、入完毕后再对索引表进行排序部记录输入完毕后再对索引表进行排序,排序后的索引表和主文件排序后的索引表和主文件一起就形成了索引文件。一起就形成了索引文件。 第十一页，共四十页。索引文件的结构特点：索引文件的结构特点： (1) 索引文件由索引文件由“主文件主文件”和多级和多级“索引索引”组成；组成； (2) 索引中的每个记录由索引中的每个记录由“关键字关键字”和和“指针指针”组成；组成； (3) 通常通常,索引文件中的主文件是无序文件索引文件中的主文件是无序文件,索引是索引是 (按关键字有序按关键字有序)的有的有序文件；序文件； (4) “索引索引”是在输入数据建立文件时自动生成是在输入数据建立文件

14、时自动生成(shn chn)。初建时的。初建时的“静态索引静态索引”为无序文件为无序文件,经过排序后成为有序文件。经过排序后成为有序文件。第十二页，共四十页。索引文件的操作特点：索引文件的操作特点： (1) 检索方式为：直接存取和按关键字存取。检索方式为：直接存取和按关键字存取。“按关键字检索按关键字检索”将分两步进行：先查索引将分两步进行：先查索引,然后然后(rnhu)根据索引中指针所指索取记录；根据索引中指针所指索取记录； (2) 插入记录时插入记录时,“记录记录”插入在主文件的末尾插入在主文件的末尾,而相应的而相应的“索引索引项项”必须插入在索引的合适位置上。因此必须插入在索引的合适位置

15、上。因此,最好在建索引表时留有最好在建索引表时留有一定一定“空位空位”； (3) 删除记录时删除记录时,仅需删除索引表中相应的索引项即可；仅需删除索引表中相应的索引项即可； (4) 更新记录时更新记录时,应将更新后的记录插入在主文件的末尾应将更新后的记录插入在主文件的末尾,同时修改相应同时修改相应的索引项。的索引项。第十三页，共四十页。有两种典型的索引顺序文件有两种典型的索引顺序文件(wnjin)。12.2.1 ISAM文件文件 ISAM(Index Sequential Access Method)(索引顺序存取方索引顺序存取方法法)是一种专为磁盘存取设计的文件组织方法。是一种专为磁盘存取设

16、计的文件组织方法。第十四页，共四十页。1. 文件的组织文件的组织(zzh)方式方式 主文件按柱面集中存放主文件按柱面集中存放,同时同时(tngsh)建立三级索引：建立三级索引： (1) 磁道索引磁道索引 (2) 柱面索引柱面索引 (3) 主索引主索引磁道索引磁道索引(suyn)结构如下：结构如下：基本索引项基本索引项溢出索引项溢出索引项关键字关键字 指针指针 关键字关键字 指针指针第十五页，共四十页。2101024主主索索引引 r(14) r(21) r(38) r(41) r(57) r(63) r(72) r(85) r(99) 溢溢 出出 区区 磁磁 道道 索索 引引 r(514) 溢溢

17、 出出 区区 磁道索引磁道索引(suyn) r(1024)一一 个个 柱柱 面面 .柱柱面面索索引引992101024T0T1T2T3T4T5第十六页，共四十页。2. 操作的特点操作的特点 (1) 检索检索 可有两种方式：可有两种方式： 顺序存取顺序存取 依关键字最小至大顺序存取。依关键字最小至大顺序存取。 按关键字存取按关键字存取 从主索引开始从主索引开始(kish),到到 柱面索引柱面索引,到磁道索到磁道索引引,最后取最后取 得记录得记录,先后访问四次外存。先后访问四次外存。 (2) 插入插入 将记录插入在某个磁道的合适位置上将记录插入在某个磁道的合适位置上;将该磁道上关键字最大的记录将该

18、磁道上关键字最大的记录移出到本柱面的溢出区中移出到本柱面的溢出区中;修改本磁道的索引项修改本磁道的索引项(包括基本索引项和溢出包括基本索引项和溢出索引项索引项)。 (3) 删除删除 在被删记录当前存储位置上在被删记录当前存储位置上 作作“删除标记删除标记”。第十七页，共四十页。3. 文件重组文件重组(zhn z) 在经过多次的插入和删除操作之后在经过多次的插入和删除操作之后,大量的记录进入文件的溢出区大量的记录进入文件的溢出区”,而而“基本存储区基本存储区”中出现很多已被删去的记录空间中出现很多已被删去的记录空间,此时的文件结构很不合理。此时的文件结构很不合理。因此因此,对对ISAM文件文件,

19、 需要周期地进行重整。需要周期地进行重整。第十八页，共四十页。12.3.2 VSAM文件文件 VSAM是虚拟存储存取方法是虚拟存储存取方法(Virtual Storage Access Method)的英文缩写。的英文缩写。VSAM文件是一种采用虚拟存储存取方法的文件。文件是一种采用虚拟存储存取方法的文件。 VSAM文件的存储单位是控制区间和控制区域文件的存储单位是控制区间和控制区域,这是一些逻辑这是一些逻辑存储单位存储单位,与柱面、磁道等实际存储单位并没有必然的联系。用与柱面、磁道等实际存储单位并没有必然的联系。用户在存取户在存取VSAM文件的记录时文件的记录时,不需要考虑该记录的当前位置是

20、在不需要考虑该记录的当前位置是在内存内存(ni cn)还是在外存还是在外存,也不需要考虎何时执行对外存进行读写也不需要考虎何时执行对外存进行读写的命令。可见的命令。可见,这种文件较这种文件较ISAM文件更方便用户使用。文件更方便用户使用。 第十九页，共四十页。1文件文件(wnjin)的结构的结构 . 索引索引(suyn)集集B+树树 顺序集顺序集控制(kngzh)区域控制区间数据集数据集第二十页，共四十页。2. 控制区间和控制区域控制区间和控制区域 控制区间：控制区间：是用户进行是用户进行(jnxng)一次存取的逻辑单位一次存取的逻辑单位,可看成是可看成是一个逻辑磁道。但它的实际大小和物理磁道

21、无关。一个逻辑磁道。但它的实际大小和物理磁道无关。 控制区域：控制区域：由若干控制区间和它们的索引项组成由若干控制区间和它们的索引项组成,可看成是一可看成是一个逻辑柱面。个逻辑柱面。 VSAM文件初建时文件初建时,每个控制区间内的记录数不足额定数每个控制区间内的记录数不足额定数,并且有的并且有的控制区间内的记录数为零。控制区间内的记录数为零。第二十一页，共四十页。3. 顺序集顺序集 本身是一个单链表本身是一个单链表,它包含文件的全部索引项它包含文件的全部索引项,同时同时,顺序集中的每顺序集中的每个结点即为个结点即为B+树的叶子结点树的叶子结点,索引集中的结点即为索引集中的结点即为B+树的非叶结

22、点。树的非叶结点。4. 文件的操作文件的操作 检索：检索：可进行顺序存取和按关键字存取；可进行顺序存取和按关键字存取； 插入：插入：按关键字大小插入在某个适当的控制区间中按关键字大小插入在某个适当的控制区间中,当控制区间中的当控制区间中的记录数超过文件规定的大小时记录数超过文件规定的大小时,要要“分裂分裂”控制区间控制区间,必要时必要时,还需要还需要“分裂分裂”控制区域；控制区域； 删除删除(shnch)：必须必须“真实地真实地”删除记录删除记录,因此要在控制区间内因此要在控制区间内“移动移动”记录。记录。第二十二页，共四十页。5. VSAM文件通常被作为文件通常被作为(zuwi)大型索引大型

23、索引 顺序文件的标准组织方式。顺序文件的标准组织方式。 优点优点：动态地分配和释放空间：动态地分配和释放空间, 不需要重组文件；能较快地实现对不需要重组文件；能较快地实现对“后插入后插入”的记录的检索；的记录的检索； 缺点缺点：占有较多的存储空间：占有较多的存储空间,一般只能保持约一般只能保持约75%的存储空间利的存储空间利用率。用率。(因此因此,一般情况下一般情况下,极少产生需要分裂控制区域的情况极少产生需要分裂控制区域的情况)第二十三页，共四十页。12.4 哈希文件哈希文件 哈希文件也称为哈希文件也称为(chn wi)散列文件散列文件,是利用哈希存储方式组织的文件是利用哈希存储方式组织的文

24、件,亦称亦称为为(chn wi)直接存取文件。它类似于哈希表直接存取文件。它类似于哈希表,即根据文件中关键字的特点即根据文件中关键字的特点,设计设计一个哈希函数和处理冲突的方法一个哈希函数和处理冲突的方法,将记录哈希到存储设备上。将记录哈希到存储设备上。 与哈希表不同的是与哈希表不同的是,对于文件来说对于文件来说,磁盘上的文件记录通常是成组存磁盘上的文件记录通常是成组存放的放的,若干个记录组成一个存储单位若干个记录组成一个存储单位,在哈希文件中在哈希文件中,这个存储单位叫做这个存储单位叫做桶。假如一个桶能存放桶。假如一个桶能存放m个记录个记录,则当桶中已有则当桶中已有m个同义词的记录时个同义词

25、的记录时,存存放第放第m+1个同义词会发生个同义词会发生“溢出溢出”。处理溢出虽可采用哈希表中处理。处理溢出虽可采用哈希表中处理冲突的各种方法冲突的各种方法,但对哈希文件而言但对哈希文件而言,主要采用链地址法。主要采用链地址法。第二十四页，共四十页。 当发生当发生“溢出溢出”时时,需要需要(xyo)将第将第m+1个同义词存放到另一个桶中个同义词存放到另一个桶中,通通常称此桶为常称此桶为“溢出桶溢出桶”。相对地。相对地,称前称前m个同义词存放的桶为个同义词存放的桶为“基桶基桶”。 溢出桶和基桶大小相同溢出桶和基桶大小相同,相互之间用指针链接。当在基桶中没相互之间用指针链接。当在基桶中没有找到待查

26、记录时有找到待查记录时,就沿着指针到所指溢出桶中进行查找就沿着指针到所指溢出桶中进行查找,因此因此,希希望同一哈希地址的溢出桶和基桶在磁盘上的物理位置不要相距望同一哈希地址的溢出桶和基桶在磁盘上的物理位置不要相距太远太远,最好在同一柱面上。最好在同一柱面上。 第二十五页，共四十页。 例如例如,某一文件有某一文件有20个记录个记录,其关键字集合其关键字集合(jh)为为 2,23,5,26,1,3,24,18,27,12,7,9,4,19,6,16,33,11,10,13。桶的容量桶的容量m=3,桶数桶数b=7。 用除留余数法作哈希函数用除留余数法作哈希函数H(key)=key%7。给出对应的哈希

27、文件。给出对应的哈希文件。 7 1 2 23 9 3 24 10 18 4 11 5 26 12 27 6 13 0 1 2 3 4 5 6 16 19 33 桶编号 基桶 溢出桶 第二十六页，共四十页。 在哈希文件中进行查找时在哈希文件中进行查找时,首先根据给定值求出哈希桶地址首先根据给定值求出哈希桶地址,将基将基桶的记录读入内存桶的记录读入内存,进行顺序查找进行顺序查找,若找到关键字等于给定值的记录若找到关键字等于给定值的记录,则检索成功；否则则检索成功；否则(fuz),读入溢出桶的记录继续进行查找。读入溢出桶的记录继续进行查找。 在哈希文件中删去一个记录在哈希文件中删去一个记录,仅需对被

28、删记录作删除标记即可。仅需对被删记录作删除标记即可。第二十七页，共四十页。 哈希文件的优点哈希文件的优点(yudin)是：文件随机存放是：文件随机存放,记录不需进行排序；插记录不需进行排序；插 入、删除方便；存取速度快；不需要索引区入、删除方便；存取速度快；不需要索引区,节省存储空间。节省存储空间。 其缺点是：不能进行顺序存取其缺点是：不能进行顺序存取,只能按关键字随机存取只能按关键字随机存取,且且询问方式限于简单询问询问方式限于简单询问,并且在经过多次插入、删除后并且在经过多次插入、删除后,也可能也可能造成文件结构不合理造成文件结构不合理,需要重新组织文件。需要重新组织文件。 第二十八页，共

29、四十页。12.5 多关键字文件多关键字文件 前面的文件都是只含一个主关键字的文件。前面的文件都是只含一个主关键字的文件。 为了提高查找效率为了提高查找效率,还需要对被查询还需要对被查询(chxn)的次关键字建立相应的次关键字建立相应的索引的索引,这种包含有多个次关键字索引的文件称为多关键字文件。这种包含有多个次关键字索引的文件称为多关键字文件。次关键字索引本身可以是顺序表次关键字索引本身可以是顺序表,也可以是树表。下面讨论两种多也可以是树表。下面讨论两种多关键字文件的组织方法。关键字文件的组织方法。第二十九页，共四十页。12.5.1 多重表文件多重表文件 多重表文件是将索引方法多重表文件是将索

30、引方法(fngf)和链接方法和链接方法(fngf)相结合的一相结合的一种组织方式种组织方式,它对每个需要查询的次关键字建立一个索引它对每个需要查询的次关键字建立一个索引,同时同时将具有相同次关键字的记录链接成一个链表将具有相同次关键字的记录链接成一个链表,并将此链表的头指并将此链表的头指针、链表长度及次关键字针、链表长度及次关键字,作为索引表的一个索引项。作为索引表的一个索引项。 通常多重表文件的主文件是一个顺序文件。通常多重表文件的主文件是一个顺序文件。 第三十页，共四十页。 例如例如,学生表是一个多重表文件的示例。主关键字是学号学生表是一个多重表文件的示例。主关键字是学号,次关键字是次关键

31、字是性别性别(xngbi)、民族和班号。设计对应的多重表文件。、民族和班号。设计对应的多重表文件。 设计三个链接字段设计三个链接字段,分别将具有相同性别、民族和班号的记录链在一起分别将具有相同性别、民族和班号的记录链在一起,由此形成的性别、民族和班号索引见图由此形成的性别、民族和班号索引见图12.8(b)、图、图12.8(c)和图和图12.8(d)。有。有了这些索引了这些索引,便易于处理各种有关次关键字的查询。便易于处理各种有关次关键字的查询。 第三十一页，共四十页。第三十二页，共四十页。 多重表文件检索时同样先查询索引表多重表文件检索时同样先查询索引表,然后再在主文件中然后再在主文件中读出待

32、查记录信息；插入时如果不要求保持链表的某种次序读出待查记录信息；插入时如果不要求保持链表的某种次序,则可将新记录插在链表的头指针之后则可将新记录插在链表的头指针之后(zhhu)；删除记录时比较；删除记录时比较繁琐繁琐,需要在每个次关键字的链表中删去该记录。需要在每个次关键字的链表中删去该记录。 第三十三页，共四十页。12.5.2 倒排文件倒排文件 倒排文件和多重表文件的区别在于具有倒排文件和多重表文件的区别在于具有(jyu)相同次关键字的记相同次关键字的记录不进行链接录不进行链接,而是在相应的次关键字索引表的该索引项中直接列出而是在相应的次关键字索引表的该索引项中直接列出这些记录的物理地址或记

33、录号。这样的索引表称为倒排表。由主文这些记录的物理地址或记录号。这样的索引表称为倒排表。由主文件和倒排表共同组成倒排文件。件和倒排表共同组成倒排文件。 例如例如,设计与图设计与图12.8(a)对应的倒排文件。对应的倒排文件。 第三十四页，共四十页。多重表文件多重表文件(wnjin) 第三十五页，共四十页。 倒排文件的主要优点是：检索记录较快倒排文件的主要优点是：检索记录较快,在处理复杂在处理复杂(fz)的多关键字的多关键字查询时查询时,可在倒排表中确定记录是哪个或哪些可在倒排表中确定记录是哪个或哪些,继而直接读取之；继而直接读取之； 倒排文件的缺点是维护困难：在同一倒排表中倒排文件的缺点是维护

34、困难：在同一倒排表中,不同关键字不同关键字的记录数不同的记录数不同,各倒排表的长度也不等。各倒排表的长度也不等。第三十六页，共四十页。思考题：思考题：通过文件的学习对于大型软件开发有什么通过文件的学习对于大型软件开发有什么(shn me)启示？启示？第三十七页，共四十页。本章小结本章小结本章的基本学习要点如下：本章的基本学习要点如下： (1) 理解文件的基本概念。理解文件的基本概念。 (2) 掌握各种文件的结构掌握各种文件的结构,包括顺序包括顺序(shnx)文件、索引文件、索引顺序文件、索引文件、索引顺序(shnx)文件、哈希文件和多关键字文件等。文件、哈希文件和多关键字文件等。 第三十八页，共四十页。练习练习(linx)12 教材中教材中p321习题习题2。第三十九页，共四十页。内容(nirng)总结第12章 文 件。若文件中记录(jl)含有的信息长度不等,则称做不定长文件。(2) 索引中的每个记录(jl)由“关键字”和“指针”组成。初建时的“静态索引”为无序文件,经过排序后成为有序文件。2. 控制区间和控制区域。控制区域：由若干控制区间和它们的索引项组成,可看成是一个逻辑柱面。检索：可进行顺序存取和按关键字存取。桶的容量m=3,桶数b=7。教材中p321习题2第四十页，共四十页。