学习日期：2024.7.15
内容摘要：文件的物理结构，逻辑结构与物理结构
目录
引言
文件分配方式
连续分配
链接分配
隐式链接
显式链接
索引分配
索引块大小不够装入整个索引表怎么办？
①链接方案
②多层索引
③混合索引
逻辑结构与物理结构
C语言创建无结构文件
C语言创建顺序文件
易混点：顺序文件采用顺序存储/链式存储
索引文件
引言
在 文件管理基础 中我们提到过，类似于内存分页，磁盘中的存储单元也被分成一个个“块”。在很多操作系统中，磁盘块的大小与内存块、页面的大小相同，这样在内存和磁盘之间进行数据交换时，只需要按块为单位读写即可，较为方便。
在基本分页存储管理中，我们学习过，进程的逻辑空间被划分为一个一个页面，同样的，在文件管理中，为了方便对数据的管理，文件的逻辑地址空间也被分为一个一个的文件“块”。文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式
用户通过逻辑地址操作自己的文件，操作系统负责实现从逻辑地址到物理地址的映射，本章的内容就是操作系统如何实现这一过程。
文件分配方式
连续分配
连续分配方式要求每个文件在磁盘上占有一组连续的块。
如何实现逻辑块号到物理块号的映射？
在FCB中记录文件存放的起始块号和长度，如图中“aaa”文件的起始块号为4，长度为3，这样就能访问任意的“aaa”文件了。物理块号 = 起始块号+逻辑块号
因为可以直接算出逻辑块号对应的物理块号，因此连续分配方式可以顺序访问，也可以直接访问（类似顺序表，访问逻辑块号2不需要先访问0和1）。
优点：机械硬盘在读取某个磁盘块时，需要移动磁头，访问的两个磁盘块相隔越远，所需时间越长，所以连续分配的文件在顺序读/写时最快。
缺点：如上图所示，文件A此时占用了三个块，此时文件A写入了新信息，要拓展一个块，但是因为其要满足连续存储，只能选择要么让文件A后面的一堆块全部往后挪一格，要么把文件A集体迁移，挪到绿色部分的空闲区域里，这显然都会带来很大的I/O成本。
还有， 假如磁盘有很多空闲块，但是这些块彼此不相邻，可能就放不下新文件，这是连续分配的一个显而易见的弊端，不能利用这些非连续的磁盘碎片。（类似连续内存管理当中的外部碎片）
可以用紧凑来处理碎片，（把相邻的文件放一块，把碎片整合成大一些的空间）但是这样显然要进行很多的I/O操作，耗费巨大的时间代价。
这和顺序表非常类似！容易查找，不方便拓展，必须连续保存，优缺点也和内存管理中的连续分配管理方式一样。
链接分配
链接分配采取离散分配的方式，可以为文件分配离散的磁盘块，分隐式链接和显式链接两种。
有顺序表自然就有链表，链式分配就像链表一样，FCB中存放文件的起始块号和结束块号，而每个磁盘块都会保存指向下一个磁盘块的指针，这些指针对用户来说是透明的。
隐式链接
如何实现逻辑块号到物理块号的映射？
用户给出逻辑块号，操作系统找到该文件对应的目录项FCB，从FCB中找到起始块号，再沿着指针访问到需要的物理块。
缺点：同链表类似，采用链接分配（隐式链接）方式的文件只支持顺序访问，不支持随机访问。因为我们只知道起始块号和指针，要访问第 i 号逻辑块，就必须要按顺序访问前面的所有逻辑块，共需要i+1次I/O操作，查找效率低。且指向下一个盘块的指针也要占据少量的内存空间。
优点：也同链表类似，这种方式方便拓展文件，因为块是离散分配的，随便找一个空闲磁盘块，挂到文件的磁盘块链尾，并修改文件的PCB即可。所有的空闲磁盘块都能被利用，不会有碎片问题，外存空间利用率高。
显式链接
把用于链接文件各物理块的指针显式的存放在一张表中，即文件分配表（FAT，File Allocation Table），目录中只需要记录文件的起始块号。
假设某个新创建的文件"aaa"依次存放在磁盘块2，5，0，1中，则如右图，最后1的下一块为-1，表示此处是结尾。
一个磁盘仅设置一张FAT，开机时将FAT读入内存，并常驻内存，FAT的各个表项在物理上连续存储，因此“物理块号”字段可以是隐含的。
如何实现逻辑块号到物理块号的映射？
用户给出要访问的逻辑块号 i，操作系统找到该文件对应的目录项FCB，从目录项中找到起始块号，若 i>0，则查询内存中的文件分配表FAT，再沿着表找到 i 号逻辑块对应的物理块号。因为FAT是常驻内存的，所以沿着“链表”找逻辑块对应的物理块这个过程，是在内存中完成的，不需要进行I/O操作，这就节省了很多时间。
显式链接分配就好比把指针的指向做成了一张表，塞进了内存里，每次在内存里指到最后的结果再直接访问，节约了I/O操作。
结论：采用链接分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（访问 i 号逻辑块时，不需要按顺序访问前面的0 ~ i-1块）。
优点：很方便文件拓展，不会有碎片问题，外存利用率高，支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，效率更高。
缺点：FAT常驻内存，需要占用一定的内存空间。
（如果考试题目没说是显式还是隐式，只说了链接分配，那么默认是隐式连接分配）
索引分配
索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系）。
索引表存放的磁盘块称为索引块，文件数据存放的磁盘块称为数据块，和显式链接的链式分配的区别是，FAT是一个磁盘对应一张，而索引表是一个文件对应一张。
可以用固定的长度表示逻辑块号，其可以是隐含的。
如何实现逻辑块号到物理块号的映射？
用户给出要访问的逻辑块号 i，操作系统找到该文件对应的FCB，从中找到文件对应的索引块的块号，再从索引块当中读到索引表所在的位置，再查索引表即可得知 i号逻辑块对应的物理块在外存中的存放位置，最后把实际的物理块读入。这和从逻辑页号查询页表项的过程很类似。
优点：显然在这个过程中，我们不需要访问前面的0到i-1号块，因此该方法支持随机访问。同样的，当我们要拓展文件时，只需要给文件分配一个空闲块，并增加一个索引表项即可，拓展容易。
索引块大小不够装入整个索引表怎么办？
但是我们会遇到一个问题，假如一个磁盘块1KB，一个索引表项4B，则一个磁盘块只能放256个索引项，如果一个文件的大小超过了256块，那么一个磁盘块是装不下文件的整张索引表的，怎么办呢？
有以下三个办法
①链接方案
将多个索引块链接起来存放。
每个索引块中存放比256个稍微少一点的索引项，剩下的空间存放一个指向下一个索引块的指针，这样就可以把很长的索引表拆开，并且用指针链接。文件的FCB只需要记录其第一个索引块的块号，之后如有需求，沿着链接指针查找即可。
缺点：假如一个文件大小为64MB（256KB*256KB），那么就需要256*256个索引项，也就需要256个索引块来存储，这些索引块全部要用链接方式存储，那么运气不好的情况下要读足足255个索引块才行，时间成本过高了。
②多层索引
多级存储结构再一次堂堂登场！在使用二级索引时，一级索引表的表项不再对应某个具体的文件，而是指向二级索引表，而二级索引表再对应具体的文件。
在64MB文件的这个例子中，虽然需要的索引块是257个（1+256），比上面的情况多了一个，但是读索引块的次数却最多只需要两次，速度无疑是巨大的提升，而多的一个索引块仅仅1KB，无伤大雅。
可以根据逻辑块号算出需要查找索引表中的哪个表项，如要访问1026号逻辑块，则
一级：1026/256= 4 二级：1026%256= 2 所以先将一级索引表调入内存，查询4号表项，再将其对应的2号索引表调入内存，查询2号表项，就知道1026号逻辑块存放的磁盘块号了，访问目标数据块，只需要3次磁盘I/O。
如果文件更大，就增多层数，因为各层索引表大小不能超过一个磁盘块，所以两层索引对应文件的最大长度就是256*256*1KB=64MB，几层就乘几次256就行，最后单位是KB。这个“256”就是一个磁盘块最多能放多少个索引项，有时候需要计算出来。
采用K层索引结构，访问一个数据库需要K+1次I/O操作。（前面读索引表，+1读物理块）
缺点：当采用多层索引时，如果文件非常小，比如说小于1KB，一个数据块就能放下了，但还是要为它建立两级甚至更多索引表，索引块比数据块都多，还需要读好几次，浪费空间。
③混合索引
混合索引是多种分配方式的结合。一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含指向不同层级索引表的各级间接索引。
当我们要访问直接地址索引对应的逻辑块时，读磁盘两次。（读顶级索引表+根据地址读数据块）
当访问一级间接索引时，读三次（读顶级+读一级+读数据块）
依此类推，访问二级间接索引时读四次。
采用混合索引的好处是比较灵活，小文件就少点层数，大文件就多几层，对于小文件只需要较少的I/O次数就能读取。
逻辑结构与物理结构
我们在这两章学了很多相似的概念，文件的逻辑结构和物理结构中好像都有顺序、链接、索引......搞得人头晕。那么，它们之间有什么区别和联系呢？（上一章链接： 文件的逻辑结构）
C语言创建无结构文件
生成一个text.txt文件，写入10000个Hello world！写入的每个字符1B。
因为在我们看来，整个文件占用一片连续的逻辑地址空间。所以当想要读第16个字符时，只需要使用fseek和fgetc就行，看起来我们就是读了连续的第16个字符一样。如下图所示，应该是o。
但是从操作系统的角度来说，它看到的是一堆二进制数据，它不关心数据的具体内容。这些数据会被拆分到若干个块当中，逻辑块号相邻。再根据采用的文件管理策略来决定使用哪种分配方式，将这些数据块存到磁盘当中。
而保存的方式就是我们之前学过的连续分配、链接分配和索引分配。
如fgetc语句就使用了Read系统调用，操作系统将（逻辑块号，块内偏移量）转换为了（物理块号，块内偏移量）。这个过程我们用户不关心，对于用户而言，就像是在直接操作逻辑块一样。
C语言创建顺序文件
顺序文件也是一样，比如说在下图中，我们用结构体存储了学生的信息，有学号、姓名、专业，然后定义了一个数组student，用这个数组保存了N个学生的信息，每个学生的名字和专业暂时是"?"，再使用fwrite将这些数据写入fp这个文件。（不必纠结代码，搞懂原理即可）
我们同样可以使用逻辑地址直接访问这个文件，代码省略，弄懂原理即可。
存放方式也如前面介绍的，连续分配、链接分配和索引分配。
易混点：顺序文件采用顺序存储/链式存储
顺序文件：各个记录可以顺序存储或链式存储。
这里的“顺序存储”，“链式存储”是对用户可见的，是逻辑上的顺序存储、链式存储，所以用蓝色表示，具体来说，可以理解为构造函数的顺序和链式。
如图，链式存储中定义了下一个学生的存放位置，各条数据离散存放，在逻辑上是链状的，用指针表示先后关系。和数据结构里的顺序表、链表一样。
但是无论如何，在用户视角看来，这些数据一定占据一整块连续的空间（蓝色长方形是连着的，区别是用箭头连起来还是挨个排好了队）
但是操作系统看起来.......还是如右图这样，一个一个块
所以操作系统可能将链式存储的文件在磁盘上连续分配，也可能将顺序存储的文件在磁盘上链接分配，和之前那两张图一样，所以说，逻辑上如何储存和物理上如何储存无关。
文件内部各条记录用链式存储是由用户设计的，文件整体用链接分配是操作系统决定的。
索引文件
我们在文件的逻辑结构中，还学习过索引文件，那么它和索引分配有什么关系呢？
我们前面说，逻辑结构是构造函数的设计，索引自然也需要设计。左侧的这个结构体就是定义了一个索引项，每个索引项记录了学生的学号和其记录的逻辑地址。
上图就是此时的文件逻辑结构，每一个IndexTable对应一个学生的信息，这就是一个索引文件。
从用户视角来看，整个文件依然是连续存放的。如前1MB存放索引项，后续部分存放记录。
从操作系统视角来看，这些仍然会被拆成一堆1KB的磁盘块，可以用连续分配、链式分配、索引分配任意分配方式。
区别
索引文件的索引表：用户自己建立的，映射：关键字 To 记录存放的逻辑地址
索引分配的索引表：操作系统建立的，映射：逻辑块号 To 物理块号
总之一句话，文件的逻辑结构是我们定义的，是我们用户的视角看到的文件的样子，且看起来总是占用连续的逻辑地址空间，我们不知道也不关心它具体存在哪个物理块里。
而物理结构是操作系统决定的，决定了文件的存储方式，操作系统负责将逻辑地址转变为（逻辑块号，块内偏移量）的形式，实现逻辑块号到物理块号的映射，操作系统不知道也不关心具体的文件内容。
头都绕晕了，终于捋清楚了，真是辛苦我自己啦！
感谢您看到这里，如果满意的话麻烦您点个赞支持一下，个人主页还有更多内容分享。
个人能力不足，如有错漏还请指出，我会尽快修改。
内容总结自王道计算机考研《操作系统》 和 人民邮电出版社《操作系统导论》
