B－树在NTFS索引目录管理中的应用研究

陈培德，吴建平，王丽清

(云南大学信息学院云南省高校数字媒体技术重点实验室，云南昆明 650223)

B－树在NTFS索引目录管理中的应用研究

陈培德，吴建平，王丽清

(云南大学信息学院云南省高校数字媒体技术重点实验室，云南昆明 650223)

目前国内一些有关NTFS文件系统的书籍或杂志认为NTFS对索引目录的管理是采用B+树结构，而只有少量书籍中认为NTFS对索引目录的管理是采用B-树结构。针对这种争议，以Windows7操作系统为平台，以NTFS文件系统和文件目录为研究分析对象，用WinHex磁盘编辑为分析工具，对NTFS文件系统中元文件$MFT文件夹记录的90H属性、A0H属性和B0H属性进行分析。以B-树的定义为衡量标准，对NTFS文件系统索引目录中的文件进行查找、删除和插入操作，来观察NTFS文件系统索引目录的结构变化。实验结果表明，NTFS索引目录基本符合B-树的定义。NTFS文件系统对索引目录的管理是采用B-树结构，但并非是标准的B-树结构。

NTFS文件系统;B-树;索引节点;索引目录

0 引言

NTFS文件系统是随着Windows NT的第一个版本推出的一个性能优良的文件系统，目前已是Windows系列操作系统的重要组成部分。该系统对索引目录的管理非常复杂，国内少量有关NTFS文件系统的书籍认为:NTFS文件系统对索引目录的管理采用的是B-树结构。如:NTFS对文件目录采用B-树进行管理，这种技术比在FAT文件系统中使用链表技术管理优越得多［1］;NTFS利用B-Tree文件管理方法跟踪文件在磁盘上的位置［2］;一个NTFS索引排序属性为一棵树，尤其是一棵B-树，NTFS使用B-树，其与二叉树相似，但每个节点超过了两个孩子［3］，等等。

1 B－树的定义

一棵m阶的B-树满足下列5个条件:

(1)每个节点至多有m个孩子;

(2)除根节点和叶节点外，其他每个节点至少有「m/2⌉ 个孩子;

(3)根节点至少有两个孩子(唯一例外的是只包含一个根节点的B-树);

(4)所有的叶节点在同一层，叶节点不包含任何关键字信息;

(5)有k个孩子的非叶节点恰好包含k-1个关键字［4］。

在B-树中每个节点的关键字从小到大排列。因为叶节点不包含关键字，所以，叶节点实际上是树中并不存在的外部节点，且指向这些外部节点的指针为空，叶节点的总数正好等于树中的关键字总数加1［4］。

2 文件夹记录的90H、A0H和B0H属性

在NTFS文件系统中最重要的元文件就是$MFT，它是NTFS卷中所有文件和文件夹的集合［5-7］。在元文件$MFT中的文件夹记录中与文件夹相关的属性主要有90H、A0H和B0H［8-10］。

90H属性即$INDEX_ROOT属性，在$MFT记录中只有记录项为目录(即文件夹)才有该属性，它总是常驻有属性名的属性。在90H属性中常用到的索引项类型为文件名索引，名称为$I30。NTFS对目录的管理采用B-树结构，该属性是实现NTFS的B-树的根节点［1］。

A0H属性也就是索引分配属性，存储着组成索引的目录结构的所有节点的定位信息。它总是非常驻属性，没有最大最小值限制［1］。

B0H属性即位图属性，它是由一系列的二进制位所构成的虚拟分配单元使用情况表。每一位代表一个分配单元的使用情况。该位为“0”时表示所对应的分配单元未使用，为“1”时表示所对应的分配单元已使用或者分配单元已坏(如果分配单元已坏，在元文件$BadClus中会有记载)。一个分配单元在操作系统引导记录(英文全称 DOS Boot Record，缩写为DBR［11-15］)中已有定义，可以是1个簇，也可以是1个扇区，也可以是2个扇区，等等。

B0H属性目前主要使用在两个地方:即索引目录和元文件$MFT中［11-15］。在索引目录中，该属性一般为常驻属性，每一位表示一个索引节点号的使用情况。如果该位为“1”，表示所对应的索引节点有效;为“0”表示所对应的索引节点无效。

3 NTFS中的B－树

实验环境:

(1)操作系统:Windows 7;

(2)分析工具:WinHex 15.08。

实验步骤:

(1)在Windows 7下的D盘建立一个名为abcd. vhd的文件，文件大小为500 MB;

(2)使用Windows 7的虚拟硬盘管理附加abcd. vhd文件为虚拟硬盘，在虚拟硬盘上建立一个MBR分区，分区大小为466 MB，将该分区格式化为NTFS，分配单元大小选择4 096;

