一、整体概述
1.外存管理两大核心任务

1. 已用磁盘块管理：文件数据如何存放在磁盘上 → 文件物理结构/文件分配方式（本节重点）。
2. 空闲磁盘块管理：磁盘空闲空间如何分配与回收（后续章节）。

2. 基础前置知识

1. 磁盘块（物理块）
   磁盘被划分为大小相等的存储单元，统一编号（0、1、2……）；磁盘与内存的数据交换以块为单位。
   多数系统会让磁盘块大小 = 内存页面大小，简化内外存数据交互。
2. 文件逻辑块
   文件的逻辑地址空间划分为等大的逻辑块，文件逻辑地址 = 逻辑块号 + 块内地址，类比内存「页号+页内地址」。
   ￮示例：磁盘块大小1KB，1MB文件 = 1024KB，分为 1024个逻辑块（块号 0~1023）。
   ￮核心工作：操作系统负责将逻辑块号映射为物理块号，块内地址无需转换。
3. 三大文件分配方式
   文件在磁盘的存储分为三类：连续分配、链接分配、索引分配；
   其中链接分配细分：隐式链接、显式链接（FAT）。

二、连续分配（顺序分配）
1.核心思想
一个文件占用磁盘上一组连续的物理块，逻辑相邻的块，物理位置也相邻。

2. 目录项（FCB）记录内容
文件目录项中仅需保存两个信息：
•文件起始物理块号
•文件占用块数（文件长度）

3. 地址映射公式
物理块号 = 起始块号 + 逻辑块号
例：文件起始块号4，访问逻辑块号2 → 物理块号 = 4+2=6。
系统同时会校验逻辑块号是否越界（防止非法访问）。

4. 访问特性
同时支持 顺序访问 + 随机（直接）访问。

5. 优缺点
✅ 优点
1.顺序访问速度最快：物理块连续，磁头移动距离最短，磁盘IO开销小。
2. 支持随机访问，地址计算简单。

❌ 缺点
1.文件拓展困难：文件后方物理块若被占用，只能整体迁移文件，开销极大。
2. 产生外部磁盘碎片：离散空闲小块无法分配给大文件，磁盘利用率低。
3. 碎片处理只能用「紧凑」，需要大量移动数据，耗时高。

三、链接分配（离散分配）
整体思想：文件拆分到离散的物理块，通过指针将所有块串联起来，无外部碎片，文件拓展方便。
分为隐式链接、显式链接两类。
（一）隐式链接
1.结构规则

1. FCB（目录项）记录：文件起始块号、结束块号。
2. 每个物理块内部预留空间，存放下一个块的指针；最后一块指针标记为结束（无后继）。
3. 指针对用户透明。

2. 地址访问流程
访问逻辑块号i：必须从起始块开始，依次读取 0~i-1 号块，顺着指针找到第i块。
•访问第i块，需要执行 i+1 次磁盘IO。

3. 访问特性
仅支持顺序访问，不支持随机访问，查找效率低。

4. 优缺点
✅ 优点
1.物理块离散分配，无外部碎片，磁盘利用率高。
2.文件拓展简单：直接分配空闲块，挂在链表尾部，修改FCB结束块号即可。
❌ 缺点
1.不支持随机访问，随机查找效率极低。
2.每个块需要额外空间存储指针，占用存储资源。
3.链条断裂风险：任意一块损坏，后续所有数据都无法访问。
补充：题目只写「链接分配」，未特殊说明时，默认指隐式链接。

（二）显式链接（FAT 文件分配表）
1.核心结构

1. 整张磁盘仅设置一张全局文件分配表（FAT），一个磁盘分区对应一张FAT表。
2. FAT表常驻内存（开机读入，全程不换出），表项数量 = 磁盘总物理块数。
3. 表项作用：记录每一个物理块的下一块物理块号；文件末尾块标记特殊值（如-1）。
4. FCB仅记录文件起始物理块号。

2. 地址访问流程

1. 根据文件名找到FCB，获取文件起始块号。
2. 在内存FAT表中顺着表项查找后继块号，全程无需访问磁盘。

