10.2　文件组织

选择哪一种文件组织方式,取决于对文件中记录的使用方式和频繁程度、取要求、外存的性质和容量。

常用的外存设备有磁带和磁盘。磁带是顺序存取设备,只适用于存储顺序文件；磁盘是直接存取设备,适用于存储顺序文件、索引文件、散列文件和多关键字文件等。

10.2.1　顺序文件

顺序文件是指按记录进入文件的先后顺序存放,其逻辑顺序与物理顺序一致的文件。一切存储在顺序存取存储器（如磁带）上的文件,都只能是顺序文件。从本质上讲,顺序文件就是顺序存放的线性表。

顺序文件分为串行处理文件和顺序处理文件两种。其中,串行处理文件中的记录未按关键字值排序,一般是按照记录存入文件的先后次序排列的,而顺序处理文件中的各记录已按关键字值的大小排列。

1.串行处理文件

1）串行处理文件

串行处理文件为顺序文件未按关键字排序。

2）查找搜索方法

顺序搜索,即从文件的第一个记录开始,依次将待查关键字值与文件中记录的关键字值进行比较,直到成功找到该记录,或者直到文件搜索完毕都未找到,搜索失败为止。

3）文件按记录被访问的频率

成功搜索一个记录的平均比较次数为:

S_n＝p₁＋2p₂＋…＋np_n

其中,查找关键字值为k_i的记录的概率为p_i,p₁≥p₂≥…≥p_n,p₁＋p₂＋…＋p_n＝1。S_n有最小值。

4）自组织文件

如果采用互换位置（transpose）的方法来组织文件。当在文件中成功查找到一个记录R_i后,便将R_i和其前面一个记录R_i－1互换位置。这样做同样可以得到最短的搜索时间。

2.顺序处理文件

1）顺序处理文件

顺序处理文件为顺序文件已按关键字排序。

2）查找搜索方法

有序表上的各种搜索方法原则上都可以用于顺序处理文件的搜索,如顺序搜索和二分搜索等。但是由于文件是外存上的数据结构,在考虑算法时,必须立足于尽量减少访问外存的次数,因此顺序处理文件的搜索算法有自己的特点。

下面以分块插值搜索为例介绍顺序文件的搜索方法。

设有顺序处理文件R₀,R₁,R₂,…,R_n－1,顺序存储在m个（物理）块中,如图10－1所示。并已知记录的关键字值为:K0,K1,K2,…,Kn－1。其中,K0是最小关键字值,Kn－1是最大关键字值。现要在该文件中搜索关键字值为K的记录。

图10－1　顺序存储文件

首先在m个块范围内决定被读入内存进行搜索的块号。第一次被读入内存的块号i按下式计算:

i＝1＋「（（K－K0）/（Kn－1－K0））·（m－1）?

设L_i和Hi分别是第i块的最小和最大关键字值,若L_i≤K≤Hi,则i即为所求的块,可在该块中去搜索待查关键字值K,如图10－2所示。若K＜L_i,则下次搜索的块号范围为[1,i－1],并且新的H将是L_i；若K＞Hi,则下一次被搜索的块号的范围为[i＋1,m],并且新的L将是Hi。

图10－2　分块插值搜索

一般情况下,设low和high分别是搜索范围内的最小块号和最大块号。L和H分别是该搜索范围内的最小关键字值和最大关键字值。则下一次读入内存的块号i为:

i＝low＋「（（K－L）/（H－L））·（high－low）?

若L_i≤K≤H_i,则i即为所求的块,可在该块中去搜索待查关键字值K；若K＜L_i,则下次搜索的块号范围为[low,i－1],并且新的H将是L_i；若K＞H_i,则下一次被搜索的块号的范围为[i＋1,high],并且新的L将是H_i。

分块插值搜索是一种比较高效的顺序处理文件的搜索方法。尤其当文件中的关键字值分布比较均匀时,则会更有效,常常一次或两次访问外存的操作即可命中。

10.2.2　索引文件