(3)在虚拟硬盘上建立一个文件夹，在该文件夹中建立1 000个文件名，文件名为a000～a999，其B-树结构如图1所示。

对图1说明如下:

(1)在文件夹中存储了1 000个文件，这1 000个文件名分别存储在文件夹记录的90H属性、00～51号节点中。其中:06号和38号为非叶节点，而00～05号，07～37号，39～51号为叶节点。

(2)在90H属性(即B-树的根节点)中存储1个索引文件名(即a359)和2个索引节点号(即06和38)，与B-树定义的第3条相符。

(3)在06号非叶节点中存储了17个索引文件名(即a019，a039，…，a339)和18个指针(号为00～05，07 ～18);未发现90H属性中的索引文件名a359;与B-树定义第5条相符，此时k=18，即有18个孩子(即指针)的非叶节点恰好包含17个关键字(即文件名)。

(4)在38号非叶节点中存储了31个索引文件名(即a379，a399，…，a979)和32个指针(指针号为19～37，39～51);与B-树定义第5条相符，此时k=32，即有32个孩子(即指针)的非叶节点恰好包含31个关键字(即文件名)。

(5)在各叶节点(即00～05号，07～37号，39～51 号)中均未发现90H属性、06号非叶节点和38号非叶节点中的索引文件名，与B-树定义的第4条相符。

(6)叶节点总数为50个，而关键字总数为49个，这与B-树的定义最后叙述相符(即叶节点的总数正好等于树中所包含的关键字总数加1)。

4 NTFS的B－查找分析

查找a359文件，在文件夹记录的90H属性就命中。

查找a059文件，将a059文件名与a359文件名进行比较，由于a059＜a359，而a059存储在06号非叶节点;通过折半查找的方式在06号非叶节点中命中。

查找a324文件，将a324文件名与a359文件名进行比较，由于a324＜a359，所以a324又与06号非叶节点中的a339比较;由于a324＜a339，因此，a324文件在17号叶节点中通过折半方式与17号叶节点中所存储的文件进行比较，在17号叶节点中命中。

查找a350文件，将a350文件名与a359文件名进行比较，由于a350＜a359，所以a350又与06号非叶节点中的a339文件进行比较;由于a350＞a339，因此，a350文件在18号叶节点中通过折半方式与18号叶节点中所存储的文件进行比较，在18号叶节点中命中。

5 NTFS中B－树的删除

1)将存储在90H属性中、06号和38号非叶节点中的所有文件(即a019，a039，…，a979，共计49个文件)删除后，其B-树结构如图2所示。

从图1到图2有如下变化:

(1)将18号叶节点中的文件名a358上移至文件夹记录的90H属性中;

(2)将00号～17号叶节点中的文件名 a018，a038，…，a338上移至06号非叶节点中;

(3)将19号～50号叶节点中的文件名 a378，a398，…，a978上移至38号非叶节点中。

2)删除a340～a377文件(即存储在90H属性、18号和19号节点中的文件)后，B-树结构如图3所示。

从图2到图3有如下变化:

(1)将06号非叶节点中的文件名a338上移至文件夹记录的90H属性中;

(2)存储在38号非叶节点中的文件名a378下移至20号叶节点中;

(3)由于18号和19号叶节点中的文件已被删除，18和19号叶节点已不再起作用，文件夹记录的B0H属性所记录的索引节点状态值由“1”变为“0”。

3)删除a001～a017、a021～a037共计34个文件，其B-树结构如图4所示。

图4 存储880个文件的B-树结构图(1)

从图3到图4有如下变化:

(1)将a001～a017文件删除后，00号叶节点只存储一个文件，文件名为a000;

(2)将a021～a037文件删除后，01号叶节点只存储一个文件，文件名为a020。

6 NTFS中B－树的插入

1)在该文件夹中复制 22个文件，文件名为a97700～a97721，其B-树如图5所示。

将a97700～a97721文件插入后，由于 a97700＞a977，而a97721＜a978，所以，a97700～a97721文件名存放在50号叶节点中，位于a977之后，在该叶节点中共存储了40个文件名。

2)在该文件夹中复制 1个文件，文件名为a97722，其B-树如图6所示。

将a97722文件插入后，由于a97722＞a97721，所以，a97722存放在a97721文件名之后，由于该叶节点的空间为4 096字节，无法再存储文件名，将该叶节点进行分离。而18号叶节点和19号叶节点未使用，NTFS文件系统将使用18号叶节点，将50号叶节点分离后，50号叶节点存储的文件名为a960～a977，a97700，共计19个。

