简介

操作系统的文件管理负责都计算机中的数据(文件和目录)进行组织，存储，检索，保护，共享。
其核心目标为：

高效存储
减少I/O开销，提升读写速度
数据完整
确保文件不被非法破坏
用户透明
隐藏底层细节，比如磁盘的物理指针，提供统一的API。
多用户支持
支持并发访问，权限控制和资源共享。

文件的逻辑结构

所谓文件逻辑结构，就是对用户或者GUI而言，文件内部的数据是如何呈现的。

无结构文件
文件内部数据就是一系列二进制流或字符流组成。比如txt文件，只是简单的文字表达，并无特殊结构。

int main()
{
    FILE *fp=fopen("test.txt","r");
    if(fp==NULL){
        printf("文件打开报错");
        return 0;
    }

    fseek(fp,10,SEEK_SET);//移动指针到制定位置
    char c=fgetc(fp);//从指定位置读取信息，底层使用read系统调用，实现了逻辑块号到物理块号的转换
    printf("value=%c",c);
    fclose(fp);
    return 0;
}

有结构文件
有一组组相似结构的数据组成，比如excel的统计表，比如数据库
根据每一组数据的长度不等，又分为定长记录和不定长记录

从其特性出发，定长记录=数组，可以实现随机访问，偏移量 = i × 记录长度
不定长记录=链表，无法随机访问。

文件目录，从文件名到 inode 的映射

目录本身就是一种有结构的文件，由一条一条记录组成。这个记录叫做File Control Block,FCB。
FCB中包含了文件的基本信息，权限信息，使用信息等。

眼见为实

单级文件目录

早期操作系统不支持多级目录，整个系统只建立一张目录表，每个文件占一个目录项。
因为这个特性，文件是不允许重名的。

二级文件目录

为了解决文件不允许重名的问题，又优化出了二级文件目录。
分为主文件目录(Master File directory,MFD)和(User File Directory)

两级目录允许不同用户的文件重名，但依旧缺乏灵活性。因为不能对自己的文件进行分类

多级目录结构

为了解决多用户，文件分类的问题。又优化出多级目录结构。
系统根据文件路径一级一级的向下查找，先从root开始，再找到照片目录，再找到2025/4/15目录。这个过程需要3次I/O操作。比较低效，因此可以设置一个"当前目录"，来减少I/O操作。

这就是绝对路径与相对路径的由来，与产生原因。，可以理解为一个链表，如果持有了上一个节点，就能很快找到当前节点，否则就要从表头开始遍历。

到目前为止，树形目录结构可以很方便的对文件分配，也支持多用户，结构也很清晰。但依旧存在一个缺点，树形结构不便于实现文件共享。

眼见为实

linux下，绝对路径与相对路径:

无环图目录结构

为了解决文件共享的问题，又衍生出了无环图目录结构。本质上是一个单向但不形成环的图。

眼见为实

关于图的数据结构，可以参考https://www.cnblogs.com/lmy5215006/p/18757481

用索引节点强化无环图目录结构

在FCB的结构中，往往包含了大量信息。但在查找各级目录的过程中，只需要用到"文件名"来做匹配。
因此，可以考虑让目录表"瘦身"来提高效率。

加入一个FCB占用64B，一个磁盘block是1kb，那么就只能放16个FCB，。如果一个目录下有640个FCB，那么就占用40个磁盘block ，时间复杂度为O(n/2) 也就是I/O平均下来要20次读写。
而使用索引节点，文件名占14B，节点指针占2B，那每个磁盘block就可存储1024/(14+2)=64，640个FCB，只占用10个磁盘block，I/O读写降低为5.

眼见为实

文件的物理结构

文件的物理结构，指的是在系统看来，文件的数据是如何存储在外存当中的。

外存管理与内存管理师出同门，与内存分页类似，磁盘的存储单元也会被分为一个个的block。

在很多操作系统中，磁盘块与内存页框保持大小一致，目的是为了数据交换时，因为大小，所以只需要一次I/O操作

文件分配方式

万物皆套路，本身上与内存分配方式思想并无区别。故只简单描述

连续分配(Contiguous Allocation)
原理：将文件在磁盘上分配为一组连续的物理块，文件的逻辑块号(Logical Block Number,LBN)，对应磁盘上连续的物理块号(Physical Block Number,PBN)。
优点：访问速度快，支持随机访问。比如PBN=起始块号+LBN
缺点：磁盘碎片，动态扩容复杂。

数组的优/缺点就是它的优/缺点。
早期文件系统或对访问速度要求高且文件大小固定的场景（如可执行文件）

隐式链接分配（Linked Allocation）
将文件分散存储在非连续的物理块中，通过指针（链接）记录块间顺序。
原理：为每个文件记录起始块号与结束块号，并在每个数据块末尾记录下一个块的指针。熟悉链表的朋友不会陌生，它就是一个拥有头/尾节点的单链表
优点：无外部碎片，动态扩展容易
缺点：无法随机访问，只能顺序访问。效率低O(n)

链表的优/缺点就是它的优/缺点
早期 Unix 文件系统（如 UFS）的非索引节点分配方式

显式链接（Explicit Linking）
原理：将所以块的链接指针集中存储在一张文件分配表中(File Allocation Tab,FAT)中，磁盘的每个块对应一个item，并记录它的下一个块号。
优点：通过 FAT 表直接查找块号，无需遍历。可以常驻内存提交搜索效率，不再需要I/O操作。
缺点：FAT表占用空间，有兼容性问题(FAT16,FAT32)

Windows 的 FAT 文件系统、早期数码相机存储卡。

索引分配（Indexed Allocation）
原理：索引块是一个物理块，其中每个表项对应一个数据块的物理地址。文件的逻辑块号对应索引块中的表项索引。
优点：直接通过索引查找，时间复杂度O(1)，无碎片，新增数据库不需要移动数据。
缺点：维护索引块本身就有开销

当文件过大时，单级索引块可能不足。又衍生出了多级索引，混合索引。比如linux的inode结构

特性	连续分配	链接分配（隐式）	索引分配（单级）
空间连续性	连续	不连续	不连续
随机访问支持	高效（O(1)）	低效（O(n)）	高效（O(1)）
碎片问题	外部碎片严重	无外部碎片	无外部碎片
动态扩展能力	差（需整块搬迁）	好（追加块）	好（修改索引）
元数据开销	低（仅起始块+长度）	中（每个块含指针）	高（索引块）
典型应用	早期 FAT、固定文件	早期 Unix 非索引节点	Linux ext2/ext3、NTFS

逻辑结构vs物理结构

特征	逻辑结构	物理结构
视角	在用户看来，占用连续的逻辑地址	在系统看来，系统决定连续结构 or 离散结构
关注点	数据的排列，访问方式	存储设备的物理布局，块分配策略
与存储介质	无关，它是抽象结构	有关，它依赖磁盘扇区，块大小
目标	方便用户操作	高效利用I/O设备

Linux 的 ext4 文件系统使用索引分配（inode 记录直接 / 间接块）
Windows 的 NTFS 使用混合索引（MFT 表记录文件属性和索引）
FAT 文件系统使用显式链接分配（FAT 表记录块链接）