NTFS B＋树大目录结构动态解析

吴伟民，刘 凯，江达强，苏 庆，陈梓斌

（广东工业大学计算机学院 可视计算实验室，广东 广州 510006）

0 引 言

NTFS文件系统是随着Windows NT 操作系统的诞生而产生的，并在随后的Windows版本中逐渐成为主流的文件系统。NTFS系统具有极其出色的稳定性和安全性，在使用过程中不容易产生碎片，同时它还提供了容错结构日志，在文件系统受到破坏时，可根据日志恢复至一个一致性的状态，此外NTFS还提供了文件压缩、磁盘配额、利用B＋树结构来管理文件目录等功能［1－2］。

NTFS文件系统使用B＋树结构大目录对大型文件夹进行管理。大目录结构为三层或三层以上，其中三层目录结构最为典型。B＋树大目录是NTFS优于FAT32重要特征之一。分析大目录的结构和变化规律是理解NTFS文件系统技术的重要途径，也是开发操作NTFS分区程序的基础。Windows操作系统中极其重要的文件夹如Windows、System32、Drivers等都是超大型的目录。基于商业原因，Mi－crosoft至今没有完全公布NTFS文件系统技术资料。国内外有比较多的论文论述NTFS结构，如文献［3－8］对NTFS的主要数据结构及应用进行过分析，但并未涉及目录结构方面。文献［9－10］对NTFS的目录结构做过初步的探索，但是没有分析过三层大目录的结构及变化规律。

本文通过分析NTFS分区中大目录产生的原因、结构，通过实验动态跟踪在三层大目录下创建和删除文件对大目录结构产生的影响并得出变化规律。对于大目录频繁操作可能产生的0X20属性原因和其结构进行分析。文章的最后给出改进大目录MFT 文件记录的方法并进行实验。

1 NTFS重要的数据结构简介

NTFS文件系统由元数据（metadata）文件和普通用户文件组成，元数据文件用来文件管理、文件定位、引导程序数据、整个卷分配位图、错误恢复等信息。元数据文件除MYMBoot文件外，其他元数据文件的位置是可变的［1］。

1.1 MFT文件记录结构

在NTFS文件系统中，每个文件（包括元文件）都有一个或多个MFT 记录，大小为1KB。MFT 记录由记录头和一组属性组成，各个属性之间相互独立并有各自的类型和名称。MFT 记录中属性如表1［1］所示。

1.2 索引项结构分析

NTFS文件系统中文件夹与它所包含的文件（或文件夹，下同）的关系是通过索引来建立的，一个文件夹下文件的索引在父文件夹MFT 记录的0X90 属性或数据运行（DataRun）中，一个文件夹下所有文件的索引构成一个B＋树的结构，这种数据结构便于快速的查找。索引的排序是按照MYMUpCase元数据文件的定义来完成了，而非简单Unicode编码［5］。一个索引包含了自身MFT 参考号、索引的大小、文件的属性、父目录的MFT 参考号，文件名等字段。如果该索引在B＋树结构中为非叶子节点，最后的增加8Bytes的长度用于保存子节点索引缓冲区的VCN号。表2显示了索引项各字段的含义。

表2 索引项各字段的含义

2 NTFS大目录结构解析

2.1 产生大目录的条件

当文件夹下的文件较少时，文件索引直接放在父目录MFT 记录的0X90属性中（长度一般为0X58～0X80Bytes，跟索引的文件名长度相关）。一个文件的MFT 记录大小为1KB，当父目录下的文件不断增加而生成新的索引项，父目录MFT 记录没有足够的空间存放时，会按照B＋树的节点分裂规则进行分裂，B＋树的根节点保留在父目录的MFT 记录中，此时根节点中的索引项长度增加8Bytes用来指向其子节点索引缓冲（VCN）。同时父目录MFT 记录中会添加两个属性0XA0属性和0XB0属性，分别用于存放B＋树的所有子节点VCN的位置信息和VCN号的分配情况。将分裂出来的索引项存放到VCN 所指向的数据运行（Data－Run，大小为4KB）中，此时产生了两层的B＋目录结构（文献［5］图3提到的三层实际是二层B＋树目录，只是将一个指向两层B＋树的指针放到MFT 记录中）。当文件夹下的文件数量一直增加，到一个临界点，两层的B＋树目录不足以存放所有的索引项时，B＋树第二层的一些节点会根据B＋树的分裂规则分离出叶子节点，自身成为非叶子节点，此时变成了三层B＋树结构（下文重点分析这种结构）。如果继续添加大量的索引项，三层B＋树的根节点会膨胀已达到饱和，三层B＋树的根节点在父目录的MFT 记录没有足够的空间存放，则会在父目录的MFT 记录中生成一个空节点，原根节点存放在一个新的DataRun中，此时MFT 记录存放的是一个指向三层B＋树结构的指针（Windows 7 中的System32文件夹这种目录结构比较常见）。

