呈现在用户面前的文件是逻辑文件，其组织方式是文件的逻辑结构。逻辑文件总要按照一定的方法保存在外存上，它在外存上具体的存储和组织形式称为文件的物理结构，而这时的文件则称为物理文件。物理文件的实现，归根结底就是能够把文件的内容存放在外存的合适地方，并且在需要时能够很容易地读出文件中的数据。物理文件的实现需要解决以下三个问题。
（1）给文件分配外存空间。
（2）记住文件在外存空间的存储位置。
（3）将文件内容存放在属于该文件的外存空间里。
给文件分配外存空间就是要按照用户要求或文件大小，给文件分配适当容量的外存空间。记住文件在外存空间的位置，对以后文件的访问至关重要。而将文件内容存放在属于该文件的外存空间里，则可通过相应的外存设备驱动器来实现。实现上述三点均需要了解文件在外存上的存放方式，即文件的物理结构。
文件在磁盘上的存放方式（文件的物理结构）就像程序在内存中存放方式那样有以下两种。
（1）连续空间存放方式（连续结构）。
（2）非连续空间存放方式。
其中，非连续空间存放又可以分为链表方式（链表结构）和索引方式（索引结构）两种。
1.连续结构
连续结构也称顺序结构，是一种最简单的物理文件结构，其特点是逻辑上连续的文件信息，依次存放在物理上相邻的若干物理块中。具有连续结构的文件称为连续文件（或顺序文件）。
磁带上的文件只能采用顺序结构。每个磁带文件包括文件头标、文件信息、文件尾标三部分：①文件头标包含文件名、文件的物理块数、物理块长度等文件属性并标志文件由此开始；②文件尾标标志文件到此结束；③文件信息位于文件头标和文件尾标之间。要访问磁带上的某个文件，必须从第一个文件开始查找，即首先读出第一个文件的头标进行文件名比较。若不是用户要访问的文件，则磁头前进到下一个文件的头标处继续进行文件名的比较，直到找到用户指定的文件为止，找到指定的文件后就可以进行文件的读写操作。
磁盘上的连续文件存储在一组相邻的物理块中，这组物理块的地址构成了磁盘上的一段线性地址。例如，若文件第一个物理块的地址为a，则第二个物理块的地址为a+1，第三个物理块的地址为a+2，以此类推，连续文件的所有物理块总是位于同一个磁道或同一柱面上，如仍然放不下，则存储在相邻磁道或相邻柱面上，因此存取同一个文件中的信息，不需要移动磁头或仅需磁头移动很短的距离。为了确定连续文件在磁盘上的存放位置，需要将该文件第一个物理块号及文件长度（物理块个数）等信息记录在文件目录中该文件所对应的目录项里。
连续文件的优点是顺序访问容易。连续文件的最佳应用场合是对文件的多个记录进行批量存取时，即每次要读写一大批记录，这时连续文件的存取效率是所有逻辑文件中最高的。若要对连续文件进行顺序访问，只需从目录中找到该文件的第一个物理块，就可以逐个物理块地依次向下进行访问。连续文件存储空间的连续分配特点也支持直接访问（随机访问），若需要存取文件（设起始物理块号为a）的第i号物理块内容，则可通过直接存取a+i号物理块来实现。此外，也只有连续文件才能存储在磁带上并有效地工作。
连续文件的缺点主要体现在以下4个方面。
（1）在交互应用场合，如果用户要求查找或修改文件中未知序号的某个记录，则系统只能按顺序依次查找连续文件中的相邻记录，直到找到所需记录为止，这时连续文件所表现出来的性能可能就很差，尤其是当文件较大时情况就更严重。如果是变长记录的连续文件，则为查找一个记录所需付出的开销将更大。
（2）为文件分配连续的存储空间容易出现外存碎片（随着文件存储空间的不断分配和回收，将导致磁盘上出现一些再也无法分配的小存储区，如仅有一两个物理块的存储区）。大量外存碎片的出现会严重降低外存空间的利用率，若定期利用紧凑技术来消除外存碎片，则要花费大量的CPU时间。
（3）要为文件分配连续存储空间，必须事先知道文件的长度，而许多情况下却难以事先知道文件的长度。如创建一个新文件时只能估计文件的大小，于是可能出现下述结果：①估计结果小于实际文件需要的大小，致使文件进一步操作无法继续；②估计结果远大于实际文件的长度，导致严重的外存空间浪费。
（4）增加或删除一个记录比较困难。在增加或删除记录后，需要调整文件中所有记录的存储位置来保持文件连续存储的特性。为了解决这一问题，可以为连续文件配置一个运行记录文件或称事务文件。需要对文件实施增加、删除或修改记录的操作时，并不立即对文件实施这些操作，而是将该操作的信息登记到运行记录文件中。每隔一定时间，系统则按照运行记录文件所记录的一系列操作对该文件实施这些操作，即将分散的各个操作集中起来，进行一次性处理，以此来提高处理的效率。
2.链接结构
为了克服连续文件增加或删除记录比较困难且容易产生外存碎片的缺点，可以采用离散方式为文件分配外存空间。链接结构也称串联结构，它就是为了实现文件离散分配磁盘物理块而产生的一种文件物理结构。采用链接结构，文件的信息可以保存在磁盘的若干相邻或不相邻的物理块中，每个物理块中设置一个指针指向逻辑顺序的下一个物理块，从而使同一个文件中的各物理块按逻辑顺序链接起来。具有链接结构的物理文件称为链接文件或串联文件。
由于链接文件采用离散分配方式，从而消除了外存碎片，所以可显著提高外存（磁盘）空间的利用率。此外，链接文件不需要事先知道文件的大小，而是根据文件当前需求的大小来分配磁盘物理块。随着文件的动态增长，当文件需要新的物理块时再动态地为其追加分配，因此便于文件的增长和扩充；不需要文件中某物理块时，也可从该文件的物理块链中删除。链接文件可以动态分配物理块的特点决定了在这类文件中能够方便地进行插入、删除和修改操作。链接文件的缺点是只适合顺序访问而不能直接访问（随机访问），并且因每个物理块中的链接指针都要占一定的存储空间而导致存储效率降低。
根据链接方式的不同，链接结构又可以分为隐式链接结构和显式链接结构两种。
（1）隐式链接结构
采用隐式链接结构时，文件的每个物理块中有一个指针指向该文件中逻辑顺序的下一个物理块，即通过每个物理块中的指针将属于同一个文件的所有物理块链接成一个链表，并且将指向文件第一个物理块的指针保存到该文件的目录项中。
隐式链接文件的主要问题是只适合顺序访问，直接访问的效率很低。例如，若要访问文件的某个物理块，则必须先从它的第一个物理块起，沿着指针一个物理块接着一个物理块进行查找，直至找到所要访问的物理块为止，通常这种查找需要花费较多的时间。另外，仅通过链接指针将大量离散的物理块链接起来可靠性较差，一个指针出现了问题就会导致整个物理块链断开。(www.xing528.com)
为了提高文件的检索速度和减少指针占用的存储空间，可以将相邻的几个物理块组成一个单位——簇，然后以簇为单位来分配磁盘空间。这样做的好处是成倍地减少了查找指定物理块的时间，同时也减少了指针占用的存储空间。不足之处是以簇为单位分配磁盘空间会使外存碎片增多。
（2）显式链接结构
隐式链接文件的缺点是访问速度慢，尤其是直接访问，需要从文件的第一个物理块一个指针一个指针地找下去，若有任何一个指针损坏，则无法恢复整个文件（连续文件则不存在这个问题）。此外，一个物理块的大小总是2的整数幂，这是因为计算机里2的整数幂比较容易处理。但隐式链接文件使用物理块中的一部分空间来存放指针，使得物理块里存放数据的空间不再是2的整数幂，这将造成数据处理的效率下降。此外，读取数据时要将指针从物理块中分离出来，这也影响数据处理的效率。
解决的方法是将所有的指针从物理块里分离出来集中存放在一张表中，这样，要想知道任意一个物理块的存储地址，只需要查找该表即可。并且该表可以存放在内存中，这既解决了物理块中的数据不是2的整数幂的问题，又解决了直接访问速度慢的问题。
显示链接结构就是按上述方法将用于链接文件各物理块的指针，显式地存放在内存中的一张链接表中，称为文件分配表（FAT）。文件分配表的设置方式是将整个磁盘配置一张FAT，该磁盘的每个物理块各对应一个FAT表项，因此FAT的项数与磁盘的物理块数相同。FAT的表项从0开始编号，直至n-1（n为磁盘的物理块总数）。每个FAT表项存放一个链接指针，用于指向同一文件中逻辑顺序的下一个物理块，利用链接指针将属于同一个文件的所有FAT表项链接成一个链表，并且将该链表的头指针（即文件第一个物理块号）保存到该文件的目录项中。
显示链接结构由于使用了FAT保存磁盘中所有文件物理块之间的关联信息，因此可以按照以下方式存取文件的某个物理块：将FAT读入内存并在FAT中进行查找，待找到需要访问的物理块号后，再将该物理块的信息读入内存进行存取操作。由于整个查找操作在内存中进行，与隐式链接结构相比不仅提高了查找速度，而且大大减少了访问磁盘的次数。DOS和Windows操作系统的文件就采用了显示链接结构。
采用显示链接结构存在以下两个问题。
（1）直接（随机）存取的效率不高。这是因为当需要对一个大文件进行直接存取时，首先从文件目录项中该文件的第一个物理块号开始查找FAT，即以顺序查找的方式在内存的FAT中找到需要存取的物理块号，虽然查找是在内存中进行，但这种顺序查找也可能花费较多的时间。
（2）由于整个磁盘配置一张FAT，而为了查找文件的物理块号就必须先将这个FAT读入内存，则当磁盘容量较大时这个FAT也会占用较多的内存空间。
3.索引结构
FAT虽然有效但占用内存较多，因为FAT记录了整个磁盘的所有物理块号，但如果系统中的文件数量较小，或者每个文件都不太大，那么FAT中将有很多未为文件使用的空表项，这样将整个FAT都放入内存显然没有必要。如果能将一个文件占用的所有物理块磁盘地址收集起来，集中放在一个索引物理块中，而在文件打开时将这个索引物理块加载到内存，这样就可以从内存索引物理块中获得文件的任何一个物理块磁盘地址。由于内存中存放的只是我们当前使用文件索引物理块，而不使用那些文件的索引物理块仍在磁盘上，因此，显示链接结构中FAT占用内存太多的问题就解决了，这种索引物理块的方式就是索引结构。
索引结构的组织方式：文件中的所有物理块都可以离散地存放于磁盘中，系统为每个文件建立一张索引表，用于按逻辑顺序存放该文件占用的所有物理块号。索引表或者保存在文件的目录项（即文件控制块FCB）中，或者保存在一个专门分配的物理块（索引物理块）中，这时文件目录中只含有指向索引物理块的指针（即索引物理块的块号）。具有索引结构的文件称为索引文件。
索引结构除具备链接结构所有的优点外，还克服了链接结构的缺点，既支持顺序访问又支持直接访问，当要访问文件的第i个物理块时，可以从该文件的索引表中直接找到第i个逻辑块对应的物理块号（有点像内存管理中的页表）。此外，文件采用索引结构查找效率高，便于文件进行增加或删除记录的操作，而且也不会产生外存碎片。
索引结构的主要缺点是外存空间浪费比较大，这是因为索引表本身占用空间的浪费可能较大。例如，如果每个文件使用一个专门的物理块（索引物理块）来存放索引表，则全部文件的索引表可能占用几百个，甚至上千个物理块。但一般情况下，文件以中、小型居多，甚至不少文件只需1～2个物理块来存放数据，于是索引表中的大量空间被浪费了。
注意：如果索引表不调入内存，则存取文件时首先要获取存放于外存的索引表（索引物理块）信息，所以要增加一次访盘操作，从而降低了文件访问的速度。因此系统采取的方法是在文件存取前先把存放于外存的索引表（索引物理块）调入内存，这样在以后的文件访问中就可以直接查询内存中的索引表了。
与链接结构相比，当文件比较大时索引结构要优于链接结构；但对于小文件，索引结构则比链接结构浪费存储空间。
当文件很大时，文件的索引表也会很大。如果索引表的大小超过了一个物理块，可以将索引表本身作为一个文件，再为其建立一个索引表，这个索引表作为文件索引的索引，从而构成了二级索引。第一级索引的表项指向第二级索引，第二级索引表的表项指向相应信息所在的物理块号。以此类推，可以再逐级建立索引，进而构成多级索引。在实际应用中，可以将多种索引结构组织在一起，形成混合索引结构。UNIX和Linux操作系统中的文件物理结构就采用了混合索引结构。
如果磁盘的物理块大小为4KB，每个物理块号占4B，则一个索引块可以存放1024个物理块号，于是采用两级索引结构时，文件全部索引块最多可以存放的物理块号总量为1024×1024=1M；采用三级索引结构时，文件全部索引块最多可以存放的物理块号总量为1024×1024×1024=1G。由此可以得出结论：采用单级索引时，所允许的文件最大长度是4KB×1024=4MB；采用两级索引时，所允许的文件最大长度是4KB×1M=4GB；采用三级索引时，所允许的文件最大长度是4KB×1G=4TB。
4.散列结构
链接文件很容易把物理块组织起来，但是查找某个记录则需要遍历文件的整个物理块链表，使得查找效率较低。为了实现文件的快速存取，目前应用最广的是一种散列结构，散列结构是针对记录式文件存储在直接（随机）存取设备上的一种物理结构。采用该结构时，记录的关键字与记录存储的物理位置之间通过散列（Hash）函数建立起某种对应关系，换言之，记录的关键字决定了记录存放的物理位置。具有散列结构的文件称为直接文件、散列文件或Hash文件。
为了实现文件存储空间的动态分配，直接文件通常并不使用散列函数将记录直接散列到相应的物理块号上，而是设置一个目录表，目录表的表项中保存了记录所存储的物理块号，而记录关键字的散列函数值则是该目录表中相应表项的索引号，如图7-2所示。
图7-2 直接文件的物理结构示意图
直接文件设计的关键是散列函数的选取，以及怎样解决“冲突”问题。一般来说，记录的存储地址与记录的关键字之间不存在一一对应的关系，不同的关键字可能有相同的散列函数值，即不同的关键字可能散列到相同的地址上，这种现象称为“冲突”。一个好的散列函数应将记录均匀地散列到所有地址上且冲突尽可能少，如果出现冲突也应该有好的解决办法。直接文件的文件目录项中应包含指向散列函数的指针，这是因为存取该文件的某个记录时，需要使用这个散列函数计算该记录存储的物理地址。
直接文件的优点是存取速度快，节省存储空间；缺点是不能进行顺序存取，只能按关键字直接存取。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
