文件的物理结构研究的是 已分配给文件的磁盘块在磁盘中如何组织起来的，分为连续分配、链式分配和索引分配3种。

其中链接分配采取离散分配的方式。分为隐式链接和显式链接两种。

逻辑上无结构的文件（如二进制流文件或字节流文件）在物理上也是有结构的，也会遵循这3种物理结构中的一种。

类似于内存分页，磁盘中的存储单元也会被分为一个个物理块。很多操作系统中，磁盘块的大小与内存块、页面的大小相同（例如内存块如果一个块大小是1K，那么磁盘块的大小也会为1K或者1K的倍数）。为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。

和内存地址类似，文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。每个文件的逻辑块号从0开始。

文件打开和关闭

打开操作调用了open系统调用，它会根据传入的文件路径找到文件的iNode节点地址，把iNode节点的内容从磁盘读入内存，并将文件的描述信息作为一个表项添加到“打开文件表”的末尾，并将文件标识符返回给用户，用户根据这个标识符可以直接在内存的打开文件表中查到文件的FCB信息，不用再通过磁盘IO去从目录文件中查。

关闭文件就是回收文件的磁盘空间并从打开文件表中删除这个表项。

接下来介绍物理块的分配方式，我们需要关注这几个问题：每种分配方式如何实现逻辑块号到物理块号的映射，根据一个逻辑块号读取一个物理块需要的IO次数是多少，当文件块数增加时是否方便扩展文件（即文件的修改和追加内容）。

一、连续分配

连续分配方式要求每个文件在磁盘上占有一组连续的块。目录文件中要记录每个文件 的起始物理块号和长度 （总共占用几个块）。

已知一个文件打开后，它的FCB信息如文件名、起始块号和长度就在内存中有了，根据文件标识就能获取这些信息。

Q1： 如何实现文件的逻辑块号到物 理块号的转变？

如果用户想读取逻辑块号i。那么 目标数据的 物理块号 = 起始物理块号 + 逻辑块号。

当然，还需要检查用户提供的逻辑块号 是否合法（逻辑块号 ≥ 长度 就不合法）。

Q2：读取一个物理块需要的IO次数是多少？

连续分配支持随机访问第i号逻辑块，所以根据一个逻辑块号访问一个块的IO次数是1次。

连续分配的优点：

从磁盘的物理特性来说，读取某个磁盘块时，需要移动磁头到这个磁盘块的开始位置。访问的两个磁 盘块相隔越远，移动磁头所需时间就越长。因此连续分配的文件在顺序读取多个逻辑上连续块的情况下速度最快。

连续分配的缺点：

物理上连续分 配的文件A占用 了连续的三个 块。若此时文件A要拓展多一个磁盘块（总共 需要连续的4个磁盘块）。 由于采用连续结构， 因此只能将文件A全部“迁 移”到有4个连续空闲块的绿色区域，开销很大。

此外连续分配无法充分利用磁盘碎片，也容易产生磁盘碎片，因此磁盘利用率高。可以用紧凑技术（将已使用的磁盘空间集中在一边，将未使用的块集中在另一边，把小的空闲磁盘碎片连成一片大的空闲空间）来处理碎片，但 是需要耗费很大的时间代价。

总结：

连续分配的优点：支持随机访问；连续分配的文件在顺序访问多个块时速度最快。

连续分配的缺点：不方便文件拓展；存储空间利用率低，容易产生磁盘碎片。

读取一个逻辑块的IO次数：1次。

二、链接分配之隐式链接

特点：

文件块按照链式存储，每个块离散存储，且记录下一个块的指针（物理地址）。FCB中记录了文件 存放的起始物理块号和 结束物理块号。

Q1： 如何实现文件的逻辑块号到物 理块号的转变？

如果要读取 i 号逻辑块，要将起始的9号物理块（0号逻辑块）读入内存，由此知道1号逻辑块存 放的物理块号2，于是读入2号物理块，再找 到2号逻辑块的存放位置……以此类推。

Q2：读取一个物理块需要的IO次数是多少？

读入i号逻辑块，总共需要 i+1 次磁盘 I/O。读取一个逻辑块的平均IO次数是 n/2。

Q3：扩展性如何？

若要拓展文件，则可以随便 找一个空闲磁盘块，挂到文件的 磁盘块链尾，并修改文件的FCB，不会有碎片问题， 外存利用率高。

隐式链接分配的优点：很方便文件拓展；不会有碎片问题故而外存利用率高。

隐式链接分配的缺点：只支持顺序访问不支持随机访问；查找效率低（因为平均IO次数高）；指向下一个盘块的指针也需要耗费少量 的存储空间。

读取一个逻辑块的IO次数：平均 n/2 次，n是文件的总盘块数。

三、链接分配之显式链接

特点：

文件块按照链式存储，每个块离散存储，但不记录下一个块的指针（物理地址）。所有物理块的下一个块物理地址统一存储在一个文件分配表 FAT 中。FCB中记录了文件 存放的起始物理块号。

一个磁盘仅设置一张FAT。 开机时，将FAT读入内存，并常驻 内存。FAT 的各个表项在物理上 连续存储，且每一个表项长度相 同，因此“物理块号”字段可以 是隐含的，不占空间的。

Q1： 如何实现文件的逻辑块号到物 理块号的转变？

