应网友催稿，主包最近也是很多事很疲惫，所以笔记以最简洁形式来了，可能不适合初学者抠细节，但是复习框架是够的

一、文件系统基础概念

我直接思维导图（放大来看）

【文件基础概念术语】

• 定义了解一下：【文件】就是一组有意义的数据/信息的【集合】
  • 一般【文件】是存储在【磁盘】的（因为是要长期保存的数据）
• 文件的【属性（也叫“访问类型”）】（只记重要的常用的）：
  • 文件名："四级学习资料.pdf" 的这个 "四级学习资料" 就是给用户辨别的文件名
    • 注：同一目录下不可有同名文件（比如不能有2个"test.txt"）
  • 标识符：文件系统内部给操作系统识别各个文件的符号
    • 虽然同一目录下不允许同名文件，但是我在桌面和在D盘还是可以创建两个同名的“test.txt”文件啊，操作系统内部就会用一串用户看不懂的数字、符号组合，来标识区分各个文件
  • 类型：.mp3、.txt、.java、.pdf......这些文件类型
  • 位置：特指用户看的懂的文件路径，比如“D:/data”
    • 而非物理的磁盘实际地址
  • 大小：就是这个文件的实际大小
  • 保护：就是【安全】那限制用户的“写、改、读...”等权限，经常做开发的应该会接触

；

；

其中思维导图里的【文件结构】只是简单提一下其【逻辑结构】，下面第二大点会重点讲

 【例题】

二、文件目录（简称“目录”）

1、【目录文件】概念

        当我们双击“照片”后，操作系统会从一个“目录表文件”中找到【关键字 “照片”】对应的【目录项(也就是记录)】，然后根据这个信息从外存中将“照片”目录的信息读入内存，于是“照片”目录中的内容就可以显示出来了。

        而这个“目录表文件”就是【目录文件】，它本身是存磁盘上的结构化文件，记录当前路径下所有文件 / 子文件夹的元数据（名字、权限、物理块号）。永久存放于外存磁盘，在运行时从外存调入到内存方便操作系统随时查找文件时用到它

• 【文件控制块：FCB】=【目录项】

  • 那么一个【目录文件】里记录了很多条【目录项】，这每一条【目录项】也叫【文件控制块：FCB】
    • 再次强调FCB的多个名字：【目录项】、【文件控制块】
    • 他记录的就是一个文件的各种属性，其中最重要的是【文件名】、【文件物理存放地址】
    • 另外：（进程有【PCB】、文件有【FCB】，别记混了！！！）

2、【索引节点】（对FCB的改进）

注意：

• 1、记一下【FAT32文件系统】不用索引节点
• 2、凡是看到【从目录项分离】、【分离目录】这些字眼都是指【索引节点形式】

【索引节点重点】

• 因为在目录表查找文件时其实只用到了【文件名】，所以FCB太多冗余属性信息了
• 因此【索引节点】的改进结构如下：
  • 【索引表】：只记录【文件名】+【该文件索引节点的位置指针】
  • 【索引节点】：除了【文件名】之外的文件其他属性信息
    • 另外，放在外存的索引节点叫【磁盘索引节点】；
    • 放在内存后的索引节点叫【内存索引节点】，放在内存后因为文件会被改动，所以会额外添加一些内容（比如：几个进程在访问这个节点？这个节点被改写了吗？.....等，了解即可）

3、【目录文件】和【文件目录】的区别

这几个知识点可能很多人会混淆，下图直观解释了

• 【文件目录】和【目录文件】
• 【目录项】和【记录】
  • 【记录】：是一个【普通文件】的“一行数据信息”
  • 【目录项】：是【目录文件】里的“一行数据”，目录文件是特指“记录文件目录信息的文件”抱歉这里应该一个文件目录应该对应的是【文件】而不是【文件夹】的，我截图时忽略这点，急了。。。

 【例题】

三、文件的【逻辑结构】

直接思维导图，记得放大看

1、无结构文件

• 又称【流式文件】，就是一串【字符流】，长度单位是【字节】，没有结构所以也没甚好探讨的

2、有结构文件

