414_文件的物理结构（下）
# 4.1_4_文件的物理结构（下）
在这个小节中我们会继续学习文件的物理结构，也就是文件分配方式相关的问题。在之前的小节中，我们介绍了连续分配和链接分配这两种分配方式，连续分配要求给文件分配的必须是一些连续的磁盘块，而链接分配允许为文件分配的是一些离散的磁盘块 和链接分配类似的是索引分配这种第三种分配方式，它同样允许给文件分配的是一些离散的磁盘块，系统会为每一个文件建立一张索引表，而索引表当中记录了文件的各个逻辑块对应的物理块，所以这个地方大家会发现，索引表的功能其实有点类似于我们内存管理当中的页表的功能，页表是建立了逻辑页面到物理业之间的一个映射关系，磁盘当中用于存放索引表的磁盘块就称为文件的索引块，而用于存放文件实际数据的那些磁盘块就称为数据块。
直接来看一个例子，假设有一个文件AAA它的数据依次存放在了2,5,13,9这么几个磁盘块当中，采用索引分配方式的话，系统会为AAA文件建立一张索引表，索引表记录了AAA的这些逻辑块和物理块之间的一一对应的这种映射关系，那么如果说 AAA文件的索引表是存放在7号磁盘块当中的，那么7号磁盘块就是AA的索引块，而2,5,13,9 这几个磁盘块是AAA的数据块
采用索引分配方式的这些文件需要在自己的目录项，也就是fcb当中记录自己的索引块到底是哪一块，索引块当中存放的是索引表，因此系统可以根据索引块的块号找到它的索引表，接下来就可以找到这些各个逻辑块对应的物理括号了。
像这个例子当中，AAA的索引表是存放在7号块当中的，它的这些实际数据是依次存放在2,5,13,9这么几个块当中的，
类似的假如说有另外一个文件，BBB它的索引块是23号块么BBB的索引表就应该是存放在这个地方。
所以这个地方大家会发现，如果采用的是索引分配方式的话，那么每一个文件都会有一张自己的索引表，而之前咱们介绍的显示链接的链接分配方式当中，文件分配表也就是fat，是一个磁盘只对应一张fat，所以这是他们俩的一个小小的区别。
另外我们可以用固定长度，固定字节的存储空间来表示这些物理块号，也就是索引表的这些表项，比如说像一个磁盘的总容量，假如说是1TB，也就是二的40次方个字节，并且磁盘块的大小是1KB，那么这么大的磁盘就可以被分为2的30次方个磁盘块，因此要表示这么多个磁盘块只需要用30个二进制位就可以了。那么4个字节的空间可以包含32个二进制位，它是足够表示2的30次方个磁盘块的块号的。
因此我们可以让索引表的块号每1个表项占4个字节，所以索引表当中的逻辑块号这些数据就可以是隐含的，因为索引表的表项每一行占的是4个字节，所以只要我们知道索引表的起始位置，那么我们就可以直接根据逻辑块号直接计算出某一个逻辑块号对应的表项到底是在什么位置了。
接下来我们要探讨的问题是采用索引分配方式应该怎么实现逻辑块号到物理块号的转变？假设此时用户想要访问的是逻辑块号 i ，那么操作系统首先需要找到这个文件对应的目录项，也就是它的fcb，从中找到这个文件的索引块的块号，再从索引块当中读出文件的索引表的内容。
那么接下来就只需要通过逻辑块号来查询索引表，就可以找到某一个逻辑块号对应的物理块号到底是多少了。查表的方式其实和咱们内存管理当中介绍的，通过逻辑页号来查询页表项的那种方式是很类似的。
所以从这个过程分析我们可以看到，如果我们想要访问逻辑块号为 i 的逻辑块的话，那么我们并不需要顺序的访问前面的0 ~ i-1号块，我们可以直接找到 i 号块存放的物理块号，因此索引分配这种方式是支持随机访问的。
另外索引分配这种方式也很容易实现文件的拓展。比如说像AA这个文件现在想要继续拓展，也就是再分配一个物理块数据块的话，那么只需要随便找一个空闲的磁盘块，比如说是19号磁盘块把它分配给AA，然后在AA对应的索引表当中增加相应的表项，这就完成了文件的拓展。因此索引分配方式中文件的拓展也是很容易实现的。不过索引分配方式的索引表需要占用一定的存储空间，这是它的一个小小的缺点。
接下来我们再来考虑下一个问题，假设每个磁盘块的大小是1KB，1个索引表的表项，也就是这样的一行占用4个字节，那么1个磁盘块只能存放1k除以4，也就是256个索引项，假如说有一个文件它的大小已经超过了256个块，那也就意味着这个文件它对应的索引表肯定也要超过256个索引项。
既然如此，这么大的索引表肯定是没办法在一个磁盘块中就可以装得下的，也就是说一个很大的文件，它对应的索引表在一个磁盘块下肯定存不下，那么我们怎么解决这个问题？一般来说有这样的三种解决方案，第一种叫做链接方案，第二种叫做多层索引，第三种叫混合索引，我们会依次介绍。
首先来看链接方案，如果说一个文件的索引表太大，那么可以为文件的索引表分配多个索引块，并且用链接的方式把它们连起来。还是接着刚才的条件往下分析，假设一个磁盘块只能存放256个索引项，那么如果一个文件的大小超过了256块的话，那么就意味着这个文件的索引表，它的索引项肯定也超过256个，因此可以把索引表拆分，为文件分配多个索引块，每一个索引块当中存放256个索引项，并且在每一个索引块当中用一定的空间存储指向下一个索引块的指针，这样的话就可以把一个很长的索引表拆分成不同的部分，并且用这种链接的方式把它们连起来了。
如果采用的是链接方案的话，文件的fcb当中只需要记录它的第一个索引块的块号，像文件AAA就只需要记录它的第一个索引块，也就是7号块。假设现在用户想要访问的是AAA的逻辑块号为256的逻辑块的话，为了查到256号逻辑块对应的物理块号，那就肯定需要找到 AA的第二个索引块，而由于各个索引块之间是用这种间接的方式把它们连起来的，所以为了找到第二个索引块的块号操作系统，首先需要把第一个索引块读入内存，然后才能根据索引块当中的指针找到第二个索引块的块号，并且把第二个索引块读入内存，只有这样才能找到256这个逻辑块号对应的物理块号到底是多少。
因此可以看到如果说用户要访问的逻辑块号对应的索引项，是在索引表当中的第二个部分的话，那么系统首先必须先顺序的读取索引表的第一部分之后才能找到索引表的第二部分，这个特点就造成了一个问题，假设一个文件的大小是64兆字节，也就是256×256 × 1KB，由于说每个磁盘块的大小是1KB，所以这个文件应该占用256×256个磁盘块，也就需要对应同等数量的索引项。而每一个磁盘块每一个索引块当中只能存放256个索引项，因此这么多的索引项就需要用256个索引块来存储，并且如果采用的是链接方案的话，这些索引块之间是用这种链接的方式把它们连起来的。所以如果说一个用户想要访问这个文件的最后的一个逻辑块的话，那么就必须找到这个文件的最后一个索引块。通过刚才的分析我们知道如果要找到最后一个索引块的话，那么必须先依次读入前面的所有的那些索引块。所以可以看到如果采用的是链接方案的话，那么为了找到文件的某一个逻辑块对应的物理块号，光是这个地址转换的过程，就可能需要200多次读磁盘的操作，这显然是很低效的，这也是链接方案所存在的最大的一个问题，怎么解决这个问题？
# 多级索引
人们提出了多级索引这种解决方案，多层索引的这种解决方案就有点类似于咱们之前学习过的多级页表的那种原理，就是要建立多层的索引表，使第一层索引块指向第二层索引块，如果说文件很大的话，甚至还可以建立第三层第四层索引块
还是用刚才的条件继续分析，假设一个磁盘块只能存放256个索引项，并且一个文件的大小是256×256个块的话，那么这个文件可以为它建立两层索引，第一层的索引块总共有256个索引项，第二层的索引块每一块也有256个缩影像，然后每一个索引项再指向某一个数据块，那在文件的目录表也就是fcb，当中只需要记录它的顶级索引表存放的索引块号到底是多少就可以了。
如果说我们采用的是这种两层索引的结构的话，那文件的最大长度可以达到256×256×1KB，也就是64兆字节这么大，这是因为如果我们采用了多级索引的结构的话，那么各层索引表的大小不能超过一个磁盘块。也就是说第一级的索引表最多只会有256个索引项，也就是会分别指向256个第二级的索引表，而第二级的索引表大小仍然不能超过一个磁盘块，所以第二级的索引表最多也只会含有256个索引项，每个索引向又会分别指向一个数据块，每一个数据块的大小就是1KB这么大，因此如果采用两层索引的话，那么文件的最大长度是64兆字节，这个条件十分重要，在考试当中经常会遇到让我们计算文件最大长度的这种类型的题。
接下来我们来看一下，如果采用多级索引的话，怎么实现逻辑块号到物理块号的转变？假设此时用户要访问的是1026号，逻辑块，那么1026÷256=4，也就是说1026号逻辑块对应的索引项应该是4号二级索引表当中存放的，而4号二级索引表存放的位置操作系统只需要从这个一级索引表当中找到4号索引项对应的物理块就可以知道了。
在读入了4号二级索引表之后，接下来应该查询4号二级索引表当中的哪一个表项，1026对256取余等于二，说明此时需要查询的是4号二级索引表当中的2号表项，找到二号表项之后就可以找到1026号逻辑块对应的物理块到底是多少了。
所以如果采用这种两层索引的方式的话，那么操作系统首先是需要根据这个fcb当中记录的顶级索引块的块号来找到顶级索引表，先把顶级索引表读入内存，然后查询相应的表项之后，又找到相应的二级索引表存放的物理块号。接下来再把二级索引表读入内存，最后再查询二级索引表，就可以找到我们最终想要访问的逻辑块到底存放在哪个物理块当中了
所以整个过程访问目标数据块，总共进行了三次读磁盘操作。第一次是读入了一级索引表，第二次是读入了对应的二级索引表，第三次才是读入我们最终要访问的数据块。类似的如果我们采用的是三层索引的结构的话，那文件的最大长度应该是256×256再乘256，再乘以1KB，也就是16GB这么大。如果采用三层索引结构的话，访问1个目标数据块，总共需要4次读磁盘的操作，所以我们得到这样的一个结论，如果我们采用的是k层索引结构，并且顶级索引表的数据还没有调入内存的话，那么根据一个逻辑块号访问一个数据块，总共需要k+1次读磁盘操作才可以完成。相比于之前的那种链接方案来说，读磁盘的操作已经是少了很多了，这是多层索引需要注意的问题。第一，大家需要学会计算文件的最大长度到底是多少。第二，大家还需要学会分析访问一个数据块到底需要多少读磁盘操作。
不过多层索引的方式也存在一个小小的问题，假如一个文件本来很小，它的数据块只有1KB这么大，但是这个文件如果在物理上采用的是两层索引的这种结构的话，那么读入这个文件1KB的内容依然需要一次读磁盘，两次读磁盘，三次读磁盘操作，可不可以用某种方式来解决这个问题？为此人们又提出了混合索引的这种方案
# 混合索引
混合索引它是多种索引分配方式的一种结合，比如说一个文件的顶级索引表当中，它可能会包含一些直接地址索引，比如说8个直接地址索引，所谓的直接地址索引就是指这些索引项是直接指向了一个数据块，所以8个直接地址索引会对应8个数据块。
另外顶级索引表当中还有可能会包含一些一级间接索引，一级间接索引会指向一个单层索引表，单层索引表的各个索引项，又会分别指向一个数据块，每个数据块是1KB。
另外顶级索引表还有可能会包含一些二级间接索引，二级间接索引会指向一个两层索引表，索引表的各个表项又依次指向了一个下一级的索引表，而第二层索引表的各个表项又分别指向了一个的数据块，所以如果有8个直接地址索引的话，他们会分别指向8个数据块，一个一级间接索引会指向一个单层的索引表，而每个索引表最多只会有256个表项，因此索引表最多只会对应256个数据块。相应的二级间接索引最多会指向256×256，也就是这么多个数据块。
因此如果一个文件它的混合索引的顶级索引表是这样的结构的话，那么这个文件最大长度可以有8+256再加65536这么多个块，也就是65800KB这么多，根据顶级索引表的这些结构来计算一个文件的最大长度，这种题型在考试当中也是很常见的，大家需要重点的把握。
接下来我们来分析一下，如果要访问某一个逻辑块，那么需要几次读磁盘操作？假设此时这个顶级索引表还没有读入内存，那么如果说我们要访问的是07号逻辑块，也就是要访问的是这个直接地址部分的话，那么我们总共需要两次读磁盘操作，第一次是读入顶级索引表，第二次是根据顶级索引表当中的某一个直接地址，找到我们的目标数据块存放的位置，然后再把这个目标数据块读入内存，所以总共需要两次读磁盘操作。
如果说我们要访问的是8~263号逻辑块，也就是要访问的是这些一级间接逻辑块的话，那么总共需要第一次读磁盘操作是读入顶级索引表，第二次是根据一级间接索引找到这一级的索引表，然后把索引表读入内存，第三次是根据索引表的内容再找到我们的目标数据块存放的位置，然后再把目标数据块读入内存，所以总共需要三次读磁盘操作。
相应的如果我们要读的是这个范围的逻辑块，也就是这些磁盘块的话，那么总共需要4次读磁盘操作。
所以可以看到采用混合索引的1个好处，就是对于小文件来说，它可能只需要占用前面的这几个块就可以了。小文件的读取只需要访问比较少的读磁盘的次数，一般来说我们计算机当中小文件是更多的，所以这是混合索引这种方式带来的一个好处。
# 索引分配总结
那么我们介绍了当文件太大索引表项太多的时候，可以采取的三种解决方案，
第一种链接方案就是把各个索引块用链接的方式把它连起来，但是它所带来的缺点，如果一个文件很大，索引表很长的话，那么想要找到 i 号索引块，就必须先依次读入0到 ~ i-1 号索引块，这就导致要查询一个索引项的时候，磁盘l次数可能会很多的问题，所以这种方案查找效率低下。
为此我们可以建立多级索引，就有点类似于我们在内存管理当中采用的多级页表那样，然后第一层索引块会指向第二层的索引块，如果说一个文件很大的话，甚至还可以建立3层甚至4层的索引块，如果我们采用的是k层索引结构，并且顶级索引表还暂时没有掉入内存的话，那么访问一个数据块只需要k+1次读磁盘的操作，但是这种方式的缺点就是即使是小文件访问一个数据块，依然是需要k+1次读磁盘操作
所以人们又提出了混合索引这种方式，一个文件的顶级索引表当中，可以既包含直接地址索引，也包含一级间接索引，也包含二级间接索引，直接地址索引，会直接指向一个数据块，而一级间接索引会指向一个单层的索引表，索引表再依次又指向各个数据块，而两极间接索引是指向一个两层的索引表，如果采用这种混合索引的方式的话，对于小文件来说，访问一个数据块所需要的读磁盘次数就可以变得更少了。
索引分配方式在考试当中是经常进行考察的，无论是小题还是大题，所以大家需要重点掌握的是这样的两个点。
第一要学会根据多层索引或者混合索引的那种结构，来计算出一个文件的最大长度是多少。那要计算最大长度，大家最关键的是需要理解，各级索引表最大是不能超过一个块的，要知道这个条件。
第二个大家要学会的是要能够自己分析访问某一个数据块，或者说访问某一个逻辑块号对应的物理块所需要的读磁盘次数到底是多少，操作系统需要从外存当中依次的读入顶级索引块，然后下一级的索引块，再下一级的索引块以此类推。大家需要注意的是题目当中的条件，顶级索引块到底是不是已经调入内存了，这个部分内容十分重要，特别是混合索引相关的知识点，很容易综合的来考察大家，所以大家还需要根据大量的课后习题来进行进一步的巩固。
# 文件的物理结构总结
这个地方我们再把上个小节和小节的内容进行一个汇总总结，我们需要掌握各种分配方式的一个思想，
像顺序分配就是要求为文件分配的必须是连续的磁盘块，而
链接分配又分为隐式链接和显示链接两种，他们都可以为文件分配离散的次方块，而隐式链接是把每个磁盘块都用链接指针的方式把它们连起来，显示链接的话是为磁盘建立一个文件分配表，然后在这个表当中记录各个磁盘块的先后关系，并且这个文件分配表是在开机的时候就会调入内存，并且之后会一直常驻内存
而索引分配方案会为文件的数据块建立一些索引表，而如果文件的索引表太大的话，又可以采用链接方案多层索引和混合缩影这几种方式来解决。采用不同的分配方式，在文件的目录像fcb当中所需要记录的这些信息也是有一定的区别的
另外大家还需要理解这些各种分配方式的优点和缺点，各种分配方式的优点和缺点很容易在选择题当中进行考察。最后还需要强调一遍，如果说题目当中只是简单的告诉我们一个文件采用的是链接分配方式，而并没有告诉我们它到底是隐式还是显示链接的话，我们一般都是默认为它指的链接分配是隐式链接的方式
