Btrfs用B-Tree替代线性表管理目录

ext2/3把目录内容存成一张线性表，查找一个文件必须从头遍历到找到为止，随着目录下文件数量增多，查找时间线性增长。Btrfs把所有元数据（不只是目录）统一用B-Tree管理：B-Tree每个节点能容纳多个子树，树高远低于二叉树，而磁盘I/O次数正好由树高决定，所以用B-Tree索引能显著减少定位一条元数据所需的磁盘I/O次数。发散：这是”数据结构选型要匹配硬件访问代价”的直接体现——B-Tree并不比二叉树在渐进复杂度上更优，它的优势完全来自”让每次比较尽量对应一次磁盘页读取”这个物理约束，这也是数据库索引普遍选择B-Tree及其变种而非二叉树的根本原因。