2.2 三级大目录存放的索引数目

假设三级B＋树大目录中存放的索引平均长度为0X60Bytes，每个DataRun 4KB空间存满的情况下可以存放42个索引项，这里取B＋树的阶为30，如果三层B＋大目录树所有DataRun按照阶的限制全部存满，则每层存放的索引项数目分别为：

第一层B＋树存放的索引项数目：30

第二层B＋树存放的索引项数目：30＊30＝900

第三层B＋树存放的索引项数目：30＊30＊30＝27000

三层B＋树存放的索引项总数：30＋900＋27000＝27930

从上述分析可以，三层B＋树目录结构完全能满足一个超大型文件夹的下文件数量的要求。

2.3 三层大目录结构分析

分析三层大目录之前，先分析一下0XA0 属性的数据运行列表的字段含义和计算方法。在0XA0属性偏移0X48处是DataRun列表。每个DataRun列表的长度不一定相等，但是各个DataRun列表前后相接，计算后一个DataRun列表中的值需要用到前一个DataRun列表的计算结果。

计算目标索引缓冲区节点的LCN号，首先要定位到第一个DataRun列表的位置，读取该列表的起始LCN和该列表标识的索引缓冲区节点个数（L1），比较目标VCN号和L1，如果小于则在目标缓冲区在该列表中，否则查找下一个列表，后一个DataRun列表的位置依据前面的DataRun列表的长度而定，DataRun列表各字段的含义及计算方法如表3所示。

图1显示了一个DataRun列表在磁盘的物理结构。

根据表3的计算方法得出每个DataRun LCN的结果，见表4。

判断索引缓冲区是不是叶子节点的依据是看节点偏移0X24的值，为1表示非叶子节点，为0表示叶子节点。

图2为Windows XP SP3 系统的System32 大文件夹的三层大目录结构（不同磁盘上的目录结构会有差异）。

表3 DataRun列表各字段的含义及计算方法

图1 数据运行列表

表4 DataRun各LCN号

图2 System32文件夹三层B＋树结构

2.4 三层大目录结构变化规律

在三层B＋树（m 阶）大目录中创建和删除文件要进行比较复杂的计算，可能要调整B＋树的结构，会导致操作时间较长。

2.4.1 删除文件B＋结构变化规律

（1）删除的B＋树叶子节点中的一个索引项，如果删除后该叶子节点的关键字个数大于等于「m／2」－1，直接删除索引节点。如删除mmc.exe，INDX节点调整后如图3所示。

（2）如果删除后该叶子节点的关键字个数小于「m／2」－1，会引起B＋树结构的调整。按照B＋树的删除规则进行变换。如删除INDX节点（VCN＝0X0D）中后一半的索引项，将相邻的叶子节点的一部分索引移至该节点，并将节点的最后一个索引上移一层并指向该节点（MPSSVC.dll索引上移一层），B＋树结构调整后如图4所示。

（3）删除非叶子节点中的索引项，绝大多数情况将索引项所指向INDX 节点中最后一个索引项替换删除索引项的位置，删除索引项的VCN 值不变，如果指向的INDX 也是非叶子节点，继续用下层替换。如下图中删除第二层的“索引项21N”和第一层的“索引项23N”B＋树变化结果。如图5所示。

（4）在大目录中删除索引项的情况种类繁多，上面列举最常见的三种。其他种类按照B＋树节点中关键的删除规则进行处理。

2.4.2 添加文件B＋树变化规律

在三层大目录中创建一个文件（或文件夹）首先根据父目录和自身MFT 记录生成索引项，再从B＋树根节点处开始逐层查找合适的插入位置，查找的过程如下。

（1）用待创建文件的文件名（下简称待插入项）依次顺序和0X90属性的（或INDX 节点索引项中的文件名（下简称索引项））比较（按照MYMUpCase排序规则），直到第一次比较大于索引项并使用该索引项中的VCN 查找下一层；如果0X90属性中只有空索引则使用空索引中的VCN查找下一层。

