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

NTFS的索引结构分析

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

NTFS的一些新功能建立在一种叫作“综合索引”的基本功能之上。综合索引中包含了具有某一特征类型的多个分类项,并使用一种高效的存储机制以便于快速查找。在Windows 2000以前的NTFS版本中仅支持$I30的综合索引,索引中仅存储目录项。索引过程将目录项按名称分类并将这些项按照B+树的结构保存,如图4-466所示。

NTFS的索引结构分析
图4-466 NTFS索引结构

图4-466是一个包含3个节点,每个节点3个项,共9项的目录的MFT条目,其中索引根(Index Root)属性指向B+树的根。这个MFT条目并不能容纳所有9个目录项,NTFS必须把其中一部分项存放在别处,因此,NTFS分配了两个索引缓冲区来存放另外的项(索引根以及索引缓冲区一般能够存储三个以上文件项,这依赖于文件名的长度)。一个MFT条目占1KB的空间,而一个索引缓冲区占4KB的空间。

从图4-466中的箭头可以看出NTFS的存储项是按字母顺序进行的。假设运行一个程序试图打开目录中的e.doc文件,NTFS会首先去读索引根属性,其中包含了d.pic、h.ppt及i.ddt三个文件项,并将名称“e.doc”与第一个项的名称“d.pic”进行比较,NTFS得出结论:e.doc在字母序上排在d.pic之后。因此转而处理下一个项“h.ppt”,经过比较以后,由于e.doc的字母序在h.ppt之前,NTFS就会检索h.ppt项中索引缓冲区的虚拟簇号(VCN)。这个索引缓冲区中存储着字母序比h.ppt小但比d.pic大的项。VCN代表一个簇在一个文件或目录中的顺序,NTFS能够将虚拟簇号映射成逻辑簇号(LCN),而逻辑簇号表示着一个簇相对于一个卷的起始点的相对偏移量。而如果h.ppt项中并不存在这个索引缓冲区的虚拟簇号,则NTFS可以立即断定这个目录中不存在e.doc文件,并报告打开文件失败。

当获得索引缓冲区的虚拟簇号以后,NTFS就会继续查找。从图4-466中可以看出,索引缓冲区的第一个项正是要找的e.doc,于是NTFS就从e.doc项中读出它对应的文件记录的位置。索引项中还存储着如时间戳(创建时间、最后修改时间等)、文件大小、属性等其他信息。虽然NTFS在文件的文件记录中也存储了这些信息,但将这些信息复制到目录项中可以提高列目录或做一些简单的文件查询时的效率。

目录项是按照字母排序的,这也解释了NTFS系统在列目录的时候为什么总是按照字母顺序的问题。相反,FAT文件系统并不对目录项排序,所以在FAT文件系统中列目录时并没有顺序。另外,由于NTFS将目录项按照B+树的结构保存,使得在包含很多文件的目录中查找文件时效率非常高。一般来说,NTFS只需要扫描所有目录项中的一小部分即可。在这一点上,FAT文件系统只能使用线性查找,也就是说,为了查找一个文件,很大程度上需要查询这个目录中的几乎每一个文件项。

索引缓冲区是NTFS的B+目录管理中非常重要的一个结构,每个索引缓冲区在NTFS中一般是4KB的固定大小,其位置和大小由目录的文件记录中A0H属性的Run List定义,如图4-467所示。

NTFS的索引结构分析
图4-467 根目录的A0H属性

从图4-467中A0H属性的Run List可以看到,索引缓冲区的起始簇号是4014H,换算为十进制就是16 404号簇,大小是一个簇。只要跳转到16 404号簇就是索引缓冲区的开始了,如图4-468所示。

NTFS的索引结构分析
图4-468 索引缓冲区

在图4-468的索引缓冲区中,最前面是一个标准索引头,后面有四个索引项。

标准索引头的结构见表4-92。

表4-92 标准索引头的结构

字节偏移 字段长度(字节) 描述
0x00 4 头标志,总是“INDX”
0x04 2 更新序列号的偏移
0x06 2 更新序列号与更新数组以字为单位的大小(S)
0x08 8 日志文件序列号
0x10 8 本索引缓冲区在索引分配中的VCN
0x18 4 索引项的偏移
0x1C 4 索引项大小
0x20 4 索引项分配大小
0x24 1 如果不是叶节点,置1,表示还有子节点
0x25 3 用0填充
0x28 2 更新序列
0x2A 2S-2 更新序列数组

注意

标准索引头中0x18处“索引项的偏移”是相对当前位置计算的,而不是相对标准索引头的起始点计算的,所以,实际索引项的偏移该是在0x58处。

在标准索引头之后就是索引项,索引项的结构见表4-93。

表4-93 索引项的结构

NTFS的索引结构分析

这里以图4-468中的“索引项①”为例,做一下讲解。“索引项①”的内容如图4-469所示。

NTFS的索引结构分析
图4-469 索引项①

对“索引项①”的分析结果见表4-94。

表4-94 索引项①的分析结果

字节偏移 字段长度(字节) 分析结果
0x00 8 文件的MFT参考号为0x04
0x08 2 索引项大小为0x68字节
0x0A 2 文件名偏移为0x52
0x0C 2 索引标志,文件名索引
0x0E 2 填充(到8字节)
0x10 8 父目录的MFT文件参考号,为0x05,表示根目录
0x18 8 文件创建时间:2009-10-03,21:17:25
0x20 8 最后修改时间:2009-10-03,21:17:25
0x28 8 文件记录最后修改时间:2009-10-03,21:17:25
0x30 8 最后访问时间:2009-10-03,21:17:25
0x38 8 文件分配大小,0x9000=36 864字节=72扇区=9簇
0x40 8 文件实际大小,0x8CA0=36 000字节
0x48 8 文件标志,0x06表示系统、隐藏文件
0x50 1 文件名长度(F),8个字符
0x51 1 文件名命名空间,0x03表示Win32&DOS
0x52 16 文件名,$ATTRDEF
方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门