如何恢复Linux上删除的文件 （6）

　　熟悉数据结构的读者都会清楚，B+ 树是一棵平衡树，从根节点到达每个叶子节点的深度都是相同的。与 B- 树相比，B+ 树的好处是可以将数据全部保存到叶子节点中，而中间节点中并不存放真正的数据，仅仅用作对叶子节点的索引。为了方便起见，树的深度从叶子节点开始计算，叶子节点的深度为 1，之上的中间节点逐层加 1。在 B+ 树中查找匹配项首先要对关键字进行比较并沿对应指针进行遍历，直至搜索到叶子节点为止；而叶子节点也是按照关键字从小到大的顺序进行排列的。也正是由于这种结构，使得 B+ 树非常适合用来存储文件系统结构。

　　关键字

　　reiferfs 中采用的关键字包含 4 个部分，形式如下：

( 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 所示。