• 又称【记录式文件】，由多个【记录】构成
  • 每个记录里可以【定一个数据项】作为【关键字】
  • 1个【记录】由 多个【数据项】构成
  • 而【记录】的类型又分为【不定长 (可变长) 记录】和【定长记录】
    • 【定长记录】：每个记录的【数据线个数一样】、【对应的数据项大小一样】
      • 重点：【定长记录】可以【随机存储（随机查找）】！！！
        • 就像访问数组第3个元素直接访问 a[2]！！只要知道了第1个记录的起始地址 + 2个记录的大小就找到 a[2]了

    • 【不定长 (可变长) 记录】：每个记录的【数据线个数不一样】或者【对应数据项的大小不一样】

      • 重点：【不定长 (可变长) 记录】不可以【随机存储（随机查找）】！！！

        • 你都不知道每个记录的大小规律，怎么计算第i个元素在哪

• 有结构文件(记录式文件) 的【文件类型】

  • 1）《顺序文件》：

    • 顾名思义，就是文件一个一个按顺序排列
      • 逻辑上：就是数据结构的【逻辑结构之：线性结构】（回忆线性结构有：线性表、串、数组、队列、栈）
      • 物理上：【线性表】物理上还对应了【物理结构：顺序存储 、链式存储】，所以顺序文件同样也包含了【顺序存储】+【链式存储】
        • 但是考试不考【顺序文件：链式存储】，所以考试中默认【顺序文件】= 逻辑上、物理上都是【顺序存储】！！！！！
    • 【顺序文件】还分【可变长记录】、【定长记录】
      • 区别是： 【能否随机存取】！！！！
        • 【不定长（可变长）记录】不适合【随机存取】的，因为各个记录大小不一样，没法根据a[0]的地址算出第i个记录在哪
        • 【定长记录】是所有记录大小都统一，因此可以根据大小计算出a[i]的地址，可以【随机存取】【定长记录】还分【串结构】、【顺序结构】
          • 区别是： 【能否按关键字排序】！！！！
          • 串结构不能按关键字排序，每次查找都要从头遍历；顺序结构可以按关键字排序，比如按姓名首字母大小、学号第一位大小

  • 2）《索引文件》：

    • 要记住的重点就是：
      • 添加【索引表】，每个【索引记录】是【变长记录】的长度、地址位置
        • 索引表的【每一个记录 (索引表项)】，一一对应【每一个变长记录】
      • 【索引表】这个表必须是顺序、记录是定长的；
        • 【索引表】指向的【变长记录】才是乱序的、记录是不定长的
      • 可以实现【快速查找 “不定长记录”】，但却额外增加了【索引表空间】

  • 3）《索引顺序文件》

    • 我直接思维导图解释，要记住的重点就是：
      • 解决【索引表】空间大问题：把 “多个变长记录” 归为【一组】
        • 索引表【每一个记录 (索引表项)】，指向的是【一组里的 “第1个记录” 的信息】
      • 【索引表】必须是顺序、记录是定长的，但不需按关键字排序；
        • 【变长记录组与组】之间是【乱序的】；
          • 【一组里的记录】是【按顺序的】
      • 不仅减小了【索引表空间】、还提高了【查找效率】

• 顺序文件、索引顺序文件的【查找次数】：全网最透彻，没有之一

  • ​​​​​​1个含有【​n个记录】的顺序文件，【查找一个记录的平均次数】就是【(1+n)/2】
  • 然而有的题目会隐含了 “粗略的”【平均查找次数公式】，我们就不需要上面这个公式了
    • 例如这题，题目规定了计算【平均查找次数的公式】=【总记录数 / 2】
  • 而【n条记录的顺序文件】若用【一个索引文件】
    • 【最好的情况】就是分成【根号n个分组】=【n个索引项的索引表】
      • 则【索引顺序文件】的【平均查找次数】计算：
        • 【索引表平均查找次数】+【1个分组平均查找次数】
• 这还多一个【多级索引表】，效率更高，原理就是“不断套娃”，【高级索引表】记录【低级索引表】的表项位置、【最低级索引表】才记录【各组变长记录】

【例题】

四、文件的【物理结构】

前提提示（不是知识点，只是方便加深计组的知识点）：

        这一块概念有点像《计算机组成原理——第3章磁盘和固态硬盘》的内容，像复习的可以去看看（可看可不看，非必要）：

 《磁盘和固态硬盘》https://blog.csdn.net/m0_73991249/article/details/149423765

1、【文件块】和【磁盘块】理解

四句话：

• 1、内存和外存（磁盘）以【块】传输
  • （【块】就是把多个存储单元分为一组，块之间存储单元都一样）
