文件的逻辑与物理结构

一早赶过来写这个篇幅，其实是很恼火的，昨天夜里写了90%时，不知是不是太累的原因，竟然按错键，白忙了半个小时。哎，算了，言归正传，听着westlife歌，让我心情没有昨晚那么郁闷了。

其实这几天都在看内核的东西，这一块以前也就是SS, 一直认为比较简单，但是现在回过头来，以前只能算是被侵夺性记忆，并没有深入理解，特别是一起基础概念。文件的逻辑与物理结构。首先看第一个，这是理解后一个概念的关键。摸机子的人都知道，文件按其逻辑结构可以分为：有结构的文件，这是由若干个记录所构成的，又称为记录式文件；无结构文件，这是直接由字符序列所构成的文件，故又称为流式文件，但是流式文件是记录式文件的特例，即其每个记录中只含有一个字符。所以对于文件，以下只看成有结构的，即由记录构成的。那么现在，我们上升一个层次，什么是文件的逻辑结构？从哲学的角度说逻辑结构，其实说穿了就是相互之间的关系，那对于文件的逻辑结构就是记录之间的相互关系。再上升一个层次就是每个记录在文件中的位置。我们也笼统的称之为顺序，那么如果你要写一个文件，一定有个潜意识的排列顺序（对于记录文件，就是第一个记录是什么，第二个记录是什么，…；对于流式文件也一定有个字符序，总之这样才能有意义），那么这个排列顺序就是逻辑结构。这些顺序是怎么确定的，一般有顺序与索引两种，由这两种方式来决定记录在文件中的位置。逻辑文件的形式主要有：

1) 顺序文件，其记录是按某种顺序排列所形成的，记录在文件中的位置由某种顺序决定，第一个位置上的记录，第二个位置上的记录，…，由某种顺序来决定记录在文件中的位置。

2) 索引文件，记录在文件中的位置由索引表来指向，其实是按某个记录键来确定位置的，即第一个位置的记录在哪，第二个位置的记录在哪....。由索引表来决定这些位置上都是哪些记录。

3) 索引顺序文件，上述的两种相结合，将顺序文件中的记录先分为组，为顺序文件建立一张索引表，在索引表里为每组中的第一个记录建立索引项，记录在文件中的位置由索引表和顺序来决定。

以上这些逻辑的组织方式，都形成一个文件，这个文件是具有一定的逻辑结构的，即每个记录在文件中都有其自己的位置。现在，在您的脑中就存在一个文件，这个文件是从用户的视角来看的，它具有一定的逻辑结构，不管这些记录的位置是怎么确定的(顺序也罢，索引表来指向也罢)，但是，它们在文件中的位置现在是确定的，同时也不管这些记录在磁盘里是怎么存储的。那它就是一个具有了逻辑结构的文件，看成一个客观存在就是了。对，有了这个概念对于我们理解物理结构大有帮助。

现在看看文件的物理结构，是指文件在物理存储上的结构。在此之前您的脑有要有二个概念：一是，现在存在一个具有了具体逻辑结构的文件，即这个文件中的记录的位置是确定的，也就是对此文件，在逻辑上有了第一位置上是什么记录，第二个位置上是什么记录，…。二是，物理结构是为逻辑结构服务的，从用户的角度看这个文件的逻辑的结构是这个样子的，这只是个虚拟中的概念，但是任何虚拟最终都要实体来体现，怎么存储来体现文件的记录之间的位置关系呢，对，这就是物理结构。它是为体现逻辑结构服务的。逻辑文件+外存分配方式－＞物理文件。

1）  连续分配　要求为每个文件分配一组相邻的盘块。这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性，为使系统能找到文件存放的地址，应在目录项的文件物理地址字段中，记录该文件第一个记录所在的号和文件长度，逻辑结构的文件最终要在物理上体现出来，即物理上如何体现文件的逻辑结构。这种盘块的相邻关系，体现了逻辑上的相邻位置关系。优点：顺序访问容易，顺序访问速度快；缺点：要求有连续的存储空间，必须事先知道文件的长度，易造成碎片。

