文件的逻辑结构及索引文件结构

文件是信息的集合，文件的结构是指文件中信息的构造和组织形式。文件的逻辑结构是指从用户应用文件的角度出发，研究文件中的信息组织形式。这种文件的信息组织形式独立于文件在物理存储器上的存放形式，即文件的逻辑结构独立于文件的物理结构。在本质上，文件的逻辑结构存在两种形式：字节流形式和记录形式。

7.2.1 文件逻辑结构的形式

1.字节流形式

字节流文件是指文件中的信息以字节组合在一起，这种形式的文件称为无结构文件或流文件。在文件中分界，通常会按照字节个数读取信息，或插入特殊字符作为分界而读取信息。

对于流式文件，用户按照字节来读取所需要的信息。事实上，流式文件为操作系统文件管理提供了极大的灵活性，操作系统接受的文件由字节组成，文件中的信息组织不需要操作系统解释，只需要用户解释。因此，用户可以不受束缚地灵活组织文件内部结构。

2.记录形式

记录式文件是有结构的文件，它包含若干逻辑记录，每个逻辑记录是文件中按信息在逻辑上的独立含义划分的一个信息单位。各记录有着相同或不同数目的数据项。记录的长度可分为定长和不定长两类。

（1）定长记录。这是指文件中所有记录的长度都是相同的，所有记录中的各数据项都处在记录中相同的位置，具有相同的顺序和长度。文件的长度用记录数目表示。对定长记录的处理方便、开销小，所以这是目前较常用的一种记录格式，被广泛用于数据处理中。

（2）变长记录。这是指文件中各记录的长度不相同。产生变长记录的原因可能是由于一个记录中所包含的数据项数目并不相同，如书的著作者、论文中的关键词等，也可能是数据项本身的长度不定，例如病历记录中的病因、病史，科技情报记录中的摘要等。

从操作系统管理的角度来看，逻辑记录是文件内独立的最小信息单位，但从用户使用程序设计语言处理信息的角度来看，还可以把逻辑记录进一步划分成一个或多个更小的数据项。数据项是具有标识名的最小的不可分割的数据单位，数据项的集合构成逻辑记录，相关逻辑记录的集合构成了文件。以一个单位的工资文件为例，工资信息逻辑文件中有若干逻辑记录，每一个逻辑记录表示一个职工的工资信息，其中每个记录中的职工编号、姓名、应发工资、扣除工资等都是独立的数据项，当然，扣除工资数据项还可进一步划分为扣除房租、扣除水电费等，水电费又可进一步划分为水费、电费等更低层次的数据项。

根据用户和系统管理上的需要，可按照记录的排列方式不同，形成下述的几种文件：

（1）顺序文件。这是由一系列记录按某种顺序排列所形成的文件。其中的记录通常是定长记录，因而能用较快的速度查找文件中的记录。

（2）索引文件。当记录为可变长度时，通常为之建立一张索引表，并为每个记录设置一个表项，以加快对记录检索的速度。

（3）索引顺序文件。这是上述两种文件构成方式的结合。它为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。

7.2.2 文件逻辑结构的类型

从用户使用观点来看，他们关心的是数据的逻辑结构，即记录及其逻辑关系。文件中的记录可以按照不同的顺序进行排列。根据排列方式的不同，可归纳为以下几种逻辑结构。

1.连续文件

文件按照记录生成的时间顺序连续排列。因此记录的顺序是由存入记录的时间决定的，与记录的内容无关。对于某些应用，如日志文件和各种现场记录文件等，为了按照事件发生的时间查询和使用方便，常常需要根据生成记录的时间顺序组织文件，因此连续结构形式的文件能够满足这样的要求。

连续文件的优点是记录的增加和修改都比较方便，缺点是不易于文件内容的搜索。

2.顺序文件

顺序文件的记录按照一定的顺序规则排列，顺序规则由关键字决定。例如一些人员管理数据文件或学生管理列表文件，需要按照员工号或学号排列所有的记录，员工号或学号就是记录的关键字，文件中的所有记录都按照员工号或学号的顺序进行组织。

顺序文件的最佳应用场合是在对诸记录进行批量存取时，即每次要读或写一大批记录时。在交互应用的场合，如果用户（程序）要求查找或修改单个记录，为此系统便要去逐个查找诸记录。这时，顺序文件所表现出来的性能就可能很差，尤其是当文件较大时，情况更为严重。例如，有一个含有104个定长记录的顺序文件，如果对它采用顺序查找法去查找一个指定的记录，则平均需要查找5×103个记录，查找开销比较大。(www.xing528.com)

顺序文件的优点是关键字可以作为检索记录的索引，检索记录快。缺点是增加和修改记录后需要重新组织记录的顺序和关键字。

3.索引文件

对于定长记录文件，如果要查找第i个记录，可直接根据下式计算来获得第i个记录相对于第一个记录首址的地址：

然而，对于可变长度记录的文件，要查找其第i个记录时，须首先计算出该记录的首地址。为此，须顺序地查找每个记录，从中获得相应记录的长度Li，然后才能按下式计算出第i个记录的首址。假定在每个记录前用一个字节指明该记录的长度，则

可见对于定长记录，除了可以方便地实现顺序存取外，还可较方便地实现直接存取。然而对于变长记录就较难实现直接存取了，因为用直接存取的方法来访问变长记录文件中的一个记录是十分低效的，其检索时间也很难令人接受。为解决这个问题，可采用索引文件结构。对文件建立一个索引表，文件中的每一条记录在索引表中都有相应的表项。索引表中有每条记录的指针，通过指针可以在文件中找到每条记录。如果文件是变长记录文件，则在索引表中通常还会有每条记录的长度，如图7-2所示。

图7-2 索引文件的组织

在对索引文件进行检索时，首先是根据用户（程序）提供的关键字，并利用折半查找法去检索索引表，从中找到相应的表项；再利用该表项中给出的指向记录的指针值，去访问所需的记录。而每当要向索引文件中增加一个新记录时，便须对索引表进行修改。由于索引文件可有较快的检索速度，故它主要用于对信息处理的及时性要求较高的场合，例如飞机订票系统。

索引文件的优点是通过索引查找文件记录非常快，文件记录的插入和修改方便。缺点是需要建立索引表，插入和删除记录需要在索引表中增加相应表项和删除相应表项。

4.索引顺序文件

索引顺序文件结合了顺序文件和索引文件的优点，将顺序文件中的多个记录组合成一组，并对每一组记录建立一个索引，通过索引指针找到记录组中的第一条记录，如图7-3所示。

图7-3 索引顺序文件的组织

在对索引顺序文件进行检索时，首先利用用户（程序）所提供的关键字以及某种查找算法去检索索引表，找到该记录所在记录组中第一个记录的表项，从中得到该记录组第一个记录在主文件中的位置；然后再利用顺序查找法去查找主文件，从中找到所要求的记录。

索引顺序文件有如下两个优点：

（1）克服了单纯采用索引文件需要建立的索引表非常大、占用很大空间的缺点。

（2）克服了单纯采用顺序文件，需要在大量的记录中按照关键字查询记录、花费时间很长的缺点。

因此，在文件记录非常多的情况下，采用索引顺序文件比较适合。