简介
操作系统的文件管理负责都计算机中的数据(文件和目录)进行组织，存储，检索，保护，共享。
其核心目标为：
- 高效存储
减少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 表记录块链接）
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
