操作系统文件管理详解：索引文件结构与多级索引方式
操作系统文件管理详解：索引文件结构与多级索引方式
操作系统中的文件管理是计算机科学中的一个重要领域，其中索引文件结构和各种索引方式（直接索引、一级间接索引、二级间接索引和三级间接索引）是其核心内容。本文将详细介绍这些概念的原理、实现方式以及在软考中的考点分析。
一、索引文件结构 简介
1、索引文件结构 原理
索引文件结构是一种高效的文件存储管理方式，通过引入索引表实现对文件数据块的快速定位和随机访问。索引文件结构解决了文件数据顺序存储和链式存储的随机访问效率低、扩展性差等局限性，现代的文件系统都是基于索引文件结构进行设计的。
索引文件结构设计思想：为每个文件分配一个独立的索引块，索引块中直接或间接存储该文件所有数据块的物理地址。
- 数据访问方式：文件访问时，先通过索引块找到目标数据块的物理位置，再直接访问数据。
- 支持随机访问（文件访问）：通过索引表快速定位数据块。
- 支持动态扩展（文件写出）：灵活分配数据块。
2、索引文件结构 关键部件
索引文件结构关键部件：
- 文件控制块：包含文件元数据，如大小、权限等，并指向索引块。
- 索引块：存储文件所有数据块的物理地址/指针/物理块号。
- 数据块：实际存储文件数据内容的物理块。
3、索引结构的操作流程
文件读取操作流程：该过程就是随机访问操作。
- 路径访问：用户通过逻辑路径访问文件。
- 查找控制块：操作系统查找inode文件控制块。
- 计算块号：根据逻辑偏移量计算目标数据块号，逻辑偏移量/块大小=数据块号。
- 查询索引：查询索引块，找到对应的物理地址。
- 访问数据：直接访问目标数据块。
文件写出操作流程：该过程就是动态扩展操作。
- 查找空闲数据块：查找空闲数据块并分配给文件。
- 更新直接索引/间接索引：更新索引块，
- 直接索引：如果直接索引块块没用完，直接添加新数据块的物理地址作为直接索引。
- 间接索引：如果直接索引块已满，分配新的间接索引块并更新上级索引。
二、索引方式 简介
1、索引结点
在LINUX/UNIX系统中，每个文件默认有13个索引结点，结点编号是0~12，每个编号中放置的就是索引地址，索引地址存储的是物理块号，指向具体的物理盘块。
2、直接索引 和 间接索引
直接索引：又称为单级索引，索引块直接存储所有数据块的物理地址（物理块号）。
- 适用场景：小文件存储，如文本文件、配置文件。
- 优点：访问速度快，只需一次索引查询，实现简单。
- 缺点：索引块大小固定，无法支持大文件，若文件需要的数据块数超过索引块容量，则需其他机制扩展。
间接索引：又称为多级索引，通过多级索引块间接定位数据块，支持大文件存储。
- 优点：支持超大文件，扩展性强，平衡存储效率和访问速度。
- 缺点：多级索引需要多次磁盘访问，如二级索引需访问索引块两次。
3、直接索引方式
直接索引方式：13个索引结点中，前10个索引结点，对应的节点编号是0~9，这10个索引结点都是"直接索引"，直接索引就是索引地址直接指向物理块，这些物理块中存放的就是文件数据。
每个直接索引指向一个物理块（存放文件数据）。
直接索引方式不经过地址跳转，直接就可以找到文件数据。
0~9号索引结点（直接索引表）->文件数据
参考下图红色矩形框部分：
4、一级间接索引方式
一级间接索引方式：第10号索引结点的索引方式是"一级间接索引方式"，该索引结点指向的物理块中存放的是一级地址索引表，包含n个直接索引。
每个10号索引结点指向一个物理块（存放一级间接索引表），存放直接索引地址。
一级间接索引方式经过1次地址跳转可以找到文件数据。
10号索引结点->一级间接索引表->文件数据
参考下图红色矩形框部分：
5、二级间接索引方式
二级间接索引方式：第11号索引结点的索引方式是"二级间接索引方式"，该索引结点指向的物理块中存放的是n个一级间接索引。
每个11号索引结点存储的索引指向一个物理块，存放二级间接索引表，
每个二级简介索引表存放的是n个一级间接索引表的索引地址。
每个一级间接索引表有n个直接地址，直接地址指向一个物理块（存放文件数据）。
二级间接索引方式经过2次地址跳转可以找到文件数据。
11号索引结点->二级间接索引表->一级间接索引表->文件数据
参考下图红色矩形框部分：
6、三级间接索引方式
三级间接索引方式：
第12号索引结点的索引方式是"三级间接索引方式"，该索引结点指向的物理块中存放的是三级间接索引表，对应n个二级间接索引表。
每个二级间接索引表指向一个物理块（存放一级间接索引表），存放的是n个一级间接索引，
每个一级间接索引指向一个物理块（存放直接索引），存放n个直接索引，
每个直接索引指向一个物理块（存放文件数据）。
三级间接索引方式方式经过3次地址跳转可以找到文件数据。
12号索引结点->三级间接索引表->二级间接索引表->一级间接索引表->文件数据
三、软考考点
1、不同索引方式指向对象
不同的索引方式，指向的对象是不同的，索引指向对象分为以下两类：
- 数据块：0~9号直接索引指向数据块。
- 索引表：
- 10号索引结点指向一级间接索引表。
- 11号索引结点指向二级间接索引表。
- 12号索引结点指向三级间接索引表。
在索引结点表/一级间接索引表（直接索引表）/二级间接索引表/三级间接索引表都可以理解成一个数组元素，
上述数组元素存储的内容是物理块号，可以理解成地址或指针，根据这个物理块号/地址/指针可以找到一个物理块，这个物理块中存放数据块或索引表；
如下图所示：在索引结点或者间接索引表中存储的都是物理块号；
- 在第0号索引结点存储的是108，指向物理块号为108的物理块；
2、不同索引方式访问磁盘次数分析
不同索引方式访问磁盘次数分析：
- 直接索引：只需要访问一次数据盘，直接查看磁盘中的数据即可。
- 一级间接索引：访问1次索引盘，1次数据盘，总共访问2次磁盘。
- ①第一次访问磁盘：访问索引盘（一级间接索引表），从一级间接索引表中找到直接索引。
- ②第二次访问磁盘：访问直接索引指向的物理块。
- 二级简介索引：访问2次索引盘，1次数据盘，总共访问3次磁盘。
- ①第一次访问磁盘：访问索引盘（二级间接索引表），从二级间接索引表中找到一级间接索引表所在的物理块。
- ②第二次访问磁盘：访问索引盘（一级间接索引表），从一级间接索引表中找到直接索引。
- ③第三次访问磁盘：访问直接索引指向的物理块。
- 三级简介索引：访问3次索引盘，1次数据盘，总共访问4次磁盘。
- ①第一次访问磁盘：访问索引盘（三级间接索引表），从三级间接索引表中找到二级间接索引表所在的物理块。
- ②第二次访问磁盘：访问索引盘（二级间接索引表），从二级间接索引表中找到一级间接索引表所在的物理块。
- ③第三次访问磁盘：访问索引盘（一级间接索引表），从一级间接索引表中找到直接索引。
- ④第四次访问磁盘：访问直接索引指向的物理块。
3、文件逻辑位置计算
文件数据在逻辑位置上是连续的，在物理位置上可以是分散的；
下图红色矩形框中，就是文件的逻辑位置；
① 连续 逻辑位置
连续逻辑位置的理解：
09号索引结点分别指向文件的前10个物理块，对应文件的逻辑上的序号为09的10个物理块；
第10号索引结点指向一级间接索引表，其中有个直接索引，每个直接索引指向一个物理块存储文件数据，对应文件的逻辑上的序号为10~n+9的个物理块；
第11号索引结点指向二级简介索引表，其中对应个一级间接索引表，每个一级间接索引表有个直接索引，每个直接索引指向一个物理块存储文件数据，对应文件的逻辑上的序号为n+10~n+9+nxn的nxn个物理块；
② 一级间接索引 计算
10号索引结点指向一个物理块，该物理块中存储一级间接索引表，该表中存放的物理块号是固定的；
假设每个物理块的大小固定为1KB=1024B，每个物理块号占4B（4字节）大小，
物理块号就是物理块地址/索引值，
那么一个物理块中可以存储1024/4=256个索引值；
在下图计算中，第10节点指向的物理块中存储的是一级间接索引表，该物理块存储了256个直接索引，对应文件中的第10~265序号的逻辑物理块，对应256个文件块；
③ 二级间接索引 计算
11号索引结点指向一个物理块，该物理块中存储二级间接索引表，该表中存放的物理块号/索引个数是固定的；
在上个章节已经计算出，每个物理块可存储256个索引值；
二级间接索引表对应着256个一级间接索引表，每个一级间接索引表指向一个物理块，又对应一个一级间接索引表，其中又存放着256个直接索引，进而对应256个存放文件数据的物理块；
第11节点指向二级间接索引表，其中索引指向256个一级间接索引表，每个一级间接索引表包含的索引指向256个直接索引，
则该索引结点间接指向的物理块有256x256=65536个，对应文件中的第266~65801序号的逻辑物理块，对应65536个文件块；
④ 三级间接索引 计算
第12节点指向的三级间接索引表，包含的索引指向256个二级间接索引表，每个二级间接索引表包含的索引分别指向256个一级间接索引表，每个一级间接索引表包含256个直接索引，
则该索引结点间接指向的物理块有256x256x256=256^3=16,777,216个，
对应文件中的第65802~(65801+256^3=16,843,017)序号的逻辑物理块，
对应256^3个文件块；
4、文件长度计算
假设每个物理块的大小固定为1KB=1024B，每个物理块号占4B（4字节）大小，一个物理块中可以存储1024/4=256个索引值；
0~9号直接索引方式，可以表示10KB大小的文件；
10号一级间接索引方式，指向256个文件块，可以表示256KB大小的文件；
11号二级简介索引方式，指向256x256个文件块，可以表示65536KB大小的文件；
12号三级间接索引方式，指向256^3个文件块，可以表示256^3KB大小的文件，等于16384MB=16GB大小的文件；
四、软考案例
下图是一个索引文件示意图，文件有8个索引结点，分别是i-addr[0]~i-addr[7]；
- 直接索引：i-addr[0]~i-addr[4]
- 一级间接索引：i-addr[5]~i-addr[6]
- 二级简介索引：i-addr[7]
索引盘和数据块的物理块大小为1KB，每个索引地址值为4字节；
文件的逻辑块号从0开始计数，在最右侧的文件块依次向下累加，将文件的逻辑号标记在下图的最右侧文件块中；
- 直接索引：i-addr[0]
i-addr[4]是直接索引，直接指向存放文件数据的物理块，对应04序号的逻辑文件块； - 一级间接索引：
- i-addr[5]是一级间接索引方式，指向一级间接索引表，包含256个直接索引，分别指向256个文件块，对应的文件块的逻辑序号为5~260这256个逻辑块；
- i-addr[6]是一级间接索引方式，指向一级间接索引表，包含256个直接索引，对应的文件块的逻辑序号为261~516这256个逻辑块；
- 二级简介索引：i-addr[7]是二级间接索引方式，指向二级间接索引表表，包含的256个索引分别指向一级间接索引表；一级间接索引表，包含256个直接索引，分别指向256个文件块；
- 对应的文件逻辑序号为517~66052的65536个逻辑块；
该文件最多可以存储65536+256+256+5=66053个文件块，每个1KB，则文件最多66053KB大小；
物理块索引表名称：
- 90号/91号/156号/168号物理块中，存储的是一级地址索引表；
- 101号物理块中，存储的是二级地址索引表；