若目标逻辑块号是 3，已知逻辑块0的物理块号是2，则查询内存中的FAT[2] = 5（逻辑块号1），再找 FAT[5] = 0（逻辑块号2），再找 FAT[0] = 1（逻辑块号3）。FAT表本质是一个数组，因此访问 FAT[k]的复杂度是O(1)。

Q2：读取一个物理块需要的IO次数是多少？

逻辑块号转换成物理块号的过 程不需要读磁盘操作。因此IO次数为1，就是直接读取目标物理块的那次IO操作。所以显式链接支持随机访问。

Q3：扩展性如何？

不会产生外部碎片，也可以很方便地对文件进行拓 展。

显式链接分配的优点：很方便文件拓展；不会有碎片问题，外存利用率高；支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。

显式链接分配的缺点：文件分配表的需要占用一定的存储空间（1T的磁盘，FAT表可能占几十到上百M，而且几百兆是要直接载入内存的，这点很糟糕）。

四、索引分配

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文 件的各个逻辑块对应的物理块（类似于内存管理中的页表——建立逻辑页面到物理页之间 的映射关系）。一个文件中的索引表占用的磁盘块称为索引块。文件数据占用的磁盘块称为数据块。

假设某个新创建的文件“aaa”的数 据依次存放在磁盘块 2 -> 5 -> 13 -> 9 。 7号磁盘块作为“aaa”的索引块， 索引块中保存了索引表的内容。

可以用固定的长度表示物理块号（如： 假设磁盘总容量为1TB=2^40B，磁盘块大 小为1KB，则共有 2^30个磁盘块，则可用 4B 表示磁盘块号），索引表中 的“逻辑块号可以是隐含的。

Q1： 如何实现文件的逻辑块号到物 理块号的转变？

用户给出要访问的逻辑块号 i。

首先根据索引块的起始物理块号将整个索引表 从外存读入内存（索引表可能占了多个索引块），查找 索引表[i] 得到 i 号 逻辑块的物理块号。

索引分配方式可以支持随机访问（无需从0号逻辑块查起）。

Q2: 扩展性如何？

文件拓展也很容易实现（只需要给文件分配 一个空闲块，并增加一个索引表项即可）。

但是索引表需要占用一定的存储空间。

Q3：如果一个文件的大小超过了256 块，那么一个磁盘块是装不下 文件的整张索引表的，如何解 决这个问题？

有3种解决方法：①链接方案； ②多层索引； ③混合索引

链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。

假设磁盘块大小为1KB，一个索引表 项占4B，则一个磁盘块只能存放256 个索引项。

若一个文件大小为 256*256KB = 65,536 KB = 64MB

该文件共有 256*256 个块，也就需要 256 个 索引块来存储，这些索引块用链接方 案连起来。

若想要访问文件的最后一个逻辑块， 就必须找到最后一个索引块（第256 个索引块），而各个索引块之间是用 指针链接起来的，因此必须先顺序地 从磁盘读入前 255 个索引块到内存中。一共要发生257次IO操作。

该索引方式的缺点是读取一个逻辑块会发生太多次磁盘IO。

多层索引：将索引表分层，使第一层索引块指向第二层的索引块。还可根据 文件大小的要求再建立第三层、第四层索引块。顶层索引表只占一个索引块，非底层的索引表表项记录指向的下一层索引表的开始地址，底层的索引表表项指向数据块地址。

我们可以理解为所有层级的索引表在逻辑上就是一个索引表。

假设磁盘块大小为1KB，一个索引表项占4B，则一个 磁盘块只能存放256 个索引项。

若某文件采用两层索引，则该文件的最大长度可以到 256*256*1KB = 65,536 KB = 64MB

可根据逻辑块号算出应该查找每一层索引表中的目标表项。

要访问 1026 号逻辑块，则 1026/256 = 4（要查询的底层索引表是第5个索引块），1026%256 = 2（数据逻辑块号在第五个索引块的第3个表项）

因此可以先将一级索引表调入内存，查询 4 号表项， 将其对应的二级索引表调入内存，再查询二级索引表 的2号表项即可知道 1026 号逻辑块存放的磁盘块号了。

访问目标数据块，需要3次磁盘I/O。

采用 K 层索引结构，且顶级索引表未调入 内存，则访问一个数据块只需要 K + 1 次 读磁盘操作。

该索引方式的缺点是一个只占几个块的小文件，对其读取一个逻辑块也要发生不只一次磁盘IO。

混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接 指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表） 。

如上图，假设顶级索引表没有读入内存。

访问0~7号逻辑块中的某一块，需要2次磁盘IO。

访问8~263号逻辑块中的某一块，需要3次磁盘IO。

访问264~65799号逻辑块中的某一块，需要4次磁盘IO。

对于小文件，只需要较少的磁盘IO即可读到目标数据块。

索引分配总结

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文 件的各个逻辑块对应的物理块号（类似于内存管理中的页表——建立逻辑页面到物理页之间 的映射关系） 。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

若文件太大，索引表项太多，可以采取以下三种方法解决：

①链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。

缺点：若文 件很大，索引表很长，就需要将很多个索引块链接起来。想要找到 i 号索引块，必须先依次读入 0~i-1 号索引块，这就导致磁盘I/O次数过多。

②多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据 文件大小的要求再建立第三层、第四层索引块。采用 K 层索引结构，且顶级索引表未调入内存，则访问 一个数据块只需要 K + 1 次读磁盘操作。

缺点：即使是小文件，访问一个数据块依然需要K+1次读磁盘。

③混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接 指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表） 。

优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。

更多内容请关注微信公众号