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