如何恢复 Linux 上删除的文件-reiserfs 文件系统原理（2）

look_w

B+ 树与 ext2/ext3 的超级块比较一下会发现，reiserfs 的超级块中并没有索引节点表的信息，这是由于 reiserfs 并没有使用索引节点表，而是采用了 B+ 树来组织数据（在 reiserfs 的文档中也称为是 S+  树）。图 2 中给出了一棵典型的 2 阶 B+ 树，其深度为 4。
图 2. 2 阶 B+ 树一棵 B+ 树有唯一一个根节点，其位置保存在超级块的 root_block 字段中。包含子树的节点都是中间节点（internal node），不包含子树的节点称为叶子节点（leaf node）。按照是否包含 B+ 树本身需要的信息，节点又可以分为两类，一类节点包含 B+ 树所需要的信息（例如指向数据块位置的指针，同时也包括文件数据），称为格式化节点（formatted node）；另外一类只包含文件数据，而不包含格式化信息，称为未格式化节点（unformatted node 或 unfleaf）。因此，所有的中间节点都必须是格式化节点。一个格式化的叶子节点中可以包含多个条目（item，也称为项），所谓条目是一个数据容器，其内容可以保存到一个数据块中，也就是说，一个条目只能隶属于一个数据块，它是节点管理空间的基本单位。
为了方便理解起见，我们可以认为对于 B+ 树来说，一共包含 3 类节点：中间节点（其中保存了对叶子节点的索引信息）、叶子节点（包含一个或多个条目项）和数据节点（仅仅用来存放文件数据）。
熟悉数据结构的读者都会清楚，B+ 树是一棵平衡树，从根节点到达每个叶子节点的深度都是相同的。与 B- 树相比，B+ 树的好处是可以将数据全部保存到叶子节点中，而中间节点中并不存放真正的数据，仅仅用作对叶子节点的索引。为了方便起见，树的深度从叶子节点开始计算，叶子节点的深度为 1，之上的中间节点逐层加 1。在 B+ 树中查找匹配项首先要对关键字进行比较并沿对应指针进行遍历，直至搜索到叶子节点为止；而叶子节点也是按照关键字从小到大的顺序进行排列的。也正是由于这种结构，使得 B+ 树非常适合用来存储文件系统结构。
关键字reiferfs 中采用的关键字包含 4 个部分，形式如下：

1	( directory-id, object-id, offset, type )

这 4 个部分分别表示父目录的 id、本对象的 id、本对象在整个对象（文件）中的偏移量以及类型。关键字的比较就是按照这 4 个部分逐一进行的。读者可能会好奇为什么不简单地采用对象 id 作为关键字。实际上，这种设计是有很多考虑的，采用 directory-id作为关键字的一部分，可以将相同目录中的文件和子目录组织在一起，加快对目录项的存取。offset 的出现是为了支持大文件，一个间接条目（后文中会介绍）最多能指向 (数据块大小-48）/4 个数据块来存放文件数据，在默认的 4KB 数据块中最大只能支持 4048KB 的文件。因此使用 offset 就可以表明该对象在文件中所处的偏移量。type 可以用来区分对象的类型。目目前reiserfs 支持四种类型，TYPE_STAT_DATA、TYPE_INDIRECT 1、TYPE_DIRECT 2、 TYPE_DIRENTRY，解释见后文的条目头部分。
在 3.5 之前的版本中，这 4 部分都是 32 位的整数，这样造成的问题是最大只能支持大约 232=4GB 的文件。从 3.6 版本开始，设计人员将 offset 扩充至 60 位，将 type 压缩至 4 位。这样理论上能够支持的最大文件就达到了 260 字节，但是由于其他一些限制，reiserfs 中可以支持的文件上限是 8TB。正是由于这个原因，reiserfs 中有两个版本的关键字，相关定义如清单 2 所示。
清单2. reiserfs 中与关键字有关的定义

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

363 struct offset_v1 { 364         __le32 k_offset; 365         __le32 k_uniqueness; 366 } __attribute__ ((__packed__)); 367 368 struct offset_v2 { 369         __le64 v; 370 } __attribute__ ((__packed__)); 371         372 static inline __u16 offset_v2_k_type(const struct offset_v2 *v2) 373 { 374         __u8 type = le64_to_cpu(v2->v) >> 60; 375         return (type <= TYPE_MAXTYPE) ? type : TYPE_ANY; 376 } 377 378 static inline void set_offset_v2_k_type(struct offset_v2 *v2, int type) 379 { 380         v2->v = 381             (v2->v & cpu_to_le64(~0ULL >> 4)) | cpu_to_le64((__u64) type << 60); 382 } 383 384 static inline loff_t offset_v2_k_offset(const struct offset_v2 *v2) 385 { 386         return le64_to_cpu(v2->v) & (~0ULL >> 4); 387 } 388 389 static inline void set_offset_v2_k_offset(struct offset_v2 *v2, loff_t offset) 390 { 391         offset &= (~0ULL >> 4); 392         v2->v = (v2->v & cpu_to_le64(15ULL << 60)) | cpu_to_le64(offset); 393 } 394 395 /* Key of an item determines its location in the S+tree, and 396    is composed of 4 components */ 397 struct reiserfs_key { 398         __le32 k_dir_id;        /* packing locality: by default parent 399                                    directory object id */ 400         __le32 k_objectid;      /* object identifier */ 401         union { 402                 struct offset_v1 k_offset_v1; 403                 struct offset_v2 k_offset_v2; 404         } __attribute__ ((__packed__)) u; 405 } __attribute__ ((__packed__)); 406

尽管结构定义中并没有显式地声明 offset 和 type 分别是 60 位和 4 位长，但是从几个相关函数中可以清楚地看到这一点。