操作系统（13）-----文件管理2：https://developer.aliyun.com/article/1511180
②多层索引
多层索引会建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。
假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256个索引项。在索引表中，只需要存放顶级索引表对应的索引块即可。
若采用多层索引，则各层索引表大小不能超过一个磁盘块，若某文件采用两层索引，则该文件的最大长度可以到256（第一个索引表最多有256个索引项，即分别指向256个索引表）*256（第二个索引表最多有256个索引项）*1KB（每个索引项又分别指向一个数据块，数据块的大小为1KB）=65,536KB=64MB
怎么实现逻辑块号到物理块号？
可根据逻辑块号算出应该查找索引表中的哪个表项。
如：要访问1026号逻辑块，则1026/256=4（1024号逻辑块存放在4号二级索引表中，操作系统只需要在一级索引表中找到4号索引项对应的物理块号即可），1026%256=2（表示需要查看4号二级索引表中的2号表项，2号表项就是1024号逻辑块对应的物理块）
因此可以先将一级索引表调入内存，查询4号表项，将其对应的二级索引表调入内存，再查询二级索引表的2号表项即可知道1026号逻辑块存放的磁盘块号了。
访问目标数据块，需要3次磁盘I/O。
同理，若采用三层索引，则文件的最大长度为256*256*256*1KB=16GB。
类似的，访问目标数据块，需要4次磁盘I/O。
总结：
采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作
③混合索引
混合索引是指多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引(直接指向数据块)，又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)。
如下图所示，8个直接地址索引对应8个数据块
一个一级间接索引会指向一个单层索引表，每个索引表最多有256个表项，所以这个索引表对应256个数据块
同理，一个二级间接索引对应256*256=65,536块。
那么如图的这种结构的索引支持的最大文件长度为65800KB。
假设想访问某个逻辑块，那么需要几次I/O操作。
若顶级索引表还没读入内存
① 访问0~7号逻辑块（直接地址），需要两次读磁盘，第一次是读入顶级索引表，第二次是通过顶级索引表中的直接地址找到目标数据块存放的位置。
注：对于小文件，只需较少的读磁盘次数就可以访问目标数据块(一般计算机中小文件更多)。
② 访问8~263（一级间接索引），需要三次读磁盘，第一次是读入顶级索引表，第二次是通过一级间接索引找到下一级索引表，将这一索引表读入内存，第三次是通过这一索引表的索引项找到目标数据块的位置，再将目标数据块读入内存。
③ 同理，访问264~65799（二级间接索引），需要四次读磁盘。
总结：
①链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入0~i-1号索引块，这就导致磁盘I/0次数过多，查找效率低下。
②多层索引：建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作。
缺点：即使是小文件，访问一个数据块依然需要K+1次读磁盘。
⑧混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引(直接指向数据块)，又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)。
优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。
重点：
①要会根据多层索引、混合索引的结构计算出文件的最大长度(Key：各级索引表最大不能超过一个块)；
②要能自己分析访问某个数据块所需要的读磁盘次数(Key：FCB中会存有指向顶级索引块的指针，因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外，要注意题目条件--顶级索引块是否已调入内存，若没有则需要增加1次I/O操作)
三种分配方案表格如下：
2.对空闲磁盘块的管理
（1）存储空间的划分与初始化
安装 Windows 操作系统的时候，一个必经步骤就是为磁盘分区(C盘、D盘、E盘等)，也就是将物理磁盘划分为一个个文件卷(逻辑卷、逻辑盘)。
初始化就是将各个文件卷划分为目录区、文件区。
目录区主要存放文件目录信息(FCB)、用于磁盘存储空间管理的信息。
文件区用于存放文件数据。
平常使用的电脑都是将一个物理磁盘划分为多个逻辑磁盘，但是在某些系统中，支持超大型文件，可支持由多个物理磁盘组成一个文件卷（一个逻辑磁盘）。
（2）管理方法
空闲表法：
磁盘存放情况如下：
用空闲表来记录第一个空闲盘号，以及空闲盘块数，下图是磁盘对应的空闲表：
空闲表法适用于"连续分配方式"。
那么应该如何分配磁盘块？
与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。
例如，新建的文件请求3个块，如果使用首次适应算法的话，操作系统会依次检查空闲表中的各个表项，找到第一个能满足连续3个块空闲的空闲区域。由上图可知，第一个空闲块号为10的空闲区域满足。
最佳适应算法：找到最小的能够满足空闲块数的空闲区域进行分配
最坏适应算法：找到最大的能够满足空闲块数的空闲区域进行分配
如何回收磁盘块？
与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况
① 回收区的前后都没有相邻空闲区；（会在空闲表中新增一个表项）
②回收区的前后都是空闲区；（将回收区与前后空闲区合并，那么表项的数量会减少1）
③回收区前面是空闲区；（与前面空闲区合并）
④回收区后面是空闲区。（与后面空闲区合并）
③④两种情况不会导致表项减少。总之，回收时需要注意表项的合并问题
空闲链表法：
空闲链表法又分为空闲盘块链和空闲盘区链，空闲盘块链以盘块为单位组成一条空闲链，空闲盘曲链以盘区为单位组成一条空闲链。
空闲盘块链：
空闲盘块种存储着下一个空闲盘块的指针。
如何分配磁盘块？
若使用空闲盘块链，操作系统会保存链头和链尾指针。如上图，链头为20号磁盘块，链尾为0号磁盘块。若某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。
如何回收磁盘块？
回收的盘块依次挂到链尾，并修改空闲链的链尾指针。
适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作。
空闲盘区链：
连续的空闲盘块组成一个空闲盘区。空闲盘区中的第一个盘块内记录了盘区的长度、下一个盘区的指针。
如何分配磁盘块？
若使用空闲盘区链，操作系统保存着链头、链尾指针。若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。
如何回收磁盘块？
若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。如下图，若此时要回收的是17，18盘区，那么将这一空闲盘区挂到链尾。
空闲盘区链适用于离散分配、连续分配都适用。并且相比于空闲盘块链而言，为一个文件分配多个盘块时效率更高。
位示图法：
对于位示图，每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲，“1”代表盘块已分配。位示图一般用连续的“字”来表示，如本例中一个字的字长是16位，字中的每一位对应一个盘块。因此可以用(字号，位号)对应一个盘块号。当然有的题目中也描述为(行号，列号)
在考试中，要能自己推出盘块号与(字号,位号)相互转换的公式。
注意题目条件:盘块号、字号、位号到底是从0开始还是从1开始
如本例中盘块号、字号、位号从0开始，若n表示字长，则：
(字号,位号)=(i,j)的二进制位对应的盘块号b=ni+j
b号盘块对应的字号i=b/n，位号j=b%n
若字号、位号从1开始，n表示字长，则：
b=n(i-1)+j
如何分配磁盘块？
若文件需要K个块：
①顺序扫描位示图，找到K个相邻或不相邻的“0”；
②根据字号、位号算出对应的盘块号，将相应盘块分配给文件；
③将相应位设置为“1”。
如何回收磁盘块？
①根据回收的盘块号计算出对应的字号、位号；
②将相应二进制位设为“0”。
若采用位示图法，则连续分配、离散分配都适用。
成组链表法：
空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。
文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。
在超级块中，记录了下一组空闲盘块的数量以及空闲盘块号，通过这些盘块号就可以依次找到下一个分组的各个盘块。
例如下图，300磁盘块，作为下一个分组的第一个磁盘块，这一磁盘块会记录下一个分组的空闲磁盘块的信息，100表示下一个分组的空闲盘块数的块数，301~400表示下一个分组的空闲块号。
若已经没有下一组空闲块，则表示下一组空闲盘块数的磁盘块的下一个磁盘块用某特殊值表示，说明这是最后一组空闲块。所以最后一个分组块数为99，其中一个用来存放特殊值，如下图，特殊值为-1。
注：一个分组中的块号不需要连续，此处只是为了更方便看出各个分组的数量。
如何分配磁盘块？
例如，现在需要1个空闲块
① 检查第一个分组的块数是否足够。1<100，因此是足够的。
② 分配第一个分组中的1个空闲块，并修改相应数据。（如上图，会将分组中的最后一个磁盘块201分配出去，磁盘块分配出去后，就要修改超级表的数据，将这一空闲磁盘块删除，并且将块数由100改为99）
注：由于超级块已经读入内存，所以只需要根据超级块中的数据进行检查即可。
又例如，需要100个空闲块
①检查第一个分组的块数是否足够。100=100，是足够的。
②分配第一个分组中的100个空闲块。但是由于300号磁盘块内存放了再下一组的信息，因此如果直接把300号磁盘块分配给文件，那么和下一组链接的信息就断了，所以在300号空闲磁盘块分配给文件之前，需要将300号磁盘块中的数据复制到超级块中，这样就能保证虽然分组全部分配给文件，但是下一个分组的链接信息依然保存在超级块中。
如何回收磁盘块？
（1）若第一个分组没满，可以把回收的空闲块插到第一个分组中。
例如，假设每个分组最多为100个空闲块，此时第一个分组已有99个块，还要再回收一块，我们首先将该块的链接信息放到超级块中，再将下一组空闲盘块数由99变为100。
（2）若第一个分组已满，则把回收的空闲块作为一个新分组。
例如，假设每个分组最多为100个空闲块，此时第一个分组已有100个块，还要再回收一块。由于第一个分组满，所以不能将这一回收的空闲块放到第一个分组中。所以我们可以把这一回收的空闲块作为一个新的分组。但是我们也要将超级块的内容复制到这一新分组中。那么这一新回收的块即可作为新的分组，拥有了下一分组的链接指针。
并且超级块的数据也需要进行修改，使其指向新分组，也就是新的回收的空闲块组成的新分组，由于新分组中只有一个空闲块，所以超级块中表示下一分组的块数的磁盘块中的内容为1
七.文件的逻辑结构与物理结构的对比
逻辑结构与物理结构分类如下：
在用户看来，整个文件占用的是连续一片的逻辑地址空间，但是从操作系统的视角看，只负责把文件拆分成一个个逻辑块，再根据分配方式（连续分配，连接分配，索引分配）将文件的数据块分配到磁盘中。
对于顺序文件，各记录可以顺序存储或链式存储。
（1）顺序存储：各条记录相邻着存放
对于顺序存储，我们可以直接确定第i条记录的逻辑地址，即支持随机访问。
（2）链式存储：各条记录离散着存放，用指针表示先后关系
而对于链式存储，要确定i条记录的逻辑地址，则必须先读入0~i-1条记录
① 链式存储的顺序文件，可以采用连续分配：逻辑上相邻的块，物理上也相邻。
② 链式存储的顺序文件，也可以采用链接分配，这里区分链式存储和链接分配：
文件内部各条记录链式存储：由创建文件的用户自己设计的
文件整体用链接分配：由操作系统决定，操作系统会将整个文件拆分成一个个相等的逻辑块
例如上图，逻辑块1中是没有数据的，但是操作系统不会管这些，他只管将整个文件都拆分成一个个逻辑块。再将这些逻辑块放到磁盘中。
在磁盘中存放这些逻辑块时，会用链接分配的方式记录这些逻辑块的存放顺序：
对于索引文件：
索引文件从用户视角来看，整个文件依然是连续存放的。如：前1MB存放索引项，后续部分存放记录。可以先将索引项调入内存，查询索引项，找到目标学生的索引项，根据索引项得到目标学生信息的逻辑地址，最后读取信息即可。
索引文件可以采用连续分配，链接分配，也可以采用索引分配，也就是操作系统会维护一个索引表，索引表会记录逻辑块号到物理块号的映射关系。
索引文件的索引表：用户自己建立的，映射：关键字--->记录存放的逻辑地址
索引分配的索引表：操作系统建立的，映射：逻辑块号--->物理块号
总结：
不是采用链式存储的顺序文件对应链接分配，索引文件对应索引分配，顺序文件和索引文件对应的是逻辑结构，在用户看来，整个文件占用连续的逻辑地址空间。文件内部的信息如何组织，由用户自己决定，操作系统并不很关心。
链接分配和索引分配是操作系统将逻辑块分配到外存（磁盘块中）的方式，即实现逻辑块号到物理块号的映射关系，是操作系统负责的。
所以，顺序文件可以使用3种分配方式，索引文件同理，两者是没有必然联系的。用户只需要提供想要访问的文件的逻辑地址，由操作系统负责将文件以不同的方式存储起来，并且将用户提供的逻辑地址转为物理地址。
操作系统（13）-----文件管理4;https://developer.aliyun.com/article/1511187
