您当前的位置:首页 > 计算机 > 文件格式与编码

手工遍历NTFS的B+树

时间:01-02来源:作者:点击数:

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

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

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

手工遍历NTFS的B+树
图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所示。

手工遍历NTFS的B+树
图4-471 根目录的文件记录

第4步 分析索引属性

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

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

手工遍历NTFS的B+树
图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所示。

手工遍历NTFS的B+树
图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所示。

手工遍历NTFS的B+树
图4-474 “36.txt”的索引项

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

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

手工遍历NTFS的B+树
图4-475 76号文件记录

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

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

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门