在学习了NTFS的索引结构之后,下面用一个例子实际体会一下NTFS的B+树结构,用手工遍历NTFS的B+树的方法定位一个文件。
对B+树的数据结构不了解的读者请先学习1.4节。
在NTFS分区G的根目录下有3个目录和88个文本文件,如图4-470所示。
其中“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步 分析索引属性
在根目录的文件记录中有7个属性,目录在NTFS文件系统中其实就是一个文件名的索引,所以目录的文件记录中一定有索引属性。对于小目录来说,有索引根(90H)属性就够了;而对于大目录来说,还需要有索引分配(A0H)属性。本例中根目录是一个大目录,在它的文件记录中有一个90H属性,但里面没有实质的索引项,所以重点要放在下面的A0H属性上。这是一个索引分配属性,该属性的数据流就是索引缓冲区,也就是B+树的节点。根目录下的文件及目录的索引项就存放在这些节点中。
具体分析这个A0H属性,通过该属性中的Run List定位到其数据流,该属性的Run List如图4-472所示。
在图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中的这四个索引项,发现它们都包含子节点。我们的目标文件“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所示。
第7步 访问目标文件的文件记录
从“36.txt”的索引项中可以获得其$MFT参考号,也就是其文件记录号,为“4CH”,也就是十进制的76。进入$MFT文件,找到76号文件记录,内容如图4-475所示。
很明显该记录就是文件“36.txt”的记录,其80H属性用来管理文件的数据。该80H属性为非常驻属性,Run List的取值为“32 D8 01 A3 DC 02”,只有一个数据流,说明文件是连续存放的,没有碎片。通过数据流的具体值可以定位到文件的开始LCN为187 555簇,占用472个簇,通过80H属性还能查看到文件的实际大小是241 664字节。
到此为止,我们就成功地定位了文件“36.txt”的数据存储地址。