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.