（2）将查找到的VCN 使用0XA0 属性中的数据运行（DataRun）计算出LCN。

（3）读出LCN 指向的INDX，查看INDX 是否为叶子节点，如果是叶子节点，在INDX 中顺序查找第一个比待插入项大的索引项。此时待插入项的插入位置在这个索引项的前面，则查找位置成功。如果是非叶子节点按照（1）继续递归进行查找。

如果插入索引后叶子节点的关键字个数大于B＋树的阶或者导致INDX 节点溢出，这时必须按照B＋树的分裂规则进行INDX 节点分裂。

在实际的创建和删除文件的操作中，直接对叶子节点处理耗时较短，如何对B＋树结构做大范围的调整则耗时较长，所以在大目录中创建和删除文件有时需要等待一段时间。

如在System32文件夹下插入文件MicrosoftInsert.txt，结果如图6所示。

2.5 大目录结构下的0X20属性分析

在三层B＋树大目录中很容易产生其他中小型目录中见不到的0X20 属性，0X20 属性是MYMATTRIBUTE＿LIST 属性，当一个文件的MFT 记录中有很多属性或者有些属性体很大时就会在主MFT 中生成0X20 属性，此时NTFS会给再分配一个MFT（次）记录给该文件，用于存放主MFT 记录存储不下的属性。0X20属性就是用来指标哪些属性在主MFT 记录中哪些属性在次MFT 记录中。

图6 三层B＋树结构中插入MicrosoftInsert.txt索引项

0X20属性很少见，只是在三层B＋树目录结构中可能见到，却是大目录存在的重要特征。有四种情况可能需要0X20属性。

（1）文件有很多的硬链接（即有很多的文件名属性存在）。

（2）文件夹下不断有新的文件产生，产生了很多碎片，一个MFT 记录不足以保存下这么多碎片的DataRun。

（3）文件有很复杂的安全描述符（不适用于NTFS v4.0以上的版本）。

（4）属性中有很多的命名流。

0X20属性各字段的含义如表5所示。

表5 0X20属性各字段含义

0X20出现在一个文件有多个MFT 记录的情况下，它描述了非0X20属性所属的MFT。

3 改进NTFS大目录结构

3.1 消除0X20属性方案

当一个文件产生0X20属性时，则说明文件至少具有两个MFT 记录用来存储常驻属性。这种特殊的情况给编写操作NTFS分区的程序带来了困难，对多个MFT 记录处理会显著降低NTFS文件系统效率。很有必要对这种结构进行改进。从分析的结果看，常常0X20属性要占用很大的空间0X80～0X120Bytes之间，但是放到第二个MFT 记录中的属性占用的空间不大，常常比0X20属性的占用的空间少。所以在大多数情况下0X20属性是没有必要的。不清楚为什么Microsoft公司没有用一种更好的方式处理0X20 属性。下面提出一种消除0X20 属性的方法，将一个文件的两个MFT 记录变成一个MFT 记录的方法。

（1）读MFT 记录头部长度字段，跳到0X10属性开始处，根据0X10属性的长度，跳到0X20属性。

（2）在0X20 属性，检索每个属性的所在的MFT号，找到次MFT 记录和其中的属性组，保存属性组，计算属性组的长度；计算主MFT 记录最大可用空间，0X400－主MFT 记录的实际长度＋0X20 属性的长度。如果属性组长度小于等于最大可用空间，则下一步，否则退出。

（3）读取0X20属性的后面的所有属性并保存。

（4）消除MFT 记录更新序列号，将主MFT 记录中的0X20属性后面的属性组与次MFT 记录的属性组依次比较属性类型，按照大小从0X20开始处存放。

（5）所有属性在主MFT 记录中存放完毕后，在最后加上0XFFFFFFFF结束标识。

（6）更新主MFT 记录偏移0X18 处的MFT 记录实际长度字段。值更新为：原MFT 实际长度－0X20属性长度＋次MFT 记录中属性组的长度。

（7）写回更新序列号：将主MFT 记录的第一、第二个扇区的最后两个字节分别到0X32～0X35 偏移处的更新数组处，再将0X30～0X31的更新序列号写到MFT 记录的第一和第二个扇区的最后两个字节。主MFT 记录修改完毕。

（8）添加删除标志：将次MFT 记录的0X16处的删除标志更新为0X00（MFT 被删除）或0X02（目录被删除）。

（9）根据次MFT 记录的MFT号，在MYMMFT：BitMap中找到对应的位，将1更新为0，表示次MFT 记录删除。流程图如图7所示、实验结果图8所示。

