手工遍历NTFS的B＋树

在学习了NTFS的索引结构之后，下面用一个例子实际体会一下NTFS的B＋树结构，用手工遍历NTFS的B＋树的方法定位一个文件。

对B＋树的数据结构不了解的读者请先学习1.4节。

在NTFS分区G的根目录下有3个目录和88个文本文件，如图4-470所示。

图4-470　NTFS分区G的根目录

其中“36.txt”文件是我们的访问目标。下面将以NTFS的工作方式手工定位到“36.txt”这个文件在分区中的存放地址。

第1步　定位DBR

通过分区G所在硬盘的分区表定位到G盘的开始位置，在63号扇区。这个扇区就是G盘的DBR扇区。

第2步　定位$MFT

访问DBR扇区的BPB，通过“$MFT起始簇号”、“每簇扇区数”两个参数的值便可计算出$MFT的开始扇区。

第3步　定位根目录的文件记录

找到$MFT后，在$MFT中寻找根目录的文件记录，5号文件记录就是根目录了，其内容如图4-471所示。

图4-471　根目录的文件记录

第4步　分析索引属性

在根目录的文件记录中有7个属性，目录在NTFS文件系统中其实就是一个文件名的索引，所以目录的文件记录中一定有索引属性。对于小目录来说，有索引根（90H）属性就够了；而对于大目录来说，还需要有索引分配（A0H）属性。本例中根目录是一个大目录，在它的文件记录中有一个90H属性，但里面没有实质的索引项，所以重点要放在下面的A0H属性上。这是一个索引分配属性，该属性的数据流就是索引缓冲区，也就是B＋树的节点。根目录下的文件及目录的索引项就存放在这些节点中。

具体分析这个A0H属性，通过该属性中的Run List定位到其数据流，该属性的Run List如图4-472所示。

图4-472　A0H属性的Run List

在图4-472的A0H属性中，Run List包含多个数据流，所以Run List占用了很多字节。但图4-472中“①”处圈中的两个字节“13 00”并不是Run List中的数据，而是更新序列号。这两个字节需要用更新数组中的两个字节替换，也就是图中“②”处圈中的两个字节“08 9B”，所以该Run List的完整字节应该是“31 08 9B 10 03 21 08 77 CA 21 08 45 01 21 08 9B 03 21 10 F0 20 21 08 0E 05”。该Run List中一共有6个Data Run（数据流），这6个数据流的具体计算方法及结果见表4-95。

表4-95　6个Data Run的计算方法及结果

数据流编号	数据流起始LCN（逻辑簇号）	数据流长度（簇）
1	200 859	8
2	200 859-13705＝187 154	8
3	187 154＋325＝187 479	8
4	187 479＋923＝188 402	8
5	188 402＋8432＝196 834	16
6	196 834＋1294＝198 128	8

第5步　分析位图属性

在A0H属性的Run List所列出的数据流分配中，哪些簇实际使用了，哪些簇没有使用，这是由位图（B0H）属性管理的，所以还需要分析一下B0H属性。

回到前面的图4-472中看一下B0H属性。该属性是一个常驻属性，重点关心它的属性体，属性体的大小为8个字节，其值为“77H”，换算成二进制为“01110111”，它的含义是，当前分配给索引项的空间中有6个被使用的索引缓冲区，结合表4-95中6个Data Run的LCN分配结果，就能跟其虚拟簇号（VCN）对应上了，对应关系见表4-96。

表4-96　索引缓冲区的LCN与VCN对应关系

数据流编号	数据流起始LCN（逻辑簇号）	数据流起始VCN（虚拟簇号）	数据流长度（簇）
1	200 859	0（已用）	8
2	200 859-13705＝187 154	8（已用）	8
3	187 154＋325＝187 479	16（已用）	8
4	187 479＋923＝188 402	24（未用）	8
5	188 402＋8432＝196 834	32（已用）	16
6	196 834＋1294＝198 128	48（已用）	8

（注：该分区每簇扇区数为1，每索引缓冲区大小为8簇）

第6步　遍历B＋树

分析完索引缓冲区的LCN与VCN的对应关系，下一步就可以开始遍历B＋树了。

从表4-96可知，B＋树的节点分别存放在LCN为200 859、187 154、187 479、196 834、198 128的各个簇中。到这些簇中遍历一下，结果发现在196 834号簇所在的索引缓冲区中的节点含有子节点，如图4-473所示。

图4-473　包含子节点的四个索引项

通过分析图4-473中的这四个索引项，发现它们都包含子节点。我们的目标文件“36.txt”的文件名大于“34.txt”，小于“53.txt”，所以文件“36.txt”的节点一定在“53.txt”的子节点中。由图4-473中“53.txt”的索引项可以看出，其子节点的起始VCN是“10H”，换算为十进制等于16，查看表4-96中索引缓冲区LCN与VCN对应关系，可知VCN的16号簇对应LCN的187 479号簇。

现在可以跳转到187 479号簇，在该索引缓冲区中进行顺序遍历，很快发现其中的第二个节点就是目标文件“36.txt”的节点了，如图4-474所示。

图4-474　“36.txt”的索引项

第7步　访问目标文件的文件记录

从“36.txt”的索引项中可以获得其$MFT参考号，也就是其文件记录号，为“4CH”，也就是十进制的76。进入$MFT文件，找到76号文件记录，内容如图4-475所示。

图4-475　76号文件记录

很明显该记录就是文件“36.txt”的记录，其80H属性用来管理文件的数据。该80H属性为非常驻属性，Run List的取值为“32 D8 01 A3 DC 02”，只有一个数据流，说明文件是连续存放的，没有碎片。通过数据流的具体值可以定位到文件的开始LCN为187 555簇，占用472个簇，通过80H属性还能查看到文件的实际大小是241 664字节。

到此为止，我们就成功地定位了文件“36.txt”的数据存储地址。