数据结构-文件

第十章文件基本概念顺序文件索引文件

ISAM文件和VSAM文件散列文件（直接存取文件）多关键字文件基本概念文件：是由大量性质相同的记录组成的集合。（通常，存储在外存储器中。）操作系统文件（系统文件）：仅是一维的连续的字符序列，无结构、无解释。数据库文件：是带有结构的记录的集合，这类记录是由一个或多个数据项组成的集合。（分为：单关键字文件、多关键字文件）定长记录文件：文件中每个记录含有的信息长度相同。不定长记录文件：文件中含有信息长度不等。基本概念记录的逻辑结构：是指记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方式。（它着眼于用户使用方便）记录的物理结构：是数据在物理存储器上的存储方式，是数据的物理表示和组织。（它着眼于存储空间的提高和存取时间的减少）基本概念文件的操作：检索和修改检索（1）顺序存取：存取下一个逻辑记录（2）直接存取：存取第i个记录（3）按关键字存取：给定一个值，查询一个和一批关键字与给定值相关的记录。查询：（1）简单查询：查询关键字等于给定值的记录。（2）区域查询：查询关键字属于某个区域的记录。（3）函数查询：给定关键字的某个函数。（4）布尔查询：将上述三种查询用布尔运算组合起来的查询。基本概念修改插入删除更新文件的物理结构文件在存储介质上的组织方式。（1）顺序组织（2）随机组织（3）链组织顺序文件顺序文件是物理结构最简单的文件，也是数据处理历史上最早使用的文件结构。顺序文件是记录按其在文件中的逻辑顺序依次进入而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序一致。连续文件：若次序相继的两个物理记录在存储介质上的存储位置是相邻的，则又称为连续文件。串联文件：若物理记录之间的次序由指针相连表示，则称为串联文件。