索引文件由主文件和索引表构成。主文件是指文件本身（也称数据区）。索引表是在文件本身之外建立的一张表,它指明逻辑记录和物理记录之间的一一对应关系。索引表由若干索引项组成,是关键字值和指针的偶对的集合。一般情况下,索引项由主关键字和该关键字所在记录的物理地址组成。索引表必须按主关键字有序,而主文件则可以按主关键字有序或无序。索引表是由系统程序自动生成的。

主文件按主关键字有序的文件称索引顺序文件,如果数据文件是顺序处理文件,则可对一组记录建立一个索引项,组成索引表。这时,每个索引项的关键字值是该组记录中的最大关键字值,而指针指向存放该组记录的块的起始地址。这种索引称为稀疏（非稠密）索引。

索引顺序文件的主文件是有序的,适合于随机存取、顺序存取。最常用的索引顺序文件有ISAM文件和VSAM文件。

主文件按主关键字无序的文件称索引非顺序文件,通常将索引非顺序文件简称为索引文件。如果索引非顺序文件是串行处理文件,则必须对每个记录建立一个索引项,组成索引表,这种索引称为稠密索引。因为索引非顺序文件主文件无序,顺序存取将会频繁地引起磁头移动,所以适合于随机存取,不适于顺序存取。

索引文件的检索操作分两步进行:①将外存上含有索引区的页块送入内存,查找所需记录的物理地址；②将含有该记录的页块送入内存。故在索引表不大时,索引表可一次读入内存。在索引文件中检索只需进行两次外存访问:一次是读索引,另一次是读记录。由于索引表有序,对索引表的查找可使用顺序查找或二分查找等方法。

10.2.3　散列文件

散列文件是利用散列存储方式组织的文件,又称为直接存取文件,即根据文件中关键字的特点,设计一个散列函数和处理冲突的方法,将记录散列到存储设备上。其特点是:由记录的关键字“直接”得到记录在外存上的映象地址。类似于散列表的构造方法,根据文件中关键字的特点设计一种“散列函数”和“处理冲突的方法”将记录散列到外存储设备上。

由于记录在外存上是成组存放的,因此允许多个记录映象到同一个地址上,称外存储器中用于存放多个记录的“数据块”为“桶”（bucket）。因此,由哈希函数得到的映象地址为“桶地址”。桶是散列文件的基本存储单位,假如一个桶能存放m个记录,则当桶中已有m个同义词的记录时,存放第m＋1个同义词会发生“溢出”。需要将第m＋1个同义词存放到另一个桶中,通常称此桶为“溢出桶”。相应地,称前m个同义词存放的桶为“基桶”。

注意:（1）溢出桶和基桶大小相同,相互之间用指针相链接。

（2）当在基桶中没有找到待查记录时,就沿着指针到所指溢出桶中进行查找。因此,希望同一散列地址的溢出桶和基桶,在磁盘上的物理位置不要相距太远,最好在同一柱面上。

【例10－1】　某一文件有16个记录,其关键字分别为:23,05,26,01,18,02,27,12,07,09,04,19,06,16,33,24。桶的容量m＝3,桶数b＝7。用除余法作散列函数h（k）＝k%7。由此得到的散列文件如图10－3所示。

图10－3　散列文件

散列文件的操作包括检索、插入、删除等。检索只能进行按关键字进行查找,不能进行顺序查找。检索时,先在基桶内进行查找,若不存在,则再到溢出桶中进行查找。当查找不成功时,可将其插在最后一个桶（基桶或溢出桶）中；若该桶已装满,则在该桶后新增加一个溢出桶,将新记录插入该新桶中。删除时仅需对被删除的记录作删除标记即可,当被删除的记录不在最后一个桶中时,将最后一个桶中的记录移到存放被删除记录的位置。当经过多次插入和删除后可能会造成基桶或较前面的溢出桶内多数记录已被删除,而后面的桶则较满的不合理的文件结构的情况,此时需重新组织文件。