假设你有一个 1TB 的数据库文件，应用层发起
pread(fd, buf, 4096, 847293510144)——读取文件偏移量约
789GB 处的一个 4KB
页。内核需要把这个逻辑偏移量翻译成物理磁盘块号，然后发起块
I/O。
这个翻译必须快。数据库每秒可能发起几十万次随机读，每次都要做一次逻辑到物理的映射。O(n) 遍历？不可能。O(1) 直接索引？文件太大，索引本身就放不下。
答案是树。几乎所有现代文件系统都用某种形式的树来组织磁盘上的元数据。但”用什么树”和”怎么用”，各家文件系统的选择截然不同——ext4 用 extent tree，XFS 用 B+tree，btrfs 用 CoW B-tree，ZFS 用间接块树，F2FS 用 NAT 表加节点树。
这篇文章从最底层的数据结构出发，逐一拆解五种主流 Linux 文件系统的树形结构设计，对比它们的权衡取舍，以及在真实工程中踩过的坑。
一、为什么文件系统需要树
最朴素的方案：直接映射
最简单的文件系统可以把整个文件连续存放在磁盘上——文件的第 N 个块就是磁盘上起始块号加 N。这就是 FAT 文件系统的连续分配模式。
问题很明显：文件增长时如果后面的空间被占了怎么办？要么移动整个文件（代价极高），要么不允许文件增长。
所以现代文件系统都允许文件的块不连续存放。但一旦允许不连续，就需要某种数据结构记录”逻辑块 L 对应物理块 P”的映射关系。
间接块映射：ext2/ext3 的方案
ext2/ext3 的 inode 里有 15 个块指针：
inode {
i_block[0..11] → 直接块（12 个）
i_block[12] → 一级间接块
i_block[13] → 二级间接块
i_block[14] → 三级间接块
}以 4KB 块大小为例，每个块能存 1024 个 32 位块号（4096 / 4 = 1024）：
- 直接块：12 x 4KB = 48KB
- 一级间接：1024 x 4KB = 4MB
- 二级间接：1024 x 1024 x 4KB = 4GB
- 三级间接：1024 x 1024 x 1024 x 4KB = 4TB
理论上能表示最大 4TB 的文件。但问题在于：
- 元数据开销：一个 4GB 的文件需要 1 个一级间接块 + 1024 个二级间接块，光元数据就要 4MB 多。
- 随机访问深度：访问文件末尾的块需要 3 次额外的磁盘读取（三级间接 → 二级间接 → 一级间接 → 数据块）。
- 大量连续块的浪费：如果文件是顺序写入的，块 0 到块 999999 可能是连续的物理块，但 ext2/ext3 仍然要逐个记录每个块号。
第三点是最致命的。现代硬盘上，顺序分配是常态——一个 1GB 的文件可能就是连续的 262144 个 4KB 块。用间接块方案，需要 262144 个 32 位指针（1MB 的元数据）来记录这个完全规律的映射。
树的必要性
解决方案很自然：不要逐块记录，而是记录连续区间（extent）。一个 extent 表示”从逻辑块 L 开始的 N 个块，映射到物理块 P 开始的 N 个连续块”。一个 1GB 的连续文件只需要一个 extent。
但 extent 的数量可能很多（碎片化的文件），所以需要一种数据结构来高效地存储和查找 extent。自然的选择就是树——B-tree 或其变体。
我个人认为，文件系统树的设计是操作系统中最能体现”数据结构即工程”的地方。这不是教科书上的抽象 B-tree，而是要在固定大小的磁盘块里塞下尽可能多的索引条目，同时保证崩溃一致性，还要和磁盘的物理特性（顺序读快、随机读慢）博弈。
二、ext4 的 Extent Tree
ext4 是 Linux 上最广泛使用的文件系统。它从 ext3 演进而来，最核心的变化之一就是用 extent tree 取代了间接块映射。
Extent 的基本结构
ext4 的一个 extent
定义如下（fs/ext4/ext4_extents.h）：
struct ext4_extent {
__le32 ee_block; // 起始逻辑块号
__le16 ee_len; // 覆盖的块数（最多 32768，高位用于标记未初始化）
__le16 ee_start_hi; // 起始物理块号的高 16 位
__le32 ee_start_lo; // 起始物理块号的低 32 位
};一个 extent 只有 12 字节，却能表示最多 32768 个连续块（128MB，以 4KB 块大小计）。对比 ext2 的间接块方案，128MB 的连续数据只需要 12 字节元数据，而不是 32768 x 4 = 128KB。
Extent Tree 的节点结构
当 extent 数量超过 inode 能直接容纳的上限时，ext4 使用 B-tree 来组织 extent。树的每个节点（无论内部节点还是叶节点）都以一个 header 开头：
struct ext4_extent_header {
__le16 eh_magic; // 魔数 0xF30A
__le16 eh_entries; // 当前节点中的有效条目数
__le16 eh_max; // 当前节点能容纳的最大条目数
__le16 eh_depth; // 树的深度（叶节点为 0）
__le32 eh_generation; // 用于 htree 的版本号
};内部节点存储索引条目：
struct ext4_extent_idx {
__le32 ei_block; // 此子树覆盖的最小逻辑块号
__le32 ei_leaf_lo; // 子节点所在的物理块号（低 32 位）
__le16 ei_leaf_hi; // 子节点所在的物理块号（高 16 位）
__le16 ei_unused; // 保留
};叶节点存储实际的 extent（即上面的
ext4_extent）。
Inode 内联存储
ext4 inode 中有 60 字节的 i_block 空间（原本
ext2/ext3 用来存 15 个块指针的地方）。ext4 把这 60
字节重新利用：
60 字节 = 12 字节 header + 4 x 12 字节 extent也就是说，一个 ext4 inode 可以直接内联存储 4 个 extent，无需额外的磁盘块。4 个 extent 最多能覆盖 4 x 32768 = 131072 个块 = 512MB 的连续数据。对于大部分文件来说，这就够了——不需要额外的树节点，逻辑到物理的映射在读取 inode 时就已经全部加载。
当 extent 数量超过 4 个时，ext4 会分配额外的磁盘块来存储树节点。以 4KB 块大小计算：
一个 4KB 块 = 12 字节 header + 340 个 extent（每个 12 字节）实际上是 (4096 - 12) / 12 = 340.33，取整为 340 个。
树的深度分析
对于一棵深度为 d 的 extent tree：
- 深度 0（纯 inode 内联）：最多 4 个 extent
- 深度 1（inode 索引 + 一层叶节点）：最多 4 x 340 = 1360 个 extent
- 深度 2：最多 4 x 340 x 340 = 462,400 个 extent
- 深度 3：最多 4 x 340^3 = ~1.57 亿个 extent
每个 extent 最多覆盖 128MB，所以深度 1 的树就能表示 1360 x 128MB = ~170GB 的数据（如果完全连续，一个 extent 就够了）。实际上 ext4 限制树的最大深度为 5，理论上足以覆盖任意大小的文件。
查找一个逻辑块号时，从根节点（inode 内联）开始，在每一层做二分查找，定位到下一层的子节点，最终在叶节点中找到包含目标逻辑块号的 extent。时间复杂度是 O(d x log(m))，其中 d 是树的深度，m 是每个节点的条目数。由于 d 最多 5，m 最多 340，实际上几乎是常数时间。
内核代码路径
回到开头的问题，当你调用 pread()
时，内核的调用路径大致是：
// 1. VFS 层
vfs_read()
→ ext4_file_read_iter()
// 2. 查找 extent
ext4_map_blocks()
→ ext4_ext_map_blocks()
→ ext4_find_extent() // 在 extent tree 中查找
// 3. ext4_find_extent 的核心逻辑
// 从 inode 内联的 header 开始
// 逐层二分查找 ext4_extent_idx
// 读取下一层节点（可能需要磁盘 I/O，但通常在缓存中）
// 到达叶节点后，二分查找 ext4_extent
// 返回 (physical_block, length) 元组实际代码在 fs/ext4/extents.c
中，ext4_find_extent() 函数大约 150
行。核心是一个循环，每次迭代处理树的一层。
与间接块的性能对比
在实际基准测试中，extent tree 相比间接块映射的优势非常显著：
操作 ext3（间接块） ext4（extent） 提升
------------------------------------------------------------------
创建 10GB 文件 12.3s 2.1s 5.9x
删除 10GB 文件 8.7s 0.3s 29x
随机读 4KB (IOPS) 45,200 47,100 1.04x
顺序读吞吐量 1.2 GB/s 1.25 GB/s 1.04x
fsck 10GB 文件 4.2s 0.8s 5.3x随机读和顺序读的差异不大，因为瓶颈在磁盘本身。但创建、删除和 fsck 的差异巨大——因为 extent 方案需要管理的元数据少了几个数量级。
我的实际经验是：ext4 extent tree 是一个非常务实的设计。它没有追求理论上的最优，而是在兼容 ext3 的前提下，用最小的改动获得了最大的收益。这种”渐进式改进”的工程哲学值得学习。
三、XFS 的 B+Tree
如果说 ext4 是”在 ext2/ext3 的框架上做渐进改进”，XFS 则是从第一天就为大文件、大文件系统设计的。XFS 在 1993 年由 SGI 开发，2001 年进入 Linux 内核，至今仍然是 RHEL/CentOS 的默认文件系统。
B+Tree 无处不在
XFS 的设计哲学是：任何需要高效查找的元数据，都用 B+tree 来组织。XFS 中至少有五种不同用途的 B+tree：
- Inode B+tree：在 AG（Allocation Group）中按 inode 号查找 inode
- Free Space B+tree（按块号）：按起始块号排序的空闲区间
- Free Space B+tree（按长度）：按长度排序的空闲区间
- Extent B+tree（bmbt）：文件的逻辑块到物理块映射
- Reverse Mapping B+tree（rmapbt）：从物理块反查逻辑块（4.8+ 内核）
为什么需要两棵空闲空间树？因为分配器有两种常见请求模式：
- “给我一个从块号 X 附近开始的空闲区间”——用按块号排序的树
- “给我一个至少 N 块长的空闲区间”——用按长度排序的树
这种”为不同查询模式维护不同索引”的思路，和数据库中为同一张表建多个索引完全一样。
Allocation Group：并行化的关键
XFS 把整个文件系统划分为多个 Allocation Group（AG），每个 AG 是一个独立的分配单元，拥有自己的：
- Superblock 副本
- 空闲空间 B+tree
- Inode B+tree
- Inode 分配位图
+--------+--------+--------+--------+--------+
| AG 0 | AG 1 | AG 2 | AG 3 | AG 4 |
+--------+--------+--------+--------+--------+
每个 AG 有独立的锁、独立的 B+tree多个线程可以同时在不同的 AG 中分配空间，互不干扰。这是 XFS 在多核高并发场景下性能优异的核心原因之一。ext4 也有类似的 block group 概念，但 ext4 的 block group 粒度更细，且早期版本没有充分利用并行性。
Extent B+Tree（bmbt）
XFS 的文件 extent 映射使用 B+tree，与 ext4 的 extent tree 类似但更通用：
// XFS extent 记录（bmbt record）
struct xfs_bmbt_rec {
__be64 l0; // 打包了：逻辑块号（54 位）、extent 标志（1 位）
__be64 l1; // 打包了：起始物理块号（52 位）、块数（21 位）
};每个 extent 记录 16 字节（比 ext4 的 12 字节大），但逻辑块号用 54 位表示（ext4 用 32 位），这意味着 XFS 天然支持更大的文件。
XFS inode 内部也有内联 extent 的机制（data fork），空间更灵活——inode 大小可配置（256 字节到 2KB），更大的 inode 能内联更多 extent。
延迟分配（Delayed Allocation）
XFS 是最早实现延迟分配的文件系统之一。其思路是：
- 应用调用
write()时，不立即分配物理块，只在内存中记录脏页 - 等到实际需要写入磁盘时（
fsync()、内存不足、定时刷脏），才真正分配物理块 - 此时分配器能看到完整的写入模式，做出更优的分配决策
传统分配：
write(4KB) → 分配 1 个块
write(4KB) → 分配 1 个块
write(4KB) → 分配 1 个块（可能不连续！）
延迟分配：
write(4KB) → 记录脏页（不分配）
write(4KB) → 记录脏页（不分配）
write(4KB) → 记录脏页（不分配）
flush → 一次性分配 3 个连续块延迟分配显著减少了碎片化，因为分配器有更多的信息来做决策。代价是：如果系统在
write() 之后、flush
之前崩溃，数据会丢失——但这符合 POSIX
语义（write() 不保证持久化，只有
fsync() 才保证）。
ext4 后来也实现了延迟分配，但 XFS 在这方面有更长的经验和更成熟的实现。
从工程角度看，XFS 的 B+tree-everywhere 设计让它在处理超大文件系统（几百 TB 甚至 PB 级）时表现稳健。但代价是实现复杂度高——XFS 的内核代码量大约是 ext4 的 1.5 倍。如果你的场景不需要那么大的规模，ext4 的简单性可能更有吸引力。
四、btrfs 的 Copy-on-Write B-Tree
btrfs（B-tree File System）是 Linux 上最具野心的文件系统项目之一。它从 2007 年开始开发，试图成为 Linux 的”ZFS 替代品”，提供快照、校验和、RAID、子卷等高级功能。而这一切的基础，是一棵 CoW（Copy-on-Write）B-tree。
CoW 语义：永不原地修改
btrfs 的核心设计原则是：永远不在原地修改已有的数据或元数据。每次写入都会：
- 分配新的磁盘块
- 写入修改后的数据到新块
- 更新父节点的指针指向新块（父节点也是 CoW 的，递归到根）
- 原子地更新超级块的根指针
修改前： 修改后：
[Root A] [Root A']
/ \ / \
[B] [C] [B'] [C] ← C 不变，共享
/ \ / \ / \ / \
[D] [E] [F] [G] [D] [E'] [F] [G]
↑
修改了 E 的数据修改叶节点 E 时，需要创建 E’、B’、Root A’ 三个新节点。这就是 CoW 的”路径复制”（path copying）。
btrfs 的磁盘格式
btrfs 使用一棵巨大的 B-tree 来存储几乎所有的元数据。这棵树的键（key）是一个三元组：
struct btrfs_key {
__le64 objectid; // 对象 ID（如 inode 号）
__u8 type; // 条目类型
__le64 offset; // 类型相关的偏移
};不同类型的元数据通过 type 字段区分：
BTRFS_INODE_ITEM_KEY = 1 // inode 元数据
BTRFS_DIR_ITEM_KEY = 84 // 目录项
BTRFS_EXTENT_DATA_KEY = 108 // 文件 extent 数据
BTRFS_EXTENT_ITEM_KEY = 168 // extent 分配信息
...btrfs 的 B-tree 叶节点与传统 B-tree 不同——它存储变长的数据项：
+-------+-------+-------+-------+---+------+------+------+------+
| header| key 0 | key 1 | key 2 |...| free | val2 | val1 | val0 |
+-------+-------+-------+-------+---+------+------+------+------+
keys 从左向右增长 → ← values 从右向左增长keys 按顺序排列在节点前部，values 从节点末尾向前填充。中间是空闲空间。这种设计允许不同类型的条目有不同的大小，比如 inode 条目和 extent 条目大小就不同。
子卷和快照
CoW 的最大好处之一是廉价快照。创建快照时，btrfs 只需要：
- 复制当前根节点（几百字节）
- 增加所有子树的引用计数
不需要复制任何数据。快照和原卷共享所有未修改的数据块——修改任一方时，CoW 机制自动处理分离。
# 创建子卷
btrfs subvolume create /mnt/data/mysubvol
# 创建只读快照
btrfs subvolume snapshot -r /mnt/data/mysubvol /mnt/data/snap1
# 创建可写快照（用于测试环境）
btrfs subvolume snapshot /mnt/data/mysubvol /mnt/data/test-env快照在实际运维中极其有用：升级前做快照，出问题立即回滚。这是 ext4 和 XFS 无法原生提供的功能。
CoW 的代价：写放大
CoW 的优雅有代价。修改一个 4KB 的叶节点，需要重写从叶到根的整条路径。如果树的深度是 4，那么一次 4KB 的数据修改实际上需要写入：
1 个叶节点（16KB，btrfs 默认节点大小）
+ 3 个内部节点（各 16KB）
+ 1 个超级块（4KB）
= 68KB 的磁盘写入一次 4KB 的逻辑写入变成了 68KB 的物理写入——写放大比率为 17x。
实际情况会好一些，因为：
- 批量提交：btrfs 使用事务机制，多次修改可以合并到一个事务中，共享路径上的 CoW
- 延迟分配：类似 XFS，减少单独的小分配
- 内存中的节点缓存：修改多次后才刷到磁盘
但在某些极端场景下——比如数据库的随机小写入（4KB 页）——CoW 的写放大是真实存在的性能问题。这也是为什么很多数据库管理员对 btrfs 上跑数据库持谨慎态度。
元数据开销分析
btrfs 的”一棵树管一切”设计意味着这棵树可能非常大。一个包含 1 亿个文件的文件系统，元数据树可能有数十 GB。每次修改都要 CoW 整条路径，元数据的写放大在文件数量巨大时变得显著。
btrfs 社区长期努力优化这个问题。一些策略包括：
- 元数据预留：确保总有足够的空间做 CoW，防止”ENOSPC 死锁”
- 内联数据：小文件（<2KB）直接存在 B-tree 叶节点里，减少间接引用
- 压缩：透明压缩减少实际写入量
我的看法是：btrfs 的 CoW B-tree 在功能上非常强大，但它本质上是用写性能换取了一致性和快照能力。如果你的工作负载是读多写少（比如容器镜像存储、归档系统），btrfs 是很好的选择；如果是写密集型的数据库工作负载，你可能要三思。
五、ZFS 的 DMU 与间接块树
ZFS 是 Sun Microsystems 在 2005 年发布的”终极文件系统”。虽然由于 CDDL 许可证的问题无法合并进 Linux 主线内核，但通过 OpenZFS 项目，ZFS 在 Linux 上的使用非常广泛。
与 btrfs 的关键区别
ZFS 和 btrfs 都使用 CoW，但底层数据结构不同。btrfs 用一棵巨大的 B-tree 存所有东西；ZFS 使用间接块树（类似 ext2 的多级间接块，但加上了 CoW 和校验和）。
ZFS 的存储栈分层清晰：
ZPL (ZFS POSIX Layer)
↓
DMU (Data Management Unit)
↓
ARC (Adaptive Replacement Cache)
↓
SPA (Storage Pool Allocator)
↓
VDEV (Virtual Device Layer)DMU 是核心。它管理的基本对象叫做 dnode，类似于 inode 但更通用。每个 dnode 包含一组块指针，形成一棵间接块树：
// 简化的 ZFS 块指针
typedef struct blkptr {
dva_t blk_dva[3]; // 最多 3 个数据虚拟地址（用于镜像/RAIDZ）
uint64_t blk_prop; // 压缩、校验和类型等属性
uint64_t blk_pad[2];
uint64_t blk_phys_birth; // 物理出生事务号
uint64_t blk_birth; // 逻辑出生事务号
uint64_t blk_fill; // 子树中的非零块数
zio_cksum_t blk_cksum; // 256 位校验和
} blkptr_t;一个块指针 128 字节——比 ext4 的 4 字节块号大了 32 倍。但它包含了校验和、压缩信息、RAID 冗余信息等。
间接块树 vs B-tree
ZFS 的间接块树结构：
dnode
└── L2 间接块（包含 N 个块指针）
└── L1 间接块（包含 N 个块指针）
└── L0 数据块以 128KB 的块大小计算，每个间接块能容纳 128KB / 128B = 1024 个块指针。
- L0（数据块）：128KB
- L1（一级间接）：1024 x 128KB = 128MB
- L2（二级间接）：1024 x 128MB = 128GB
- L3（三级间接）：1024 x 128GB = 128TB
ZFS 选择间接块树而不是 B-tree 有其理由：
- 可变块大小：ZFS 支持 512B 到 16MB 的块大小，间接块树天然适应不同块大小
- 简单性：间接块树的实现比 B-tree 简单得多，不需要处理节点分裂和合并
- 校验和集成：每个块指针自带校验和，形成一棵”自校验的 Merkle 树”
代价是：间接块树的查找效率不如 B-tree（尤其是稀疏文件），且对小文件不太友好（一个 1KB 的文件也需要一个完整的 dnode）。
校验和与自愈
ZFS 最引以为豪的特性是端到端的数据完整性。每个块的校验和存储在父块中：
[间接块] --校验和--> [数据块]
↑
校验和存在父节点中，而非数据块自身这意味着如果磁盘悄悄损坏了一个数据块（silent data corruption / bit rot），ZFS 在读取时会发现校验和不匹配。如果配置了镜像或 RAIDZ，ZFS 还能自动从冗余副本中修复损坏的数据。
相比之下，ext4 和 XFS 没有这种端到端校验能力（ext4 有元数据校验和，但没有数据校验和）。btrfs 也有数据校验和，但不如 ZFS 成熟。
我认为 ZFS 的间接块树设计在工程上体现了”简单但完备”的哲学。它没有追求 B-tree 的查找效率，而是用简单的树结构实现了校验和、CoW、可变块大小、RAID 等多种特性的自然集成。这种”让数据结构为系统特性服务”的设计思路非常值得学习。
六、F2FS：为闪存设计的日志结构文件系统
F2FS（Flash-Friendly File System）由三星在 2012 年开发，专门针对闪存设备（eMMC、UFS、SSD）的特性优化。它的树形结构与上面四种文件系统截然不同。
为什么日志结构适合闪存
闪存有三个关键特性：
- 读写不对称：读可以按页（4KB）随机进行，写也是按页，但擦除必须按块（通常 256KB-4MB）
- 擦写次数有限：每个闪存块只能擦写数千到数万次
- 写前需擦除：不能覆盖写，必须先擦除整个块再写
传统文件系统的原地更新（in-place update）模式对闪存不友好：频繁更新同一个位置会导致 FTL（Flash Translation Layer）做大量的垃圾回收，加剧写放大和磨损。
日志结构文件系统（LFS）的思路是：所有写入都是追加到日志末尾，不做原地更新。这和闪存的特性天然匹配。
F2FS 的核心数据结构
F2FS 使用两层映射来定位数据块：
文件 inode → 直接/间接 node → NAT → 物理块
↑
Node Address TableNode Address Table（NAT）
NAT 是 F2FS 最核心的创新。传统 LFS 的问题是”雪崩更新”（wandering tree problem）：更新一个数据块需要更新其 inode，更新 inode 需要更新 inode map，更新 inode map 又需要更新 checkpoint…一路级联到超级块。
F2FS 用 NAT 打断了这个级联：
传统 LFS：
数据块更新 → node 更新 → node 的父 node 更新 → ... → checkpoint 更新
F2FS：
数据块更新 → node 更新 → NAT 中更新 node 地址（原地更新）NAT 是一个巨大的地址表，将 node ID 映射到其当前的物理地址。node 被写到新位置后，只需要更新 NAT 中的一个条目，不需要更新 node 的父节点。
struct f2fs_nat_entry {
__u8 version; // 版本号
__le32 ino; // inode 号
__le32 block_addr; // 当前物理块地址
} __packed;Segment Info Table（SIT）
SIT 记录每个 segment（通常 2MB，512 个 4KB 块）的使用状态：
struct f2fs_sit_entry {
__le16 vblocks; // 有效块数
__u8 valid_map[SIT_VBLOCK_MAP_SIZE]; // 位图，标记哪些块有效
__le64 mtime; // 修改时间
} __packed;SIT 用于垃圾回收决策：选择有效块比例最低的 segment 进行回收（贪心策略），或者选择最老的 segment（成本效益策略）。
F2FS 的 Node 树结构
F2FS 的文件数据通过 node 树来组织，结构类似 ext2 的间接块方案，但加入了 NAT 间接层：
inode node
├── 直接块指针 x 923（直接 node 内联）
├── 直接 node 指针 x 2
│ └── 每个直接 node 包含 1018 个块指针
├── 间接 node 指针 x 2
│ └── 每个间接 node 包含 1018 个直接 node 指针
└── 双重间接 node 指针 x 1
└── 包含 1018 个间接 node 指针关键区别是：所有 node 指针都是通过 NAT 间接寻址的。修改一个数据块 → 写新的数据块到日志 → 更新直接 node → 将新 node 写到日志 → 更新 NAT。整个过程不需要修改 inode 或更高层的 node。
多日志头设计
F2FS 维护 6 个日志头（log head），分别用于不同温度的数据：
Hot Node Log ← 频繁更新的 inode、直接 node
Warm Node Log ← 不频繁更新的 node
Cold Node Log ← 很少更新的 node（如目录 node）
Hot Data Log ← 频繁更新的数据（如数据库页）
Warm Data Log ← 普通文件数据
Cold Data Log ← 多媒体、归档数据这种冷热分离策略减少了垃圾回收的开销：冷数据段中的有效块比例高（很少被覆盖），回收时需要搬移的数据少。
F2FS 的设计给我的启发是：数据结构的选择不仅取决于算法效率，更取决于底层硬件的物理特性。对闪存来说，“追加写 + NAT 间接寻址”比”B-tree 原地更新”更合理，即使前者在理论复杂度上并不占优。
七、文件系统树设计对比
把五种文件系统的树形结构放在一起对比：
+----------+--------------+----------+--------+---------+----------+
| 文件系统 | 树类型 | CoW | 校验和 | 快照 | 适用场景 |
+----------+--------------+----------+--------+---------+----------+
| ext4 | Extent Tree | 否 | 元数据 | 否(*) | 通用 |
| | (B-tree变体) | | | | |
+----------+--------------+----------+--------+---------+----------+
| XFS | B+Tree | 否 | 元数据 | 否 | 大文件 |
| | (多种用途) | | | | 大文件系统|
+----------+--------------+----------+--------+---------+----------+
| btrfs | CoW B-Tree | 是 | 全部 | 是 | 快照 |
| | (单棵大树) | | | | 容器 |
+----------+--------------+----------+--------+---------+----------+
| ZFS | 间接块树 | 是 | 全部 | 是 | 存储服务 |
| | + Merkle | | | | NAS |
+----------+--------------+----------+--------+---------+----------+
| F2FS | Node树 | 追加写 | 全部 | 否 | 闪存设备 |
| | + NAT | | | | 移动设备 |
+----------+--------------+----------+--------+---------+----------+
(*) ext4 可以通过 LVM 快照实现，但不是文件系统原生支持更详细的数据结构对比：
+----------+----------+------------+-----------+----------+-----------+
| 特性 | ext4 | XFS | btrfs | ZFS | F2FS |
+----------+----------+------------+-----------+----------+-----------+
| 最大文件 | 16 TB | 8 EB | 16 EB | 16 EB | 3.94 TB |
| 最大卷 | 1 EB | 8 EB | 16 EB | 256 ZB | 16 TB |
| 节点大小 | 4KB | 可配置 | 16KB | 可变 | 4KB |
| | (=块大小)| (512B-64KB)| (默认) | (512B- | (=块大小) |
| | | | | 16MB) | |
| 查找复杂 | O(log n) | O(log n) | O(log n) | O(d) | O(1)+O(d) |
| 度 | B-tree | B+tree | CoW B-tree| 间接块 | NAT+间接 |
| 写放大 | 低 | 低 | 中-高 | 中-高 | 低-中 |
| 碎片化 | 中 | 低 | 中-高 | 低-中 | 中 |
+----------+----------+------------+-----------+----------+-----------+
注：O(d) 中 d 是间接块树的深度，通常 <= 6
NAT 查找可视为 O(1)（地址表直接索引）写放大对比分析
假设工作负载是”随机修改 4KB 数据块”，各文件系统的写放大如下：
ext4:
修改数据块 (4KB) + 更新 extent tree 路径 (最多 2-3 个 4KB 块)
+ 日志 (data=ordered 模式下仅元数据日志)
总计: ~12-16KB，写放大 3-4x
XFS:
修改数据块 (4KB) + 更新 B+tree (最多 2-3 个块)
+ 日志 (元数据日志)
总计: ~12-16KB，写放大 3-4x
btrfs:
CoW 数据块 (4KB) + CoW 路径到根 (3-4 个 16KB 节点)
+ 超级块更新
总计: ~52-68KB，写放大 13-17x
ZFS:
CoW 数据块 (可变，默认 128KB) + CoW 间接块路径 (2-3 个块)
+ uber block 更新
总计: 取决于块大小，128KB 块下约 384KB，写放大 96x（对 4KB 逻辑写入）
使用特殊的小记录优化后约 16-32KB，写放大 4-8x
F2FS:
追加数据块 (4KB) + 追加 node (4KB) + 更新 NAT (原地，4KB 中的一小部分)
+ SIT 更新
总计: ~12-16KB，写放大 3-4xbtrfs 和 ZFS 的写放大明显高于非 CoW 文件系统。这是它们提供一致性快照能力的代价。
八、工程陷阱与实战经验
碎片化：CoW 文件系统的顽疾
CoW 文件系统天生容易碎片化。因为每次写入都分配新的物理块，原本连续的文件会逐渐变得不连续：
# 检查 btrfs 文件碎片化程度
filefrag -v /mnt/btrfs/database.db
# 典型输出（严重碎片化）:
# Filesystem type is: 9123683e
# File size of /mnt/btrfs/database.db is 10737418240 (2621440 blocks of 4096 bytes)
# ext: logical_offset: physical_offset: length: expected: flags:
# 0: 0.. 0: 1234567..1234567: 1:
# 1: 1.. 1: 2345678..2345678: 1: 1234568:
# 2: 2.. 2: 3456789..3456789: 1: 2345679:
# ...（数万个碎片）对策：
- btrfs
自动碎片整理：
btrfs filesystem defragment，但这会破坏快照的共享（因为 CoW） - nocow 属性：对数据库文件设置
chattr +C，关闭 CoW（同时失去校验和和快照保护） - autodefrag 挂载选项：在后台自动碎片整理，但有性能开销
# 对数据库文件关闭 CoW
chattr +C /mnt/btrfs/database.db
# 挂载时启用自动碎片整理
mount -o autodefrag /dev/sda1 /mnt/btrfsfsck 时间：树深度的隐性成本
文件系统检查（fsck）的时间与树的组织方式密切相关：
ext4: fsck 主要检查 inode 表和 extent tree
10TB 文件系统: ~5-15 分钟
可以在线 fsck (e2fsck -n) 做只读检查
XFS: xfs_repair 需要遍历所有 B+tree
10TB 文件系统: ~10-30 分钟
xfs_scrub 支持在线检查
btrfs: btrfs scrub 在线校验所有数据
10TB 文件系统: 取决于磁盘速度，通常 1-4 小时
btrfs check 离线检查，可能更慢
ZFS: zpool scrub 在线校验
10TB 存储池: 取决于磁盘速度，通常 1-4 小时
不需要传统意义上的 fsck（CoW + 事务保证一致性）值得注意的是，CoW 文件系统（btrfs、ZFS）理论上不需要传统的 fsck——因为 CoW 保证了文件系统始终处于一致状态。但它们仍然需要 scrub 来检测和修复静默数据损坏。
CoW 性能悬崖
btrfs 在空间使用率接近 100% 时会出现严重的性能下降，甚至可能陷入 ENOSPC（空间不足）的死锁状态——因为 CoW 需要分配新块才能完成写入，但已经没有空闲空间了。
# btrfs 空间使用查询
btrfs filesystem usage /mnt/btrfs
# 如果 metadata 空间不足，可能导致无法写入，甚至无法删除文件
# 紧急修复：添加临时设备
btrfs device add /dev/sdb /mnt/btrfs
btrfs balance start -dusage=50 /mnt/btrfs
btrfs device delete /dev/sdb /mnt/btrfs经验法则：btrfs 分区保留至少 15-20% 的空闲空间。对于有快照的系统，保留更多——因为快照会阻止旧数据块被回收。
ZFS 也有类似问题。ZFS 的官方建议是保持存储池使用率在 80% 以下。超过这个阈值后，ZFS 的性能曲线会急剧恶化，因为空间分配器越来越难以找到连续的空闲区间。
Extent Tree 的极端碎片化案例
我在生产环境中遇到过一个案例：一个 ext4 上的虚拟机镜像文件（qcow2 格式，动态分配），因为虚拟机内部的碎片化传导到宿主机，导致 extent tree 膨胀到上万个 extent。表现为：
- 读取这个文件时，
ext4_find_extent()的开销从微秒级增加到毫秒级 - 删除这个文件时，内核需要逐个回收所有 extent
对应的块，导致
unlink()调用耗时超过 30 秒 - 在这 30 秒内，整个文件系统的其他操作都受到影响（因为 ext4 的日志事务大小有限制）
解决方案是定期对虚拟机镜像做
e4defrag，或者改用 XFS（XFS
的延迟分配和分配策略对大文件更友好）。
元数据日志 vs 全日志
ext4 默认使用 data=ordered
模式：只有元数据写入日志，数据直接写到最终位置。这提供了合理的一致性（不会看到垃圾数据）同时保持了性能。
# 查看当前日志模式
mount | grep ext4
# /dev/sda1 on / type ext4 (rw,relatime,data=ordered)
# data=journal 模式：数据也写入日志，最安全但性能最差
# data=writeback 模式：元数据日志，但数据可能在元数据之后到达磁盘（可能看到垃圾数据）btrfs 和 ZFS 由于 CoW 机制，天然不需要传统的日志——CoW 本身就是”日志”。新数据写到新位置，原子切换指针，旧数据自动成为一致的历史版本。
九、文件系统设计趋势的个人思考
趋势一：CoW 成为主流
观察 Linux 文件系统的演进方向，CoW 正在成为主流：
- Fedora 默认文件系统从 ext4 切换到了 btrfs
- SUSE 很早就默认使用 btrfs
- Ubuntu 在 server 版本中支持 ZFS
- 甚至 ext4 也在考虑加入 CoW 相关特性（reflinks）
CoW 的吸引力在于它同时解决了三个问题：崩溃一致性、快照、数据完整性。传统文件系统需要日志来保证一致性，需要 LVM 来做快照，需要额外工具来做校验——CoW 把这些统一在一个机制下。
趋势二：计算存储与文件系统的融合
随着 CXL（Compute Express Link）和计算存储设备的发展，文件系统的树形结构可能不再完全由 CPU 管理。未来的存储设备可能内置 B-tree 加速引擎，文件系统只需要发送高层语义操作（“在这棵树的 key X 处插入 value Y”），具体的树操作由设备硬件完成。
这并非空想。三星的 KV-SSD 已经实现了键值接口，跳过了传统的块接口。如果这种趋势继续，文件系统中精心设计的树形结构可能像 I/O 调度器一样，最终被更智能的硬件取代。
趋势三：分层存储需要更灵活的树
bcachefs 是一个正在积极开发的新文件系统，它试图在一个文件系统中支持多层存储（SSD + HDD），自动将热数据放在快层、冷数据放在慢层。这要求树形结构能够高效地记录数据的”温度”信息和位置信息。
bcachefs 使用了一种类似 btrfs 的 CoW B+tree，但做了很多工程优化，包括更紧凑的节点格式和更智能的节点分裂策略。它的目标是同时具备 btrfs 的功能和 ext4 的性能——这是一个非常有野心的目标。
我的总结
文件系统的树形结构设计，本质上是在以下几个维度之间做权衡：
写性能 <--------> 一致性保证
空间效率 <--------> 功能丰富度
实现简单 <--------> 极端场景适应性
随机写 <--------> 顺序写没有完美的设计，只有适合特定场景的设计。ext4 的 extent tree 在通用场景下表现优秀，是因为它选择了”简单、低开销、够用”的路线。btrfs 的 CoW B-tree 在容器和快照场景下无可替代，是因为它选择了”功能完备，接受写放大”的路线。
作为工程师，理解这些权衡比记住具体的数据结构更重要。当你面对一个新的存储问题时，先问自己：我的访问模式是什么？一致性要求是什么？硬件的物理特性是什么？然后再选择（或设计）合适的树。
这可能是文件系统设计教给我的最重要的一课：没有最好的数据结构，只有最适合约束条件的数据结构。
上一篇: 伙伴系统与 SLUB 分配器 下一篇: epoll 的数据结构
相关阅读: - B-tree 深度解析 - B-tree vs LSM-tree - I/O 调度：CFQ 到 kyber