6.2 KiB
6.2 KiB
好，直接给你一版**“一屏吃透文件系统数据结构”**，从最底层磁盘组织 → inode → 数据块索引 → 目录结构 → 空闲空间管理 → 现代高级结构，一次性压满信息密度，尽量做到你说的“每屏最大信息量”。
一、文件系统的本质抽象（先立一个统一模型）
你可以把整个文件系统抽象成三张核心表：
(1) inode表： inode_id → metadata（权限/大小/时间/指针）
(2) 数据映射： (inode_id, offset) → block
(3) 目录映射： (parent_inode, filename) → inode_id
👉 所有“文件结构”本质都在优化这三件事：
- 如何表示文件数据（第2条）
- 如何快速查找文件名（第3条）
- 如何管理空间（块分配）
二、文件数据的组织方式（核心重点）
1️⃣ 连续分配（Contiguous Allocation）
inode:
start_block
length
[block100][block101][block102][block103]...
✔ 优点：
- 顺序读写极快（完美局部性）
- 实现简单
✘ 缺点：
- 文件增长困难（需要搬迁）
- 外部碎片严重
👉 现在基本不用（但思想在 extent 里复活）
2️⃣ 链式分配（Linked Allocation）
block100 → block500 → block20 → block9 ...
inode 只存：
first_block
✔ 优点：
- 无外部碎片
- 动态扩展容易
✘ 致命问题：
- 随机访问 O(n)
- 每个block都要存指针（浪费）
- cache locality 极差
👉 FAT 文件系统就是这个思路（用数组模拟链表）
3️⃣ FAT（File Allocation Table）
本质：
FAT[block] = next_block
FAT:
100 → 500
500 → 20
20 → EOF
✔ 优点：
- 比链式更容易管理
- 支持随机访问（通过表）
✘ 问题：
- FAT表巨大（必须常驻内存）
- 可靠性差（单点损坏）
4️⃣ 多级索引（inode经典结构，ext2/3）
inode结构：
inode:
direct[12]
indirect
double_indirect
triple_indirect
访问逻辑：
offset → 第几个block → 走指针树
结构：
inode
/ | \
direct indirect double
|
[block pointers]
✔ 优点：
- 支持大文件
- 随机访问 O(1)（理论）
✘ 问题：
- 小文件浪费指针
- 大文件访问多次IO（多级跳转）
👉 这是 UNIX 经典设计
5️⃣ Extent（现代主流，ext4）
核心思想：
👉 不记录“每个block”，而记录“连续区间”
extent:
(logical_start, physical_start, length)
例：
(0, 100, 50) // 文件0-49 → 磁盘100-149
结构：
inode
└── extent tree
✔ 优点：
- 极大减少元数据
- 顺序读写性能好
- 减少碎片
👉 本质：连续分配的升级版 + 树结构管理
6️⃣ B-tree / B+tree（XFS / Btrfs）
[key]
/ | \
child child child
key可能是：
(file_offset → block)
✔ 优点：
- O(log n) 查找
- 高扇出 → 极少IO
- 适合大规模数据
👉 XFS：extent索引用B+tree 👉 Btrfs：所有东西都是B-tree
7️⃣ Copy-on-Write（Btrfs / ZFS核心）
写数据时：
旧块不改 → 写新块 → 更新指针
结构：
旧树 ----\
\--> 新树（部分共享）
✔ 优点：
- snapshot免费
- 崩溃一致性好
- 支持版本回滚
✘ 缺点：
- 写放大
- 碎片增加
三、目录结构（名字 → inode）
1️⃣ 线性表（ext2早期）
"file1" → inode 10
"file2" → inode 20
查找：
O(n)
2️⃣ 哈希表（HTree，ext4）
hash(filename) → bucket → inode
结构：
root
/ \
bucket bucket
✔ 平均：
O(log n)
3️⃣ B-tree目录（XFS / Btrfs）
filename → inode
用B+tree组织：
✔ 优点：
- 有序（支持range scan）
- 高效查找
四、空闲空间管理（磁盘怎么分配）
1️⃣ 位图（bitmap）
1 = used
0 = free
001011000100...
✔ 优点：
- 查找连续空间方便
- 实现简单
2️⃣ 空闲链表
free → free → free
✘ 问题：
- 找连续空间困难
3️⃣ 分组（grouping）
一次记录多个空闲块：
block → [free1, free2, free3...]
4️⃣ B-tree管理（现代FS）
free_extent:
(start, length)
用树管理：
✔ 高效查找大块连续空间
五、日志（Journaling）
目的：
👉 防止系统崩溃导致文件系统损坏
流程：
写日志 → 提交 → 写实际数据
模式：
- write-ahead logging
- metadata journaling（ext4默认）
- full journaling（慢但安全）
六、把所有结构统一成一张“全景图”
用户操作:
open("/a/b/file")
↓ 路径解析
目录结构（HTree / B-tree）
(parent_inode, name) → inode
↓ inode
inode table
↓ 数据定位
extent / B-tree / indirect block
↓ block
page cache → disk
↓ 磁盘
物理block
七、一句话总结（给你压缩记忆）
文件系统 = inode + 数据索引结构 + 目录索引 + 空闲管理 + 一致性机制
演化路径：
连续 → 链式 → FAT → inode多级索引 → extent → B-tree → CoW
八、你现在应该形成的“认知模型”（很重要）
你可以这样理解：
早期FS：像数组 + 指针
现代FS：像数据库（KV + B-tree + WAL）
九、如果你继续往下深挖（我建议你下一步搞这个）
下一步最关键的是搞清楚：
👉 一次 read() 发生了什么：
用户态
→ VFS
→ dentry cache
→ inode cache
→ page cache
→ block layer
→ IO scheduler
→ disk
这个链路一通：
👉 文件系统 + 虚拟内存 + IO 子系统就串起来了
如果你下一步想继续，我可以给你一版：
👉 “从 open 到 read 到 page cache 命中/缺页的全流程 + 内核数据结构图（task_struct / file / inode / dentry 全串）”
那个是操作系统理解的分水岭。