• 2、用户操作的是【逻辑块号 + 块内地址】
  • （这里不理解需要补习计组内容，块内地址其实就是一块里的存储单元的相对地址）
• 3、实际磁盘里用的是【物理块号 + 块内地址】
• 4、用户的【逻辑块号 + 块内地址】对应 映射 磁盘的【物理块号 + 块内地址】

2、三种分配方式（映射方式）

【个人总结超快回忆法】：

• 连续分配、链式分配、索引分配每次回想起来都会忘，所以我觉得应该直接用数据结构形状来记忆

1）连续分配

就是【数组】！！！

要求【每个文件】物理磁盘上是【连续存放】

• 重点：
  • 文件【目录项】记录：该文件【第一个磁盘块号】+【所占用块数】
  • 映射关系：【物理块号 = 起始块号 + 逻辑块号】
    • （比如图中给出【逻辑块号0】，那么对应的【物理块号 = 起始块4 + 逻辑块0 = 4】）
  • 优点：
    • 【可以随机访问（因为连续块方便计算块位置）】
    • 【方便磁盘访问（磁盘、磁头、磁带原理）】
  • 缺点：
    • 【为了保持文件整体有序，增、删块要整体迁移，不方便】
    • 【不灵活，只要连续空间，那就会产生很多外部碎片】
    • 容易遗漏这个知识点：【连续分配】不允许【文件长度可变】！！！

       ​​​

2）链式分配（这种文件又叫【链接文件】）

【物理上】是【离散分散存放的】

•  ① 隐式链接（【链式分配】的【默认形式】）

  • 重点：题目没有指明是“显式链接”时【连接分配】通通默认等于【隐式链接】
  • 文件【目录项】：记录文件的【起始块号】+【结束块号】
    • （因为每个盘块都有指向下一个盘块的指针，所以中间信息不用记）
    • 缺点：（就是链表的特点）
      • 不能随机存取，只能顺序访问！！！
      • 其中一个盘块有问题，整个文件完蛋
      • 指针也占空间
    • 优点：插入删除方便（链表特点，改链尾节点的指针指向即可）

• ② 显式链接

  • 重点：
    • 就是在隐式链接基础上加了个【FAT（File Allocation Table）文件分配表】
    • 文件【目录】项：只有【起始块号】！！！！
      • 然后每个盘块的下一块的指针由【FAT表】来记录！！！！
      • 注意：【FAT表】之有一张，一开机就读入【内存】，所以显式链接【查找】文件时无需访问磁盘！！！！
    • 优点：
      • 相对于“隐式”，可以【随机存取】！！！
        • 隐式：要到磁盘外存一个一个遍历 [文件aaa] 的所有块，故【顺序存取】
          • [文件aaa] 有n个盘块，就可能【磁盘I/O：n次】
        • 显式：FAT表常驻内存，【FAT表内】依旧像链表一样要【顺序存取】，但是全程都在内存
          • 直到找到 [文件aaa] 所需的那一块的指针地址后，才去外存取出
          • 全程只有取盘块这1次【磁盘I/O：1次】
          • 因此比【隐式】快得多（因为 [查找时] 不访问磁盘）（注意【随机存取】是相对于【访问磁盘】来说的，在FAT表内查找文件时，其逻辑还是像链表一样顺序查找）

3）索引分配

 依旧文件在物理上【离散存放】（只有【连续分配】才是【连续存放】）

• 组织方式就是：
  • 系统为“每个文件”建立一个【索引表】
    • 索引表记录【逻辑块】和【物理块】之间的关系
  • 文件【目录项】：记录文件的【索引块】
    • 磁盘块里存的是“索引表”——就叫【索引块】
    • 磁盘块里存的是“文件数据”——就叫【数据块】
    • 【索引块】里存【索引表】；【索引表】的表项指向【数据块】
