《【精品】【考研计算机专业课】武汉大学数据结构PPT课件 第12章文件精品ppt课件.ppt》由会员分享，可在线阅读，更多相关《【精品】【考研计算机专业课】武汉大学数据结构PPT课件 第12章文件精品ppt课件.ppt（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、【考研计算机专业课】武汉大学数据结构PPT课件 第12章 文件12.1 文件的基本概念文件的基本概念12.1.1 什么是文件什么是文件 文件文件是性质相同的记录的集合。文件的数据量通常很大是性质相同的记录的集合。文件的数据量通常很大,它它被放置在外存上。被放置在外存上。数据结构中所讨论的文件主要是数据库意义上的文件数据结构中所讨论的文件主要是数据库意义上的文件,而不而不是操作系统意义上的文件。操作系统中研究的文件是一维的无是操作系统意义上的文件。操作系统中研究的文件是一维的无结构连续字符序列结构连续字符序列,数据库中所研究的文件是带有结构的记录集数据库中所研究的文件是带有结构的记录集合合,每个
2、记录可由若干个数据项构成。每个记录可由若干个数据项构成。记录记录是文件中存取的基本单位是文件中存取的基本单位,数据项数据项是文件可使用的最小是文件可使用的最小单位。数据项有时也称为单位。数据项有时也称为字段字段。其值能惟一标识一个记录的数。其值能惟一标识一个记录的数据项或数据项的组合称为据项或数据项的组合称为主关键字项主关键字项,其他不能惟一标识一个记其他不能惟一标识一个记录的数据项则称为录的数据项则称为次关键字项次关键字项,主关键字项主关键字项(或次关键字项或次关键字项)的值的值称为称为主关键字主关键字(或或次关键字次关键字)。为讨论方便起见为讨论方便起见,我们仍不严格区分关键字项和关键字我
3、们仍不严格区分关键字项和关键字,即即在不易混淆时在不易混淆时,将主将主(或次或次)关键字项简称为主关键字项简称为主(或次或次)关键字关键字,并且并且假定主关键字项只含一个数据项假定主关键字项只含一个数据项。文文件件可可以以按按照照记记录录中中关关键键字字的的多多少少,分分成成单单关关键键字字文文件件和和多多关关键键字字文文件件。若若文文件件中中的的记记录录只只有有一一个个惟惟一一标标识识记记录录的的主主关关键键字字,则则称称其其为为单单关关键键字字文文件件；若若文文件件中中的的记记录录除除了了含含有有一一个主关键字外个主关键字外,还含有若干个次关键字还含有若干个次关键字,则称为则称为多关键字文
4、件多关键字文件。文件又可分成定长文件和不定长文件。若文件中记录含文件又可分成定长文件和不定长文件。若文件中记录含有的信息长度相同有的信息长度相同,则称这类记录为定长记录则称这类记录为定长记录,由这种定长记录由这种定长记录组成的文件称做组成的文件称做定长文件定长文件；若文件中记录含有的信息长度不；若文件中记录含有的信息长度不等等,则称做则称做不定长文件不定长文件。12.1.2 文件的逻辑结构及操作文件的逻辑结构及操作 文文件件中中各各记记录录之之间间存存在在着着逻逻辑辑关关系系,当当一一个个文文件件的的各各个个记记录录按按照照某某种种次次序序排排列列起起来来时时(这这种种排排列列的的次次序序可可
5、以以是是记记录录中中关关键键字字的的大大小小,也也可可以以是是各各个个记记录录存存入入该该文文件件的的时时间间先先后后等等等等),各各记记录录之之间间就就自自然然地地形形成成了了一一种种线线性性关关系系。在在这这种种次次序序下下,文文件件中中每每个个记记录录最最多多只只有有一一个个后后继继记记录录和和一一个个前前驱驱记记录录,而而文文件件的的第第一一个个记记录录只只有有后后继继没没有有前前驱驱,文文件件的的最最后后一一个个记记录录只只有有前前驱驱而没有后继。因此而没有后继。因此,文件可看成是一种线性结构文件可看成是一种线性结构。文件上的操作主要有两类：检索和维护。文件上的操作主要有两类：检索和
6、维护。顺序文件的操作特点：顺序文件的操作特点：(1)便于进行顺序存取；便于进行顺序存取；(2)不不便便于于进进行行直直接接存存取取,为为取取第第i个个记记录录,必必须须先先读读出出前前i-1个个记记录录,对对于于磁磁盘盘上上的的等等长长记记录录的的连连续续文文件件可可以以进进行行折折半查找；半查找；(3)插入新的记录只能加在文件的末尾；插入新的记录只能加在文件的末尾；(4)删除记录时删除记录时,只作标记；只作标记；(5)更新记录必须生成新的文件。更新记录必须生成新的文件。12.3 索引文件索引文件 用用索索引引的的方方法法组组织织文文件件时时,通通常常是是在在文文件件本本身身(称称为为主主文文
7、件件)之之外外,另另外外建建立立一一张张表表,它它指指明明逻逻辑辑记记录录和和物物理理记记录录之之间间的的一一一一对对应应关关系系,这这张张表表就就叫叫做做索索引引表表,它它和和主主文文件件一一起起构构成成的的文文件件称作索引文件。称作索引文件。索索引引表表中中的的每每一一项项称称作作索索引引项项,一一般般索索引引项项都都是是由由主主关关键键字字和和该该关关键键字字所所在在记记录录的的物物理理地地址址组组成成的的。显显然然,索索引引表表必必须须按按主主关关键键字字有有序序,而而主主文文件件本本身身则则可可以以按按主主关关键键字字有有序序或或无无序序,前者称为前者称为索引顺序文件索引顺序文件,后
8、者称为后者称为索引非顺序文件索引非顺序文件。对于索引非顺序文件对于索引非顺序文件,由于主文件中记录是无序的由于主文件中记录是无序的,则则必须为每个记录建立一个索引项必须为每个记录建立一个索引项,这样建立的索引表称为这样建立的索引表称为稠稠密索引密索引。对于索引顺序文件对于索引顺序文件,由于主文件中记录按关键字有序由于主文件中记录按关键字有序,则则可对一组记录建立一个索引项可对一组记录建立一个索引项,例如例如,让文件中每个页块对让文件中每个页块对应一个索引项应一个索引项,这种索引表称之为这种索引表称之为稀疏索引稀疏索引。通常可将索引非顺序文件简称为索引文件通常可将索引非顺序文件简称为索引文件,本
9、节只讨论本节只讨论这种文件。这种文件。索引文件在存储器上分为两个区：索引区和数据区索引文件在存储器上分为两个区：索引区和数据区,前者存前者存放索引表放索引表,后者存放主文件。在建立文件过程中后者存放主文件。在建立文件过程中,按输入记录的先按输入记录的先后次序建立数据区和索引表后次序建立数据区和索引表,这样的索引表其关键字是无字的这样的索引表其关键字是无字的,待待全部记录输入完毕后再对索引表进行排序全部记录输入完毕后再对索引表进行排序,排序后的索引表和主排序后的索引表和主文件一起就形成了索引文件。文件一起就形成了索引文件。14物理地址12345学号姓名其他物理地址关键字物理地址物理地址关键字物理
10、地址1李明101110115王平115211333张萍123312458陈强138413524马伟144584索引文件的结构特点：索引文件的结构特点：(1)索引文件由索引文件由“主文件主文件”和多级和多级“索引索引”组成；组成；(2)索引中的每个记录由索引中的每个记录由“关键字关键字”和和“指针指针”组成；组成；(3)通通常常,索索引引文文件件中中的的主主文文件件是是无无序序文文件件,索索引引是是(按按关关键键字有序字有序)的有序文件；的有序文件；(4)“索索引引”是是在在输输入入数数据据建建立立文文件件时时自自动动生生成成。初初建建时时的的“静态索引静态索引”为无序文件为无序文件,经过排序后
11、成为有序文件。经过排序后成为有序文件。索引文件的操作特点：索引文件的操作特点：(1)检检索索方方式式为为：直直接接存存取取和和按按关关键键字字存存取取。“按按关关键键字字检检索索”将将分分两两步步进进行行：先先查查索索引引,然然后后根根据据索索引引中中指指针针所所指指索索取取记录；记录；(2)插插入入记记录录时时,“记记录录”插插入入在在主主文文件件的的末末尾尾,而而相相应应的的“索索引引项项”必必须须插插入入在在索索引引的的合合适适位位置置上上。因因此此,最最好好在在建建索索引引表表时留有一定时留有一定“空位空位”；(3)删除记录时删除记录时,仅需删除索引表中相应的索引项即可；仅需删除索引表
12、中相应的索引项即可；(4)更更新新记记录录时时,应应将将更更新新后后的的记记录录插插入入在在主主文文件件的的末末尾尾,同同时修改相应的索引项。时修改相应的索引项。有两种典型的索引顺序文件。有两种典型的索引顺序文件。12.2.1 ISAM文件文件 ISAM(Index Sequential Access Method)(索引顺序存取索引顺序存取方法方法)是一种专为磁盘存取设计的文件组织方法。是一种专为磁盘存取设计的文件组织方法。1.文件的组织方式文件的组织方式主文件按柱面集中存放主文件按柱面集中存放,同时建立三级索引：同时建立三级索引：(1)磁道索引磁道索引 (2)柱面索引柱面索引 (3)主索引
13、主索引磁道索引结构如下：磁道索引结构如下：基本索引项基本索引项溢出索引项溢出索引项关键字关键字 指针指针 关键字关键字 指针指针2101024主主索索引引 r(14)r(21)r(38)r(41)r(57)r(63)r(72)r(85)r(99)溢溢 出出 区区 磁磁 道道 索索 引引 r(514)溢溢 出出 区区 磁道索引磁道索引 r(1024)一一 个个 柱柱 面面 .柱柱面面索索引引992101024T0T1T2T3T4T52.操作的特点操作的特点 (1)检索检索 可有两种方式：可有两种方式：顺序存取顺序存取 依关键字最小至大顺序存取。依关键字最小至大顺序存取。按关键字存取按关键字存取
14、从主索引开始从主索引开始,到到 柱面索引柱面索引,到磁道索引到磁道索引,最后取最后取 得记录得记录,先后访问四次外存。先后访问四次外存。(2)插入插入 将记录插入在某个磁道的合适位置上将记录插入在某个磁道的合适位置上;将该磁道上关键字最将该磁道上关键字最大的记录移出到本柱面的溢出区中大的记录移出到本柱面的溢出区中;修改本磁道的索引项修改本磁道的索引项(包括包括基本索引项和溢出索引项基本索引项和溢出索引项)。(3)删除删除 在被删记录当前存储位置上在被删记录当前存储位置上 作作“删除标记删除标记”。3.文件重组文件重组 在经过多次的插入和删除操作之后在经过多次的插入和删除操作之后,大量的记录进入
15、文件的大量的记录进入文件的溢出区溢出区”,而而“基本存储区基本存储区”中出现很多已被删去的记录空间中出现很多已被删去的记录空间,此时此时的文件结构很不合理。因此的文件结构很不合理。因此,对对ISAM文件文件,需要周期地进行重整。需要周期地进行重整。12.3.2 VSAM文件文件 VSAM是虚拟存储存取方法是虚拟存储存取方法(Virtual Storage Access Method)的英文缩写。的英文缩写。VSAM文件是一种采用虚拟存储存取方文件是一种采用虚拟存储存取方法的文件。法的文件。VSAM文件的存储单位是控制区间和控制区域文件的存储单位是控制区间和控制区域,这是一些逻这是一些逻辑存储单
16、位辑存储单位,与柱面、磁道等实际存储单位并没有必然的联系。与柱面、磁道等实际存储单位并没有必然的联系。用户在存取用户在存取VSAM文件的记录时文件的记录时,不需要考虑该记录的当前位不需要考虑该记录的当前位置是在内存还是在外存置是在内存还是在外存,也不需要考虎何时执行对外存进行读也不需要考虎何时执行对外存进行读写的命令。可见写的命令。可见,这种文件较这种文件较ISAM文件更方便用户使用。文件更方便用户使用。1文件的结构文件的结构.索引集索引集B+树树 顺序集顺序集控制区域控制区间数据集数据集2.控制区间和控制区域控制区间和控制区域 控制区间：控制区间：是用户进行一次存取的逻辑单位是用户进行一次存
17、取的逻辑单位,可看成是一可看成是一个逻辑磁道。但它的实际大小和物理磁道无关。个逻辑磁道。但它的实际大小和物理磁道无关。控制区域：控制区域：由若干控制区间和它们的索引项组成由若干控制区间和它们的索引项组成,可看成可看成是一个逻辑柱面。是一个逻辑柱面。VSAM文件初建时文件初建时,每个控制区间内的记录数不足额定数每个控制区间内的记录数不足额定数,并且有的控制区间内的记录数为零。并且有的控制区间内的记录数为零。3.顺序集顺序集 本身是一个单链表本身是一个单链表,它包含文件的全部索引项它包含文件的全部索引项,同时同时,顺序顺序集中的每个结点即为集中的每个结点即为B+树的叶子结点树的叶子结点,索引集中的
18、结点即为索引集中的结点即为B+树的非叶结点。树的非叶结点。4.文件的操作文件的操作 检索：检索：可进行顺序存取和按关键字存取；可进行顺序存取和按关键字存取；插插入入：按按关关键键字字大大小小插插入入在在某某个个适适当当的的控控制制区区间间中中,当当控控制制区区间间中中的的记记录录数数超超过过文文件件规规定定的的大大小小时时,要要“分分裂裂”控控制制区区间间,必要时必要时,还需要还需要“分裂分裂”控制区域；控制区域；删删除除：必必须须“真真实实地地”删删除除记记录录,因因此此要要在在控控制制区区间间内内“移移动动”记录。记录。5.VSAM文件通常被作为大型索引文件通常被作为大型索引 顺序文件的标
19、准组织方式。顺序文件的标准组织方式。优点优点：动态地分配和释放空间：动态地分配和释放空间,不需要重组文件；能较快不需要重组文件；能较快地实现对地实现对“后插入后插入”的记录的检索；的记录的检索；缺点缺点：占有较多的存储空间：占有较多的存储空间,一般只能保持约一般只能保持约75%的存储的存储空间利用率。空间利用率。(因此因此,一般情况下一般情况下,极少产生需要分裂控制区域极少产生需要分裂控制区域的情况的情况)12.4 哈希文件哈希文件 哈哈希希文文件件也也称称为为散散列列文文件件,是是利利用用哈哈希希存存储储方方式式组组织织的的文文件件,亦亦称称为为直直接接存存取取文文件件。它它类类似似于于哈哈
20、希希表表,即即根根据据文文件件中中关关键键字字的的特特点点,设设计计一一个个哈哈希希函函数数和和处处理理冲冲突突的的方方法法,将将记记录录哈哈希希到到存存储储设设备上。备上。与与哈哈希希表表不不同同的的是是,对对于于文文件件来来说说,磁磁盘盘上上的的文文件件记记录录通通常常是是成成组组存存放放的的,若若干干个个记记录录组组成成一一个个存存储储单单位位,在在哈哈希希文文件件中中,这这个个存存储储单单位位叫叫做做桶桶。假假如如一一个个桶桶能能存存放放m个个记记录录,则则当当桶桶中中已已有有m个个同同义义词词的的记记录录时时,存存放放第第m+1个个同同义义词词会会发发生生“溢溢出出”。处处理理溢溢出
21、出虽虽可可采采用用哈哈希希表表中中处处理理冲冲突突的的各各种种方方法法,但但对对哈哈希希文文件件而而言言,主主要要采采用用链链地址法。地址法。当发生当发生“溢出溢出”时时,需要将第需要将第m+1个同义词存放到另一个桶个同义词存放到另一个桶中中,通常称此桶为通常称此桶为“溢出桶溢出桶”。相对地。相对地,称前称前m个同义词存放的桶个同义词存放的桶为为“基桶基桶”。溢出桶和基桶大小相同溢出桶和基桶大小相同,相互之间用指针链接。当在基桶中相互之间用指针链接。当在基桶中没有找到待查记录时没有找到待查记录时,就沿着指针到所指溢出桶中进行查找就沿着指针到所指溢出桶中进行查找,因因此此,希望同一哈希地址的溢出
22、桶和基桶在磁盘上的物理位置不希望同一哈希地址的溢出桶和基桶在磁盘上的物理位置不要相距太远要相距太远,最好在同一柱面上。最好在同一柱面上。例如例如,某一文件有某一文件有20个记录个记录,其关键字集合为其关键字集合为 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。给出对应的哈希。给出对应的哈希文件。文件。在在哈哈希希文文件件中中进进行行查查找找时时,首首先先根根据据给给定定值值求求出出哈哈希希桶桶地地址址,将将基基桶桶的的记记录录读
23、读入入内内存存,进进行行顺顺序序查查找找,若若找找到到关关键键字字等等于于给给定定值的记录值的记录,则检索成功；否则则检索成功；否则,读入溢出桶的记录继续进行查找。读入溢出桶的记录继续进行查找。在在哈哈希希文文件件中中删删去去一一个个记记录录,仅仅需需对对被被删删记记录录作作删删除除标标记记即即可。可。哈希文件的优点是：文件随机存放哈希文件的优点是：文件随机存放,记录不需进行排序；记录不需进行排序；插插 入、删除方便；存取速度快；不需要索引区入、删除方便；存取速度快；不需要索引区,节省存储空节省存储空间。间。其缺点是：不能进行顺序存取其缺点是：不能进行顺序存取,只能按关键字随机存取只能按关键字
24、随机存取,且询问方式限于简单询问且询问方式限于简单询问,并且在经过多次插入、删除后并且在经过多次插入、删除后,也也可能造成文件结构不合理可能造成文件结构不合理,需要重新组织文件。需要重新组织文件。12.5 多关键字文件多关键字文件 前面的文件都是只含一个主关键字的文件。前面的文件都是只含一个主关键字的文件。为为了了提提高高查查找找效效率率,还还需需要要对对被被查查询询的的次次关关键键字字建建立立相相应应的的索索引引,这这种种包包含含有有多多个个次次关关键键字字索索引引的的文文件件称称为为多多关关键键字字文文件件。次次关关键键字字索索引引本本身身可可以以是是顺顺序序表表,也也可可以以是是树树表表
25、。下下面面讨讨论两种多关键字文件的组织方法。论两种多关键字文件的组织方法。12.5.1 多重表文件多重表文件 多重表文件是将索引方法和链接方法相结合的一种组织多重表文件是将索引方法和链接方法相结合的一种组织方式方式,它对每个需要查询的次关键字建立一个索引它对每个需要查询的次关键字建立一个索引,同时将具同时将具有相同次关键字的记录链接成一个链表有相同次关键字的记录链接成一个链表,并将此链表的头指针、并将此链表的头指针、链表长度及次关键字链表长度及次关键字,作为索引表的一个索引项。作为索引表的一个索引项。通常多重表文件的主文件是一个顺序文件。通常多重表文件的主文件是一个顺序文件。例例如如,学学生生
26、表表是是一一个个多多重重表表文文件件的的示示例例。主主关关键键字字是是学学号号,次关键字是性别、民族和班号。设计对应的多重表文件。次关键字是性别、民族和班号。设计对应的多重表文件。设计三个链接字段设计三个链接字段,分别将具有相同性别、民族和班号的记分别将具有相同性别、民族和班号的记录链在一起录链在一起,由此形成的性别、民族和班号索引见图由此形成的性别、民族和班号索引见图12.8(b)、图图12.8(c)和图和图12.8(d)。有了这些索引。有了这些索引,便易于处理各种有关次关便易于处理各种有关次关键字的查询。键字的查询。多重表文件检索时同样先查询索引表多重表文件检索时同样先查询索引表,然后再在
27、主文件然后再在主文件中读出待查记录信息；插入时如果不要求保持链表的某种次中读出待查记录信息；插入时如果不要求保持链表的某种次序序,则可将新记录插在链表的头指针之后；删除记录时比较则可将新记录插在链表的头指针之后；删除记录时比较繁琐繁琐,需要在每个次关键字的链表中删去该记录。需要在每个次关键字的链表中删去该记录。12.5.2 倒排文件倒排文件 倒排文件和多重表文件的区别在于具有相同次关键字的倒排文件和多重表文件的区别在于具有相同次关键字的记录不进行链接记录不进行链接,而是在相应的次关键字索引表的该索引项而是在相应的次关键字索引表的该索引项中直接列出这些记录的物理地址或记录号。这样的索引表称中直接
28、列出这些记录的物理地址或记录号。这样的索引表称为倒排表。由主文件和倒排表共同组成倒排文件。为倒排表。由主文件和倒排表共同组成倒排文件。例如例如,设计与图设计与图12.8(a)对应的倒排文件。对应的倒排文件。多重表文件多重表文件 倒排文件的主要优点是：检索记录较快倒排文件的主要优点是：检索记录较快,在处理复杂的多在处理复杂的多关键字查询时关键字查询时,可在倒排表中确定记录是哪个或哪些可在倒排表中确定记录是哪个或哪些,继而直继而直接读取之；接读取之；倒排文件的缺点是维护困难：在同一倒排表中倒排文件的缺点是维护困难：在同一倒排表中,不同关键不同关键字的记录数不同字的记录数不同,各倒排表的长度也不等。各倒排表的长度也不等。思考题：思考题：通过文件的学习对于大型软件开发有什么启示？通过文件的学习对于大型软件开发有什么启示？本章小结本章小结本章的基本学习要点如下：本章的基本学习要点如下：(1)理解文件的基本概念。理解文件的基本概念。(2)掌握各种文件的结构掌握各种文件的结构,包括顺序文件、索引文件、索引包括顺序文件、索引文件、索引顺序文件、哈希文件和多关键字文件等。顺序文件、哈希文件和多关键字文件等。练习练习12 教材中教材中p321习题习题2。