随着系统的使用不断会有新的应用程序安装，在系统文件夹（Windows、System32 等）产生新的文件。这些文件夹下的文件数量不断的增加，每过一段时间就会分配一个新的索引缓冲区用于存放。这样很容易产生缓冲区碎片，影响系统的性能。在每次生成新的索引缓冲区节点时，如果前面有比较多的碎片，可以将前面的碎片合并成一个大块的缓冲区组，便于提升系统的性能。

图7 操作合并MFT 记录流程

图8 合并MFT 记录的实验操作结果

3.2 大目录优化效果

消除System32文件夹0X20属性并合并分散的数据运行。实验室硬件设备Lenovo杨天M4600N，Windows XP SP3系统。使用自制小工具使用自制小工具ReadBigDirectory读取System32文件夹下所有文件的文件名，为了确保测试精度，时间使用64位的Windows文件时间（UTC 格式），以100毫微秒为间隔的间隔数。工具核心代码为：

DateTime startTime＝DateTime.Now；

string path＝txtDirectory.Text；

string［］fileNames＝Directory.GetFiles（path，" ＊.＊"，SearchOption.TopDirectoryOnly）；

DateTime endTime＝DateTime.Now；

图9 程序运行界面

由于Windows会缓存已操作过的结果，每次系统重新启动第一次运行测试程序结果有效。对目录优化前后分别做5次数据采集，取平均值，结果如表6所示（单位毫秒）。

表6 优化前后操作大目录时间

优化前后的对比结果可以看出，查找System32文件下所有文件的时间缩短了19.389毫秒，优化后有较好的效果。

4 结束语

NTFS B＋树大目录数据结构复杂，是理解NFTS文件系统目录管理的难点，也是设计NTFS文件系统操作程序的关键。本文详细地分析三层B＋树大目录产生的原因、结构和动态变化规律，在此基础上分析大目录中可能会产生的0X20属性结构，并提出改进有0X20属性MFT记录的方法。

最后实验验证了对NTFS大目录的分析结果。该分析结果为开发操作NTFS 文件系统的程序提供了理论支持。同时提出改进NTFS文件系统效率的方法。

［1］Microsoft TechNet.Optimizing NTFS［EB／OL］.［2011－12－08］.http：／／technet.microsoft.com／en－us／library／cc767961.aspx，2010.

［2］Carrier B.File system forensic analysis［M］.Pearson Education，Inc，2009：369－380.

［3］ZHANG Kai.Analysis and implementation of NTFS file system based on computer forensics［C］／／ETCS，2010：325－328.

［4］Huebner E，Bem D，Wee C K.Data hiding in the NTFS file system［J］.Digital Investigation，2006，3（4）：211－226.

［5］WANG Lina，YANG Mo.Computer forensics research and implementation based on NTFS file system［J］.Journal－Wuhan University Natural Sciences Edition，2006，52（5）：519.

［6］WANG Lanying，JU Jinwu.Analysis of NTFS file system structural［J］.Computer Engineering and Design，2006，27（3）：418－420（in Chinese）.［王兰英，居锦武.NTFS文件系统结构分析［J］.计算机工程与设计，2006，27（3）：418－420.］

［7］JU Jinwu，WANG Lanying.Analysis of NTFS file system［J］.Computer Engineering and Design，2007，28（22）：5437－5460（in Chinese）.［居锦武，王兰英.NTFS文件系统剖析［J］.计算机工程与设计，2007，28（22）：5437－5460.］

［8］ZHAO Shuangfeng，FEI Jinlong，LIU Nan，et al.Research and implementation of data recovery on Windows NTFS［J］.Computer Engineering and Design，2008，29（2）：306－308（in Chinese）.［赵双峰，费金龙，刘楠，等.Windows NTFS下数据恢复的研究与实现［J］.计算机工程与设计，2008，29（2）：306－308.］

［9］WU Weimin，LU Qi，WANG Zhenhua，et al.Dynamic analysis of B＋tree structure of index in NTFS directory［J］.Computer Engineering and Design，2010（22）：4843－4846（in Chinese）.［吴伟民，卢琦，王振华，等.NTFS目录下索引B＋树结构动态解析［J］.计算机工程与设计，2010（22）：4843－4846.］

［10］Faraz Ahsan，Ikram Lali M.Exploring the effect of directory depth on file access for FAT and NTFS file systems［C］／／ISTASC，2008：130－135.