将a97701文件名上移至38号非叶节点，位于a958和a975之间;而将a97702～a97722文件名移动到18号叶节点中，完成节点的分离。

7 结束语

在NTFS文件系统中索引目录主要存储在文件夹记录的90H属性和各个索引节点中，90H属性为B-树的根节点。但该节点并未完全遵循B-树的定义“根节点至少有两个孩子(唯一例外的是只包含一个根节点的B-树)”。各个索引节点的位置通过文件夹记录的A0H属性的数据运行列表来定位，文件夹记录的B0H属性记录了各索引节点的状态。每个索引节点的大小固定为4 096字节，各索引节点所包含的孩子数取决于文件名长度。当索引节点中文件数量不断增加，一个索引节点容纳不下时，将该索引节点进行分离。

总之，NTFS文件系统对索引目录的管理是采用B-树结构，但并非是一棵标准的B-树结构。

［1］ 陈培德，吴建平，王丽清.NTFS文件系统实例详解［M］.北京:国防工业出版社，2015.

［2］ 张钟澍，陈代军，李新萌.修复和维护你的硬盘［M］.北京:北京希望电子出版社，2002.

［3］ Carrier B.File system forensic analysis［M］.［s.l.］:Addison Wesley Professional，2005.

［4］ 唐策善，李龙澍，黄刘生.数据结构─用C语言描述［M］.北京:高等教育出版社，2006.

［5］ 吴伟民，刘 凯，江达强，等.NTFS B+树大目录结构动态解析［J］.计算机工程与设计，2013，34(4):1376-1382.

［6］ 吴伟民，林水宾，江达强，等.基于NTFS大目录的文件创建方法［J］.计算机应用，2014，34(2):417-420.

［7］ 吴伟民，卢 琦，王振华，等.NTFS目录下索引B+树结构动态解析［J］.计算机工程与设计，2010，31(22):4843-4846.

［8］ Fathi B.深入解析Windows操作系统(英文版)［M］.第5 版.北京:人民邮电出版社，2009.

［9］ Ionescs A.NTFS on-disk structure:visual basic NTFS programmer’s guide［EB/OL］.2009.http://www.alex-ionescu. com.

［10］Microsoft TechNet.Optimizing NTFS:disabling unnecessary access updates［EB/OL］.2010.http://technet.microsoft.com/en -us/library/cc7679 61.aspx.

［11］刘 伟.数据恢复技术深度揭秘［M］.北京:电子工业出版社，2010.

［12］马 林.数据重现─文件系统原理精解与数据恢复最佳实践［M］.北京:清华大学出版社，2009.

［13］汪中夏，张京生，刘 伟.RAID数据恢复技术揭秘［M］.北京:清华大学出版社，2010.

［14］戴士剑，涂彦晖.数据恢复技术［M］.北京:电子工业出版社，2005.

［15］刘乃琦，郭建东，张 可.系统与数据恢复技术［M］.成都:电子科技大学出版社，2008.

Study on Application of Index Directories in NTFS by B-tree

CHEN Pei-de，WU Jian-ping，WANG Li-qing
(Key Laboratory of Digital Media Technology of Universities and Colleges in Yunnan Province，School of Information Science and Engineering，Yunnan University，Kunming 650223，China)

The method for managing the index directories in NTFS is thought to use the B+tree data structure in many books and magazines，and the B-tree data structure is used in the less books in the inland.Aiming at the dispute，taking the Windows7 Operation System as platform，the file directories in the NTFS as the analytic object，the WinHex as analytic tool，the attribute of 90H，A0H and B0H is analyzed in folder record for metafile$MFT in NTFS.The definition of B-tree is used for the judgment standard.The files in the NTFS index directories are found，deleted，inserted，and to be observed the structure change of NTFS index directories.The results of experiment indicate that the NTFS index directories is accorded with basically the B-tree structure definition.The B-tree structure is used for the index directories in NTFS，but it’s not a standard B-tree structure.

NTFS;B-tree;index node;index directories

TP311.12

:A< class="emphasis_bold">文章编号:1

1673-629X(2016)09-0030-04

10.3969/j.issn.1673-629X.2016.09.007

2015-12-02< class="emphasis_bold">修回日期:2

2016-03-09< class="emphasis_bold">网络出版时间:

时间:2016-08-01

云南省科技创新强省计划项目(2014AB021);云南省高校数字媒体重点实验室开放基金项目(2015KFKT002)

陈培德(1966-)，男，工程师，研究方向为文件系统与数据恢复技术。

http://www.cnki.net/kcms/detail/61.1450.TP.20160801.0904.040.html