顺序文件当需要对磁带顺序文件进行检索时，一般是采用顺序扫描的方式来检索满足查询条件的记录。例如，若要检索第i个记录，则必须先检索前面的i-1个记录。为了提高平均检索效率，可采用批量处理技术。如果将对文件的多个检索请求加以积累和排序，则形成一个称为待办文件（或事务文件）的文件。如果将被查询的文件称为主文件，则批量检索就是按照待办文件的要求成批地检索主文件。批量检索对于实时应用来说是不适宜的，因为实时查询要求响应时间快，而在很短的时间间隔内，积累的批处理文件规模太小，不能表现出它的优越性。在磁带顺序文件中插入记录，只能加在文件的末尾，不能插在两个原有记录之间。顺序文件修改记录，即使在新旧记录等长的情况下，将新记录写在旧记录的位置上，一般不但不可能完全重合，甚至还会破坏邻近记录的信息。因此，修改一个磁带文件，需要用另一条磁带将原文件复制过来，在复制过程中进行插入、删除、修改记录的操作。为了提高效率，修改一个顺序文件，也采用成批处理技术。这种批量修改方式很适用于银行帐户结算管理系统。例如，可把一天的零星支取和存入分别作为记录收集在一起，构成为一个待办文件，在当天下班时再按照待办文件进行批量修改主文件（头天下班修改过的主文件）的工作，便得到一个新主文件。顺序文件顺序文件的基本优点是在连续存取时速度较快。例如，如果文件中的第i个记录刚被存取过，而下一个要存取的记录就是第i+1个记录，则此次存取将会很快完成。磁带是比较适用于这种应用的外存设备。存放于磁带上的文件也只能是顺序文件，这是由磁带的物理特性决定的。存放于磁盘上的文件，既可以是顺序文件，也可以是索引结构或其它结构类型的文件。索引文件顺序文件的查询速度很慢。采用索引文件可以提高检索效率。索引用来表示关键字与相应记录的存储地址之间的对应关系。换言之，索引指出了记录在存储器中的存储地址。设记录Ri的关键字为Ki，Ri在外存中的存储地址为Ai，则（Ki，Ai）称为记录Ri的索引项。索引表（简称索引）是索引项的集合。如果文件中的每个记录都有一个索引项，则这样的索引称为稠密索引。如果多个记录只有一个索引项，则这样的索引称为非稠密索引。带有索引的文件称为索引文件。索引也称为目录。索引文件索引文件在外存（磁盘、磁鼓等）中可分为两个存储区：索引区和记录区（数据区）。索引表中的索引项顺序存放在索引区中，但为了便于检索，索引项一般按关键字的大小次序排列。文件中的记录按输入的先后次序存放到记录区；记录区按关键字大小次序排列的索引文件称为索引顺序文件。对于索引顺序文件，可以不必使用稠密索引，只为一个记录块（含多个有序记录）建立一个索引项。记录区不按关键字大小次序排列的索引文件称为索引非顺序文件，这时应使用稠密索引。索引文件通常，索引项所含的数据信息比记录少得多，因而索引所需的存储空间比文件本身（记录区）所需要的存储空间少得多。在文件的记录数较少的情况下，可以为每个记录建立一个索引项。文件建立时，开辟一个索引区，一般固定在某个磁盘面的一个或多个磁道上。写入一个记录到记录区时，在索引区相应登入一个索引项，即把该记录的关键字（主关键字）和记录的存储地址顺序写入索引区。文件建立后，将索引区中的索引读入内存的缓冲区，按关键字进行内部排序。最后将排序好的索引项顺序写回到磁盘上的索引区。根据关键字查找索引文件的记录分两步进行。第1步，访问外存的索引区，将索引读入内存缓冲区，使用顺序查找或折半查找法找出所查记录在外存数据区中的地址，这一过程称为预查找。第2步，如果在预查中已找到了所查记录的地址，则第2次访问外存，根据已查到的地址，读取所查的记录ISAM文件和VSAM文件ISAM(IndexedSequentialAccessMethed)索引顺序存取方法是专为磁盘存取设计的一种文件组织方式。由于磁盘由盘组、柱面和磁道(实际是盘片)三级组成，因此通常对磁盘上的数据文件建立盘组、柱面和磁道(盘面)三级索引。在ISAM文件上检索记录时，先从主索引(柱面索引的索引)找到相应柱面索引。再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直到查到为止;反之，若找遍该磁道而未找到所查记录，则文件中无此记录。ISAM文件和VSAM文件ISAM文件中记录按关键字顺序存放，插入记录时需移动记录并将同一磁道上最后的一个记录移至溢出区，同时修改磁道索引项，删除记录只需在存储位置作标记，不需移动记录和修改指针。经过多次插入和删除记录后，文件结构变得不合理，需周期整理ISAM文件。ISAM文件和VSAM文件VSAM(VirtualStorageAccessMethod)虚拟存储存取方法这种存取方法利用了操作系统的虚拟存储器的功能。对用户来说，文件只有控制区间和控制区域等逻辑存储单位，与外存储器中柱面、磁道等具体存储单位没有必然联系。VSAM文件采用B+树动态索引结构，VSAM文件结构包括索引集、顺序集和数据集三部分，记录存于数据集中，顺序集和索引集构成B+树，作为文件的索引部分可实现顺链查找和从根结点开始的随机查找。ISAM文件和VSAM文件与ISAM文件相比，VSAM文件有如下优点：动态分配和释放存储空间，不需对文件进行重组;能保持较高的查找效率，且查找先后插入记录所需时间相同。因此，基于B+树的VSAM文件通常作为大型索引顺序文件的标准组织。直接存取文件（散列文件）直接存取文件，根据关键字的散列函数值和处理冲突的方法，将记录散列到外存上。这种文件组织只适用于像磁盘那样的直接存取设备，其优点是文件随机存放，记录不必排序，插入、删除方便，存取速度快，无需索引区，节省存储空间。缺点是散列文件不能顺序存取，且只限于简单查询。经多次插入、删除后，文件结构不合理，需重组文件，这很费时。多关键字文件多关键字文件的特点是，在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。多重表文件多重表文件是把索引与链接结合而形成的组织方式。记录按主关键字顺序构成一个串联文件，建立主关键字的索引(主索引)。对每一次关键字建立次关键字索引，具有同一关键字的记录构成一个链表。主索引为非稠密索引，次索引为稠密索引，每个索引项包括次关键字，头指针和链表长度。多重表文件易于编程，也易于插入，但删除繁锁。需在各次关键字链表中删除。多关键字文件倒排文件倒排文件是一种多关键字的文件，主数据文件按关键字顺序构成串联文件，并建立主关键字索引。对次关键字也建立索引，该索引称为倒排表。倒排表包括两项，一项是次关键字，另一项是具有同一次关键字值的记录的物理记录号(若数据文件非串联文件，而是索引顺序文件—如ISAM，则倒排表中存放记录的主关键字而不是物理记录号)。倒排表作索引的优点是索引记录快，缺点是维护困难。在同一索引表中，不同的关键字其记录数不同，各倒排表的长度不同，同一倒排表中各项长度也不相等。附录磁带：磁带有不同的规格。目前使用的磁带一般有1/2英寸宽，最长可达3600英尺。1/2英寸的带在横向上可记录9位或7位二进制信息（分别称为9道带或7道带）。磁带上的信息是以块为单位存放的。一个信息块由若干个字节构成，如512字节或1024字节，要读写某一块上信息，首先要定位，即通过磁带的移动使磁头对准磁块的前端，磁带不是连续运转的设备，而是一种启停设备。为适应启动时的加速和停止时的滑动，磁带上块与块之间隙。间隙通常为1/4--3/4英尺长。间隙是一段空白区，不存放