🧲1 文件的逻辑结构
📡1.1 总览
📡1.2 无结构文件
📡1.3 有结构文件
🧬1.3.1 总览
按照各记录项的存储空间是否可以改变分为定长记录和可变长记录两种
🧬1.3.2 顺序文件
（1）定义
（2）分类
第一种分类方法
①逻辑上相邻物理上也相邻
②逻辑上相邻物理上不一定相邻
第二种分类方法
（3）对于以上的几种分类，都需要解决2个问题，比如现在知道一个顺序文件的起始地址，那么
下面给出结论：
总结：
📡1.4 索引文件
🧬1.4.1 什么是索引文件
如图，将文件分成很多部分，这些部分可以在外存中离散的存放。建立一张索引表，它的指针项指向文件的各部分。在需要查找文件的第i个内容时，只需查找索引表的第i项，再查找指针的地址就可以。
索引表项都是相同长度的，且属于顺序文件，因此对它的I/O操作就很快。
🧬1.4.2 注意
📡1.5 索引顺序文件
🧬1.5.1 索引文件的缺点
🧬1.5.2 索引顺序文件的基本实现方式
对于一个文件，先选取一个关键字，比如对于学生信息可以选取姓名作为关键字，将数据按照关键字进行分组，例如：姓名A开头的为一组，姓名B开头的为1组，每个分组的关键字无须排序（方便文件的修改）。而索引顺序文件记录了各分组的第一条数据的关键字、地址。索引顺序文件的键也无须排序（方便新表项的插入），可以看出，该表是一个定长记录的、串结构的顺序文件。
这样，当系统要查找某条记录时，首先根据关键字确定该数据项的组别，根据索引表找到组别的起始地址，并顺序查找具体的文件。
🧬1.5.3 索引顺序文件的实际效果
📡1.6 多级索引顺序文件
🧬1.6.1 单级索引顺序文件的缺点
可以看到，假如数据项很多，索引顺序文件的查找次数依然较多。
🧬1.6.2 多级索引顺序文件的实现方式
将文件进行分组，各组对应一个低级索引表，而各低级索引表又对应一个顶级索引表。这样可以提高查找效率。
🧬1.6.3 效果分析
次数平均查找次数为50+50+50 = 150次。
🧬1.6.4 注意
📡1.7 总结
🧲2 文件的物理结构
🔬2.1 总览
🔬2.2 文件块与磁盘块
（1）磁盘块的作用
因为内存、磁盘的最小数据单元就是块，所以当磁盘块的大小与内存块的大小一致时，那么内存与磁盘的数据交换就会很方便。
（2）磁盘分块的基本概念
🔬2.3 文件分配方式——连续分配
⚗️2.3.1 连续分配的基本概念
示意图：
⚗️2.3.2 如何实现逻辑地址到物理地址的映射
采用连续分配，则文件的目录文件中需存放文件的起始块号及长度
查找过程：
⚗️2.3.3 连续分配的优点
（1）连续分配可以实现随机查找（类似于数组，即：查找第2个块不需要先查找第0、1个块）
（2）连续分配的文件在顺序读/写时速度最快
解释：磁盘在读取某个磁盘块时，需要移动磁头（组成原理）。当访问的两个磁盘块距离越远，移动磁头所需的时间就越长。而连续分配方式下不同磁盘块是连续的，所以读取时间最短。
⚗️2.3.4 连续分配的缺点
（1）物理上采用连续分配不方便拓展
如图，当黄色块进行拓展时，唯一的方法就是将块迁移到更大的磁盘块中去。而迁移所耗费的资源是很大的。
（2）存储空间利用率低，会产生难以利用的磁盘碎片
如图，虽然此时磁盘内空闲块的个数为5，且此时需要分配的空间只为3，但是因为没有连续的3个空间，所以就没法分配。且这5个块也难以利用起来。
⚗️2.3.5 对于连续分配的总结
🔬2.4 文件分配方式——链接分配
⚗️2.4.1 链接分配——隐式链接
（1）基本概念
文件的目录文件中存放了文件的起始块号、结束块号。且存放文件内容的每一个块都存放了下一个块的指针。
（2）如何实现逻辑地址到物理地址的映射？
类似于链表的思想
（3）拓展文件
（4）优点
①很方便文件拓展
②所有的空闲文件块都可以被利用，不会有外部碎片，存储空间的利用率高
（5）缺点
①只支持顺序访问，查找效率低
②磁盘块存储的指针也需消耗一定的空间
⚗️2.4.2 链式分配——显式链接
（1）基本概念
（注意是物理块不是逻辑块）
假设：
那么，FAT中的内容就应该是：
由FAT内容可知，2号块的下一块是5，5号块的下一块是0，0号块的下一块是1，1号块的下一块是-1，代表没有下一块，所以1号块是文件的末尾。
而目录文件中就只需要存放文件的起始块号就可以了。
（2）注意
①FAT常驻内存
②“物理块号”字段可以隐含
③一个磁盘对应一张FAT表
（3）如何实现逻辑地址与物理地址的映射
（4）优点
①支持顺序访问
若想找到一个文件的第i号块，支持随机访问（只需在FAT中找到对应的块号就可以得到它存放的物理块号），也支持顺序访问（可以在FAT中由起始块号一直顺序查找到目标块号）。
②速度快
操作系统只需访问FAT（常驻内存）就可以找到对应的物理地址。无须对磁盘进行读写，所以速度会更快
③显然，这种方式不会产生外部碎片（链式分配的一般特性）
④便于实现对文件的存储（链式分配的一般特性）
（5）缺点
FAT会占用一定的存储空间
🔬2.5 文件分配方式——索引分配
⚗️2.5.1 什么是索引分配？
类似于页表的思想。
一个文件对应一个索引表，文件的目录文件要记录该文件的索引块是几号磁盘块。
⚗️2.5.2 例子
假设：
那么文件"aaa"的索引表的内容为：
⚗️2.5.3 如何实现逻辑地址到物理地址的转变
⚗️2.5.4 注意
（1）索引表中的“物理块号“是可以使用一个固定的长度，因此逻辑块号可以隐藏。
（2）使用索引表查找i号块时，无须查找i-1号块，因此可以实现随机查找。
（3）文件拓展很容易实现：
⚗️2.5.5 缺点
（1）索引表需要占用一定的空间，这是缺点
⚗️2.5.6 待解决的问题
（1）问题描述
（2）链接方案
①基本介绍
假设一个文件需要i个索引块，那么第 j-1 号索引块中要存储第 j 号索引块的地址。这样，目录文件中就只要记录第1个索引块的地址就可以。
②缺点
如果需要访问第 i 号索引块，那么必须要将前 i-1 个索引块都读入内存，才可以知道索引块的地址。显然，这是很低效的。
（3）多层索引
①基本介绍
②例子
对于上面的那个问题，可以建立两级索引，示意图如图所示。
目录文件只需要存储顶级索引块地址即可。
此时，文件的最大的大小为256*256*KB = 64MB
③如何实现逻辑地址与物理地址的转变
假如系统需要访问1026号逻辑块，首先计算1026/256 = 4，得出这个逻辑块应该在第4个二级索引表中，所以操作系统会先将顶级索引表调入内存，找到第4个二级索引表的物理地址，并将这个二级索引表调入内存；接着，计算1026%256 = 2，得出这个逻辑块应该在第4个二级索引表的第2个表项内，于是访问得到最终的物理地址；再次访问该物理地址可以得到对应的内容。
④缺点
假如一个文件的大小很小，那么也需要访问3次磁盘才可以得到文件内容
（4）混合索引
①基本介绍
既有直接索引，也有多层索引
示意图如图所示
对于一些大小很小的文件内容可以直接存储它的地址（直接地址）。对于可以用一张索引表表示的文件内容可以指向一个单层索引表（一级间接）。对于很大的文件内容可以指向一个多层索引表（二级间接）。
②注意
③优点
⚗️2.5.7 关于索引分配的总结
🔬2.6 知识总结
🧲3 总结
本文PDF文件下载链接：提取码：ikun
操作系统，如默默守护的守夜者，无声地管理硬件与软件的交流，为计算机创造和谐秩序。
它是无形的引导者，让复杂的任务变得井然有序，为用户提供无忧体验。
操作系统的巧妙设计，让计算机变得更加智能高效，让人与科技之间的交流更加顺畅。
在每一次启动中，它如信任的伙伴，带领我们进入数字世界的奇妙旅程。
渴望挑战操作系统的学习路径和掌握进阶技术？不妨点击下方链接，一同探讨更多操作系统的奇迹吧。我们推出了引领趋势的💻OS专栏：《OS从基础到进阶》 ，旨在深度探索OS的实际应用和创新。🌐🔍