2）  链接分配　文件的逻辑结构可以通过链接指针体现，逻辑上相邻的位置关系，通过物理上的上下块之间的指针来体现相邻位置关系。可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，由此形成的物理文件称为链接文件。可显著消除了外部碎片，故可提高外在空间的利用率，且无须知道文件的长度，根据文件的当前需要，为它分配必需的盘块。当文件动态增长时，可动态地再为它分配盘块，此外，对文件的增、删、改也十分方便。可分为隐式链接和显式链接。注：外存的空间，是按一定大小划分成盘块的，是盘块的集合。

　　隐式链接：在采用隐式链接分配方式时，在文件的目录的每个目录项中，都须集中指向链接文件第一个盘块和最后一个盘块的指针，而每个盘块中都含有一个指向下一个盘块的指针。最主要的问题是：它只适合于顺序访问，对随机访问是极其低效的，如果其中的一个指针出现问题，都会导致整个链的断开，为了提高检索和减小指针所占用的存储空间，可以将同一磁道即柱面上相邻几个盘块组成一个簇cluster，在分配盘块时，以簇为单位进行。

　　显式链接：这是指把用于链接文件各个物理块的指针，显式地存放在内存的一张链接表中，这张表体现了文件的逻辑结构。这个表只能体现上下块之间的关系，没有第几个位置的指向。该表是整个磁盘仅设置的一张表，分配给文件的所有盘块号都放在该表中，称为文件分配表FAT，是磁盘上所有文件的链接表，表的序号是物理盘块号，因为磁盘分成了盘块，从0开始一直到N-1，每个表项中，存放链接指针即为盘块号，即下一个盘块号，凡是属于某一文件的第一个盘块号，均作为文件地址被填入相应文件的FCB的物理地址字段中。查询记录的过程是在内存中进行的，所以显著地提高了检索速度。注，对于外存，链接指针即地址是盘块号。但是不能支持高效的直接存取，同时FAT也需要占用较大的内存空间。

3）  索引分配  文件的逻辑结构体现在索引表中，这个索引表不同于文件逻辑结构中的索引表，逻辑结构中的索引是索引记录键相关的东西，而讲到物理结构时，是假设其逻辑结构已经存在，即文件的上下相邻位置关系已经存在，所以在物理上要怎么体现这种上下相邻关系。将逻辑上的相邻位置关系在物理上体现出来：即哪些块在逻辑上是相邻的，所以按文件的逻辑顺序建立了物理文件盘块的索引表，这些文件的逻辑关系体现在索引表中，即在逻辑上或是按逻辑的顺序由哪些块构成的，总之是按逻辑顺序排序的盘块号集合，即第一个位置的记录在哪，第二个位置的记录在哪，…。对于索引分配一般有：

　　单级索引分配　事实上，在打开文件时，只须把该文件占用的盘块的编号调入内存即可，完全没有必要将整个FAT表调入内存，将每个文件所对应的盘块号集中地存放在一起，为每个文件分配一个索引块表，把分配给该文件的的有盘块号，都记录在该索引块中，因而该索引就是一个含有许多盘块号的数组。在建立一个文件时，便须在为之建立的目录项中，填上指向该索引块的指针。这种分配方式支持直接访问，当要读文件的第I个盘块时，可以方便地直接从索引块中找到第I块盘的盘块号。同时也不会产生外部碎片。

其实索引的方法就是将链接的方式（只有下一个是什么的概念，没有第几个是什么的概念，所以不能直接读取）顺序文本化，即逻辑位置关系（第1，第2，第3，…）体现在索引表中，而不是指针。但是问题是可能会花费较多的外在空间，当建立一个文件时，要为之分配一个索引块，将分配给文件的盘块号记录在其中，即要文本化这种逻辑关系。

多级索引分配　当文件过大时，已经装满一索引块时，OS便为之再分配一个索引块，用于以后继续为之分配的盘块号记录，依此类推要建立这些索引块的索引，将各索引块按序组织起来。

混合方式分配　将直接地址，一级索引，…，多级索引集合在一起，以适应不同文件大小的需要。其实直接地址部分就是相当于索引块本身，适合于小文件的分配。而一级索引是指向的是索引块。

总之，当你有了一个逻辑上的文件后，机器为这个文件分配磁盘，并将其存入磁盘，这种分配方式，要保证从磁盘上将文件读出来后，仍能保证逻辑上的一致性。这就是说文件在外存上存储时，分配方式要保证文件在逻辑上一致。所以物理结构就是指逻辑文件在这些分配方式下所形成的文件结构。