3. 访问特性
同时支持顺序访问 + 随机访问，查询效率远高于隐式链接。

4. 优缺点
✅ 优点
1.无外部碎片，文件拓展方便。
2.FAT常驻内存，查表速度快，支持随机访问。
❌ 缺点
整张FAT表需要占用大量内存空间，磁盘分区越大，FAT表开销越高。

四、索引分配
1.核心思想

1. 离散分配物理块，为每一个文件单独建立一张索引表（类比内存页表）。
2. 索引表：记录「逻辑块号 → 物理块号」的映射关系。
3. 分类：
   ￮索引块：存放索引表的磁盘块。
   ￮数据块：存放文件真实数据的磁盘块。
4. FCB（目录项）仅记录：该文件索引块的物理块号。
   区分：显式链接是整个磁盘一张FAT表；索引分配是每个文件一张独立索引表。

2. 基础索引（单级索引）
1）访问流程

1. 从FCB读出索引块号，将索引块读入内存。
2. 查询索引表，直接得到目标逻辑块对应的物理块号。
3. 读取目标数据块。

2）访问特性
支持随机访问，文件拓展简单（新增数据块，同步追加索引表项即可）。

3）局限性
单个磁盘块容量有限，能存放的索引项数量固定。

举例：磁盘块1KB，单个索引项占4B → 单块最多存放 256个索引项，仅能对应256个数据块。
若文件过大，索引表无法存入单个索引块，需使用扩展方案：索引链接方案、多级索引、混合索引。

3. 索引表过大的三种解决方案
方案1：索引链接方案
•规则：索引表拆分为多个索引块，索引块之间用指针链接。

•缺点：访问靠后的索引项，需要顺序读取前面所有索引块，磁盘IO次数多，效率低。

方案2：多级索引（多层索引）
•原理：和多级页表一致，一级索引块指向二级索引块，大文件可继续拓展三级、四级索引。

•核心考点1：计算文件最大长度
前提：每一个索引块能存放的索引项数量固定。

例：单块存256个索引项
￮二级索引：最大数据块数 = 256 × 256
￮三级索引：最大数据块数 = 256 × 256 × 256

•核心考点2：计算磁盘IO次数
若顶级索引块未载入内存：K级索引 → 访问数据共需要 K+1 次磁盘读操作。

•缺点：无论文件大小，都要走完多级索引流程，小文件访问IO次数偏多。

方案3：混合索引（主流方案）
•原理：结合「直接索引 + 一级间接索引 + 二级间接索引……」，兼顾大小文件效率。
a.直接索引：索引项直接指向数据块，访问最快（小文件优先使用）。
b.一级间接索引：索引项指向单层索引块，再由索引块指向数据块。
c.二级/多级间接索引：用于超大文件。

•优势：
a.小文件使用直接索引，磁盘IO次数少，访问速度快。
b.多级间接索引支撑超大文件，兼顾容量。

•核心考点：
a.分段计算文件最大长度（直接索引区+各级间接索引区总和）。
b.按逻辑块号所在区间，判断使用哪类索引，计算对应磁盘IO次数。

五、四大分配方式综合对比（复习重点）

补充易错点

1. 链接分配默认指隐式链接，做题需注意题干描述。
2. 显式链接：一个磁盘分区 = 一张FAT表，FAT常驻内存。
3. 索引分配：一个文件 = 一张独立索引表。
4. 多级/混合索引两大必考题型：文件最大长度计算、访问磁盘IO次数计算。

六、小节总结
1.外存以磁盘块为基本读写单位，文件逻辑地址划分为逻辑块，系统完成逻辑块→物理块映射。
2.连续分配：连续块，速度快、有碎片、难扩容。
3.链接分配（离散块）
￮隐式链接：块内自带指针，仅顺序访问。
￮显式链接：全局FAT表，常驻内存，支持随机访问。
4.索引分配：每个文件独立索引表，支持随机访问；大文件可采用链接索引、多级索引、混合索引优化。
5.混合索引是现代系统主流，完美适配日常「小文件居多、存在超大文件」的场景。