资源描述：
《数据结构(严蔚敏)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、索引文件索引文件由索引表和主文件两部分构成。索引表是一张指示逻辑记录和物理记录之间对应关糸的表。索引表中的每项称作索引项。索引项是按键（或逻辑记录号）顺序排列。若文件本身也是按关键字顺序排列，则称为索引顺序文件。否则，称为索引非顺序文件。（1）索引顺序文件(IndexedSequentialFile)主文件按主关键字有序的文件称索引顺序文件。在索引顺序文件中，可对一组记录建立一个索引项。这种索引表称为稀疏索引。（2）索引非顺序文件(IndexedNonSequentailFile)主文件按主关键字无序得文件称索引非顺序文件。在索引非顺序文件中，必须为每个记录建立一个索引项，这样建立的索
2、引表称为稠密索引。注意：①通常将索引非顺序文件简称为索引文件。②索引非顺序文件主文件无序，顺序存取将会频繁地引起磁头移动，适合于随机存取，不适合于顺序存取。③索引顺序文件的主文件是有序的，适合于随机存取、顺序存取。④索引顺序文件的索引是稀疏索引。索引占用空间较少，是最常用的一种文件组织。⑤最常用的索引顺序文件：ISAM文件和VSAM文件。文件一、基础知识题11.1名词解释：索引文件,索引顺序文件，ISAM文件，VSAM文件，散列文件，倒排文件。【解答】先介绍文件的概念：文件是由大量性质相同的记录组成的集合,按记录类型不同可分为操作系统文件和数据库文件。文件的基本组织方式有顺序组织、索引
3、组织、散列组织和链组织。文件的存储结构可以采用将基本组织结合的方法,常用的结构有顺序结构、索引结构、散列结构。（1）顺序结构,相应文件为顺序文件,其记录按存入文件的先后次序顺序存放。顺序文件本质上就是顺序表。若逻辑上相邻的两个记录在存储位置上相邻,则为连续文件；若记录之间以指针相链接,则称为串联文件。顺序文件只能顺序存取,要更新某个记录,必须复制整个文件。顺序文件连续存取的速度快,主要适用于顺序存取,批量修改的情况。（2）带索引的结构,相应文件为索引文件。索引文件包括索引表和数据表,索引表中的索引项包括数据表中数据的关键字和相应地址,索引表有序,其物理顺序体现了文件的逻辑次序,实现了文
4、件的线性结构。索引文件只能是磁盘文件,既能顺序存取,又能随机存取。（3）散列结构,也称计算寻址结构,相应文件称为散列文件,其记录是根据关键字值经散列函数计算确定其地址,存取速度快,不需索引,节省存储空间。不能顺序存取,只能随机存取。其它文件均由以上文件派生而得。文件采用何种存储结构应综合考虑各种因素,如：存储介质类型、记录的类型、大小和关键字的数目以及对文件作何种操作。索引文件：在主文件外,再建立索引表指示关键字及其物理记录的地址间一一对应关系。这种由索引表和主文件一起构成的文件称为索引文件。索引表依关键字有序。主文件若按关键字有序称为索引顺序文件,否则称为索引非顺序文件（通常简称索引
5、文件）。索引顺序文件因主文件有序,一般用稀疏索引,占用空间较少。ISAM文件：ISAM是专为磁盘存取设计的文件组织方式。即使主文件关键字有序,但因磁盘是以盘组、柱面和磁道（盘面）三级地址存取的设备,因此通常对磁盘上的数据文件建立盘组、柱面和磁道（盘面）三级索引。在ISAM文件上检索记录时,先从主索引（柱面索引的索引）找到相应柱面索引。再从柱面索引找到记录所在柱面的磁道索引,最后从磁道索引找到记录所在磁道的第一个记录的位置,由此出发在该磁道上进行顺序查找直到查到为止；反之,若找遍该磁道而未找到所查记录,则文件中无此记录。VSAM文件：VSAM文件采用B+树动态索引结构,文件只有控制区间和
6、控制区域等逻辑存储单位,与外存储器中柱面、磁道等具体存储单位没有必然联系。VSAM文件结构包括索引集、顺序集和数据集三部分,记录存于数据集中,顺序集和索引集构成B+树,作为文件的索引部分可实现顺链查找和从根结点开始的随机查找。散列文件：散列文件也称直接存取文件,根据关键字的散列函数值和处理冲突的方法,将记录散列到外存上。这种文件组织只适用于像磁盘那样的直接存取设备,其优点是文件随机存放,记录不必排序,插入、删除方便,存取速度快,无需索引区,节省存储空间。缺点是散列文件不能顺序存取,且只限于简单查询。经多次插入、删除后,文件结构不合理,需重组文件,这很费时。倒排文件：倒排文件是一种多关键
7、字的文件,主数据文件按关键字顺序构成串联文件,并建立主关键字索引。对次关键字也建立索引,该索引称为倒排表。倒排表包括两项,一项是次关键字,另一项是具有同一次关键字值的记录的物理记录号（若数据文件非串联文件,而是索引顺序文件—如ISAM,则倒排表中存放记录的主关键字而不是物理记录号）。倒排表作索引的优点是索引记录快,缺点是维护困难。在同一索引表中,不同的关键字其记录数不同,各倒排表的长度不同,同一倒排表中各项长度也不相等。11.2什么是文件的逻辑
