顺序档案是记录按其在档案中的逻辑顺序依次进入存储介质而建立的,即顺序档案中物理记录的顺序和逻辑记录的顺序是一致的。有时档案中的记录个数很多,查找的代价很大,为了加快查找速度,将档案划分为若干块。顺序分块档案是指将顺序档案中若干个记录分为一块,或者是将顺序档案分为若干块。
基本介绍
- 中文名:顺序分块档案
- 外文名:Sequential Block File
- 学科:计算机
- 定义:将顺序档案分为若干块
- 有关术语:顺序档案
- 领域:数据结构
简介
档案是指由创建者所定义的、具有档案名称的一组相关元素的集合。档案在档案系统中是一个最大的数据单位,它描述了一个对象集。例如,可以将一个班的学生记录作为一个档案。
顺序分块档案是是将顺序档案分为若干块,使其分块有序。所谓分块有序(block order)是指将档案划分为若干块,每一块内不要求有序(即快内无序),但第二块中所有记录的关键码均大于第一块中所有记录的关键码,第三块中所有记录的关键码均大于第二块中所有记录的关键码。顺序分块档案主要目的是减少档案查找的代价。
顺序档案
顺序档案是指按记录进入档案的先后顺序存放、其逻辑顺序和物理顺序一致的档案。一切存储在顺序存取存储器(如磁带)上的档案,都只能是顺序档案。顺序档案是最常用的档案组织形式。顺序档案由一系列记录按照某种顺序排列形成。其中的记录通常是定长记录,因而能用较快的速度查找档案中的记录。
顺序档案的最佳套用场合,是在对诸记录进行批量存取时,即每次要读或写一大批记录。此时,对顺序档案的存取效率是所有逻辑档案中最高的;此外,也只有顺序档案才能存储在磁带上,并能有效地工作。
在互动套用的场合,如果用户(程式)要求查找或修改单个记录,为此系统便要去逐个地查找诸记录。这时,顺序档案所表现出来的性能就可能很差,尤其是当档案较大时,情况更为严重。例如,有一个含有104个记录的顺序档案,如果对它採用顺序查找法去查找一个指定的记录,则平均需要查找5×103个记录;如果是可变长记录的顺序档案,则为查找一个记录所需付出的开销将更大,这就限制了顺序档案的长度。
顺序档案的另一个缺点是,如果想增加或删除一个记录,都比较困难。为了解决这一问题,可以为顺序档案配置一个运行记录档案(Log File)或称为事务档案(Transaction File),把试图增加、删除或修改的信息记录于其中,规定每隔一定时间,例如4小时,将运行记录档案与原来的主档案加以合併,产生一个按关键字排序的新档案。
档案结构分类
档案是记录的集合。档案中的记录可以是任意顺序的,因此,它可以按照各种不同的顺序进行排列。一般地,可归纳为以下两种情况:
第一种是串结构,各记录之间的顺序与关键字无关。通常的办法是由时间来决定,即按存入时间的先后排列,最先存入的记录作为第一个记录,其次存入的为第二个记录……,依此类推。
第二种情况是顺序结构,指档案中的所有记录按关键字(词)排列。可以按关键字的长短从小到大排序,也可以从大到小排序;或按其英文字母顺序排序。对顺序结构档案可有更高的检索效率,因为在检索串结构档案时,每次都必须从头开始,逐个记录地查找,直至找到指定的记录,或查完所有的记录为止。
查找方法
顺序分块档案查找方法和顺序档案查找方法差不多,主要有:顺序查找法存取,也可以用分块查找或二分查找进行存取方法。
顺序查找
顺序查找法即顺序扫描档案,按记录的主关键字逐个查找。要检索第i个记录,必须检索前i-1个记录。 注意:
① 这种查找法对于少量的检索是不经济的,但适合于批量检索。
② 顺序存取存储器上的档案只能用顺序查找法存取
分块查找法
具体方法:设档案按主关键字的递增序,每100个记录为一块,各块的最后一个记录的主关键字为Kl00,K200,…,K100i,…:
查找时,将所要查找的记录的主关键字K,依次和各块的最后一个记录的主关键字比较,当K大于K100(i-1)且小于或等于K100i时,则在第i块内进行扫描。
注意:分块查找法在查找时不必扫描整个档案中的记录。
二分查找法
① 二分查找法只适合对较小的档案或一个档案的索引进行查找。
② 当档案很大,在磁碟上占有多个柱面时,二分查找将引起磁头来回移动,增加寻查时间。
③ 对磁碟等直接存取设备,还可以对顺序档案进行插值查找和跳步查找。