• 因为【索引块】就是一个物理磁盘块，大小固定，如果【索引表】太大，一个【索引块】会装不下
  • 那就分出3种分配方式

  • ① 单级索引分配（【链接方案】）

    • 一个【索引块】装不下就多几个，然后采用【链式存储】连接各快
    • 因此可知，只能【顺序访问】，而且耗大量索引块空间

  • ② 多级索引分配

    • 像多级目录一样，分一级、二级索引表，一直套娃直到指向【数据块】
    • 重点：固定【所有索引表大小】<=【磁盘块大小】！！
    • 那么要注意考点：
      • 1、给出N级索引文件、磁盘块大小、一条索引表项大小，问你 “大小最大多大？”
        • 【索引表大小】=【磁盘块大小】，然后先计算一个索引表有最多可有几条【索引项：m】
        • 然后【m × m × m ... m × 块大小（m乘N层索引这个“N”次）】就是结果
      • 2、N层索引，问你访问几次磁盘I/O？
        • 那么答案就是【N+1】，N是放在磁盘需要调入内存的【索引表】、1是最后去磁盘取出【数据块】
      • 还有一个知识点：记住【磁盘索引节点】和【内存索引节点】的区别就是有没有【访问计数值】！！！

  • ③ 混合索引

    • 我真不知道怎么写这个笔记，自己看吧，然后等会在例题里找到做一下
    • 【例题】
• 本小点提示：
• 然后注意，【索引分配】是最牛逼的！！！！
  • 它支持【随机存取（直接访问）】！！！
    • 因为它的索引表能快速指向对应的数据块，哪怕多级索引，层层一对一指向依旧很快！！！
  • 也支持【任意拓展（插入、删除）】！！！
    • 不管插入删除，直接去索引表修改就行！！只用改索引表！！

4、【逻辑结构】和【物理结构】区分

• 大概思维导图框架：

  • 混淆点1：【顺序文件】的【顺序存储】和【链式存储】

    • 记住【顺序文件】作为逻辑结构概念，它只是人类视角的一个数据结构
    • 那么实际物理上，当然允许【顺序存储】或【链式存储】

  • 混淆点2：【链式文件】的【链式分配】

    • 还是一样，【链式文件】是用户逻辑结构概念，【链式分配】是操作系统的物理结构概念

  • 混淆点3：【索引文件】的【索引分配】

    • 还是一样，【索引文件】是用户逻辑结构概念，【索引分配】是操作系统的物理结构概念

• 总结：逻辑结构VS物理结构——服务对象

  • 【逻辑、物理结构】的本质就是看【这个结构是为了给谁服务？为了让谁看得懂？】

• 【随机存取】问题！！！

  • 内容这么多，考试怎么记得起来谁可以随机存取？谁不可以？？诀窍如下：
  • 另外关于【隐式链接】、【显式链接】、【索引链接】这三很像的玩意我也做了总结：所谓【随机存取】特指【针对外存磁盘访问可否直接一步到位】

5、【逻辑 和 物理结构】例题

重点重点！！

 

【关于各个物理结构性能对比】

 记住这些特点：

• 【综合战力：索引表是神，六边形全能战神】
• 然而从【随机（直接）访问】的角度来看：
  • 【连续分配（数组）才是神】
  • 【最垃圾：链式】
• 从【插入、删除、拓展角度】：
  • 【索引】、【链式】是神
  • 【连续、顺序分配】最垃圾

     

    

    

    

【综合拓展：记录成组分解技术！！！】

注意不要跟【成组连接分配】概念混淆：

• 【成组链接分配】：下一章节学的【文件外存存储空间分配】的内容
• 【记录成组分解技术】：
  • 1个盘块只能存【完整的记录】
  • 若还有剩余的空闲区不够一个完整记录的大小，直接不要了，不可以用来存一个记录的一部分
  • 而下一个记录直接另起一个磁盘块记录

【超级索引大难题，看不懂题目就死，看懂了巨简单】

 这种题：

• 第一件事：找到【1个 文件快 / 磁盘块 / 数据块 / 索引块 多大】、【1个 指针 / 块号 / 地址 占多大】
  • 【1个索引块大小】/ 【1个 指针 / 块号 / 地址】=【1个索引块有几个表项】
• 第二件事：判断具体某几块是【直接地址】？【间接地址（一级？二级？）】
  • 【直接地址】的块，有N个表项就【有N个数据块】
  • 【间接地址】的块，N个表项对应N个下一级索引块，最后一层索引块的N个表项才是对应N个数据块
    • 故N个表项，有m级间接索引的话，【数据块就有 N^(m-1)】

• 【这一题是 “3层” + “混合索引” 的真题！！！！】
  • 【王道的图】：我个人看得不是很舒服
  • 【我重新画的图】：非常清晰
  • 【升级版真题，SB老头真是要死】
• 学了前面的，这里就简单了
  • 回忆【索引节点】知识点（FCB的改进版）