B－樹在NTFS索引目錄管理中的應(yīng)用研究

陳培德，吳建平，王麗清

(云南大學(xué)信息學(xué)院云南省高校數(shù)字媒體技術(shù)重點(diǎn)實(shí)驗(yàn)室，云南昆明 650223)

B－樹在NTFS索引目錄管理中的應(yīng)用研究

陳培德，吳建平，王麗清

(云南大學(xué)信息學(xué)院云南省高校數(shù)字媒體技術(shù)重點(diǎn)實(shí)驗(yàn)室，云南昆明 650223)

目前國內(nèi)一些有關(guān)NTFS文件系統(tǒng)的書籍或雜志認(rèn)為NTFS對索引目錄的管理是采用B+樹結(jié)構(gòu)，而只有少量書籍中認(rèn)為NTFS對索引目錄的管理是采用B-樹結(jié)構(gòu)。針對這種爭議，以Windows7操作系統(tǒng)為平臺，以NTFS文件系統(tǒng)和文件目錄為研究分析對象，用WinHex磁盤編輯為分析工具，對NTFS文件系統(tǒng)中元文件$MFT文件夾記錄的90H屬性、A0H屬性和B0H屬性進(jìn)行分析。以B-樹的定義為衡量標(biāo)準(zhǔn)，對NTFS文件系統(tǒng)索引目錄中的文件進(jìn)行查找、刪除和插入操作，來觀察NTFS文件系統(tǒng)索引目錄的結(jié)構(gòu)變化。實(shí)驗(yàn)結(jié)果表明，NTFS索引目錄基本符合B-樹的定義。NTFS文件系統(tǒng)對索引目錄的管理是采用B-樹結(jié)構(gòu)，但并非是標(biāo)準(zhǔn)的B-樹結(jié)構(gòu)。

NTFS文件系統(tǒng);B-樹;索引節(jié)點(diǎn);索引目錄

0 引言

NTFS文件系統(tǒng)是隨著Windows NT的第一個版本推出的一個性能優(yōu)良的文件系統(tǒng)，目前已是Windows系列操作系統(tǒng)的重要組成部分。該系統(tǒng)對索引目錄的管理非常復(fù)雜，國內(nèi)少量有關(guān)NTFS文件系統(tǒng)的書籍認(rèn)為:NTFS文件系統(tǒng)對索引目錄的管理采用的是B-樹結(jié)構(gòu)。如:NTFS對文件目錄采用B-樹進(jìn)行管理，這種技術(shù)比在FAT文件系統(tǒng)中使用鏈表技術(shù)管理優(yōu)越得多［1］;NTFS利用B-Tree文件管理方法跟蹤文件在磁盤上的位置［2］;一個NTFS索引排序?qū)傩詾橐豢脴洌绕涫且豢肂-樹，NTFS使用B-樹，其與二叉樹相似，但每個節(jié)點(diǎn)超過了兩個孩子［3］，等等。

1 B－樹的定義

一棵m階的B-樹滿足下列5個條件:

(1)每個節(jié)點(diǎn)至多有m個孩子;

(2)除根節(jié)點(diǎn)和葉節(jié)點(diǎn)外，其他每個節(jié)點(diǎn)至少有「m/2? 個孩子;

(3)根節(jié)點(diǎn)至少有兩個孩子(唯一例外的是只包含一個根節(jié)點(diǎn)的B-樹);

(4)所有的葉節(jié)點(diǎn)在同一層，葉節(jié)點(diǎn)不包含任何關(guān)鍵字信息;

(5)有k個孩子的非葉節(jié)點(diǎn)恰好包含k-1個關(guān)鍵字［4］。

在B-樹中每個節(jié)點(diǎn)的關(guān)鍵字從小到大排列。因?yàn)槿~節(jié)點(diǎn)不包含關(guān)鍵字，所以，葉節(jié)點(diǎn)實(shí)際上是樹中并不存在的外部節(jié)點(diǎn)，且指向這些外部節(jié)點(diǎn)的指針為空，葉節(jié)點(diǎn)的總數(shù)正好等于樹中的關(guān)鍵字總數(shù)加1［4］。

2 文件夾記錄的90H、A0H和B0H屬性

在NTFS文件系統(tǒng)中最重要的元文件就是$MFT，它是NTFS卷中所有文件和文件夾的集合［5-7］。在元文件$MFT中的文件夾記錄中與文件夾相關(guān)的屬性主要有90H、A0H和B0H［8-10］。

90H屬性即$INDEX_ROOT屬性，在$MFT記錄中只有記錄項(xiàng)為目錄(即文件夾)才有該屬性，它總是常駐有屬性名的屬性。在90H屬性中常用到的索引項(xiàng)類型為文件名索引，名稱為$I30。NTFS對目錄的管理采用B-樹結(jié)構(gòu)，該屬性是實(shí)現(xiàn)NTFS的B-樹的根節(jié)點(diǎn)［1］。

A0H屬性也就是索引分配屬性，存儲著組成索引的目錄結(jié)構(gòu)的所有節(jié)點(diǎn)的定位信息。它總是非常駐屬性，沒有最大最小值限制［1］。

B0H屬性即位圖屬性，它是由一系列的二進(jìn)制位所構(gòu)成的虛擬分配單元使用情況表。每一位代表一個分配單元的使用情況。該位為“0”時(shí)表示所對應(yīng)的分配單元未使用，為“1”時(shí)表示所對應(yīng)的分配單元已使用或者分配單元已壞(如果分配單元已壞，在元文件$BadClus中會有記載)。一個分配單元在操作系統(tǒng)引導(dǎo)記錄(英文全稱 DOS Boot Record，縮寫為DBR［11-15］)中已有定義，可以是1個簇，也可以是1個扇區(qū)，也可以是2個扇區(qū)，等等。

B0H屬性目前主要使用在兩個地方:即索引目錄和元文件$MFT中［11-15］。在索引目錄中，該屬性一般為常駐屬性，每一位表示一個索引節(jié)點(diǎn)號的使用情況。如果該位為“1”，表示所對應(yīng)的索引節(jié)點(diǎn)有效;為“0”表示所對應(yīng)的索引節(jié)點(diǎn)無效。

3 NTFS中的B－樹

實(shí)驗(yàn)環(huán)境:

(1)操作系統(tǒng):Windows 7;

(2)分析工具:WinHex 15.08。

實(shí)驗(yàn)步驟:

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

(2)使用Windows 7的虛擬硬盤管理附加abcd. vhd文件為虛擬硬盤，在虛擬硬盤上建立一個MBR分區(qū)，分區(qū)大小為466 MB，將該分區(qū)格式化為NTFS，分配單元大小選擇4 096;

(3)在虛擬硬盤上建立一個文件夾，在該文件夾中建立1 000個文件名，文件名為a000～a999，其B-樹結(jié)構(gòu)如圖1所示。

對圖1說明如下:

(1)在文件夾中存儲了1 000個文件，這1 000個文件名分別存儲在文件夾記錄的90H屬性、00～51號節(jié)點(diǎn)中。其中:06號和38號為非葉節(jié)點(diǎn)，而00～05號，07～37號，39～51號為葉節(jié)點(diǎn)。

(2)在90H屬性(即B-樹的根節(jié)點(diǎn))中存儲1個索引文件名(即a359)和2個索引節(jié)點(diǎn)號(即06和38)，與B-樹定義的第3條相符。

(3)在06號非葉節(jié)點(diǎn)中存儲了17個索引文件名(即a019，a039，…，a339)和18個指針(號為00～05，07 ～18);未發(fā)現(xiàn)90H屬性中的索引文件名a359;與B-樹定義第5條相符，此時(shí)k=18，即有18個孩子(即指針)的非葉節(jié)點(diǎn)恰好包含17個關(guān)鍵字(即文件名)。

(4)在38號非葉節(jié)點(diǎn)中存儲了31個索引文件名(即a379，a399，…，a979)和32個指針(指針號為19～37，39～51);與B-樹定義第5條相符，此時(shí)k=32，即有32個孩子(即指針)的非葉節(jié)點(diǎn)恰好包含31個關(guān)鍵字(即文件名)。

(5)在各葉節(jié)點(diǎn)(即00～05號，07～37號，39～51 號)中均未發(fā)現(xiàn)90H屬性、06號非葉節(jié)點(diǎn)和38號非葉節(jié)點(diǎn)中的索引文件名，與B-樹定義的第4條相符。

(6)葉節(jié)點(diǎn)總數(shù)為50個，而關(guān)鍵字總數(shù)為49個，這與B-樹的定義最后敘述相符(即葉節(jié)點(diǎn)的總數(shù)正好等于樹中所包含的關(guān)鍵字總數(shù)加1)。

4 NTFS的B－查找分析

查找a359文件，在文件夾記錄的90H屬性就命中。

查找a059文件，將a059文件名與a359文件名進(jìn)行比較，由于a059＜a359，而a059存儲在06號非葉節(jié)點(diǎn);通過折半查找的方式在06號非葉節(jié)點(diǎn)中命中。

查找a324文件，將a324文件名與a359文件名進(jìn)行比較，由于a324＜a359，所以a324又與06號非葉節(jié)點(diǎn)中的a339比較;由于a324＜a339，因此，a324文件在17號葉節(jié)點(diǎn)中通過折半方式與17號葉節(jié)點(diǎn)中所存儲的文件進(jìn)行比較，在17號葉節(jié)點(diǎn)中命中。

查找a350文件，將a350文件名與a359文件名進(jìn)行比較，由于a350＜a359，所以a350又與06號非葉節(jié)點(diǎn)中的a339文件進(jìn)行比較;由于a350＞a339，因此，a350文件在18號葉節(jié)點(diǎn)中通過折半方式與18號葉節(jié)點(diǎn)中所存儲的文件進(jìn)行比較，在18號葉節(jié)點(diǎn)中命中。

5 NTFS中B－樹的刪除

1)將存儲在90H屬性中、06號和38號非葉節(jié)點(diǎn)中的所有文件(即a019，a039，…，a979，共計(jì)49個文件)刪除后，其B-樹結(jié)構(gòu)如圖2所示。

從圖1到圖2有如下變化:

(1)將18號葉節(jié)點(diǎn)中的文件名a358上移至文件夾記錄的90H屬性中;

(2)將00號～17號葉節(jié)點(diǎn)中的文件名 a018，a038，…，a338上移至06號非葉節(jié)點(diǎn)中;

(3)將19號～50號葉節(jié)點(diǎn)中的文件名 a378，a398，…，a978上移至38號非葉節(jié)點(diǎn)中。

2)刪除a340～a377文件(即存儲在90H屬性、18號和19號節(jié)點(diǎn)中的文件)后，B-樹結(jié)構(gòu)如圖3所示。

從圖2到圖3有如下變化:

(1)將06號非葉節(jié)點(diǎn)中的文件名a338上移至文件夾記錄的90H屬性中;

(2)存儲在38號非葉節(jié)點(diǎn)中的文件名a378下移至20號葉節(jié)點(diǎn)中;

(3)由于18號和19號葉節(jié)點(diǎn)中的文件已被刪除，18和19號葉節(jié)點(diǎn)已不再起作用，文件夾記錄的B0H屬性所記錄的索引節(jié)點(diǎn)狀態(tài)值由“1”變?yōu)椤?”。

3)刪除a001～a017、a021～a037共計(jì)34個文件，其B-樹結(jié)構(gòu)如圖4所示。

圖4 存儲880個文件的B-樹結(jié)構(gòu)圖(1)

從圖3到圖4有如下變化:

(1)將a001～a017文件刪除后，00號葉節(jié)點(diǎn)只存儲一個文件，文件名為a000;

(2)將a021～a037文件刪除后，01號葉節(jié)點(diǎn)只存儲一個文件，文件名為a020。

6 NTFS中B－樹的插入

1)在該文件夾中復(fù)制 22個文件，文件名為a97700～a97721，其B-樹如圖5所示。

將a97700～a97721文件插入后，由于 a97700＞a977，而a97721＜a978，所以，a97700～a97721文件名存放在50號葉節(jié)點(diǎn)中，位于a977之后，在該葉節(jié)點(diǎn)中共存儲了40個文件名。

2)在該文件夾中復(fù)制 1個文件，文件名為a97722，其B-樹如圖6所示。

將a97722文件插入后，由于a97722＞a97721，所以，a97722存放在a97721文件名之后，由于該葉節(jié)點(diǎn)的空間為4 096字節(jié)，無法再存儲文件名，將該葉節(jié)點(diǎn)進(jìn)行分離。而18號葉節(jié)點(diǎn)和19號葉節(jié)點(diǎn)未使用，NTFS文件系統(tǒng)將使用18號葉節(jié)點(diǎn)，將50號葉節(jié)點(diǎn)分離后，50號葉節(jié)點(diǎn)存儲的文件名為a960～a977，a97700，共計(jì)19個。

將a97701文件名上移至38號非葉節(jié)點(diǎn)，位于a958和a975之間;而將a97702～a97722文件名移動到18號葉節(jié)點(diǎn)中，完成節(jié)點(diǎn)的分離。

7 結(jié)束語

在NTFS文件系統(tǒng)中索引目錄主要存儲在文件夾記錄的90H屬性和各個索引節(jié)點(diǎn)中，90H屬性為B-樹的根節(jié)點(diǎn)。但該節(jié)點(diǎn)并未完全遵循B-樹的定義“根節(jié)點(diǎn)至少有兩個孩子(唯一例外的是只包含一個根節(jié)點(diǎn)的B-樹)”。各個索引節(jié)點(diǎn)的位置通過文件夾記錄的A0H屬性的數(shù)據(jù)運(yùn)行列表來定位，文件夾記錄的B0H屬性記錄了各索引節(jié)點(diǎn)的狀態(tài)。每個索引節(jié)點(diǎn)的大小固定為4 096字節(jié)，各索引節(jié)點(diǎn)所包含的孩子數(shù)取決于文件名長度。當(dāng)索引節(jié)點(diǎn)中文件數(shù)量不斷增加，一個索引節(jié)點(diǎn)容納不下時(shí)，將該索引節(jié)點(diǎn)進(jìn)行分離。

總之，NTFS文件系統(tǒng)對索引目錄的管理是采用B-樹結(jié)構(gòu)，但并非是一棵標(biāo)準(zhǔn)的B-樹結(jié)構(gòu)。

［1］ 陳培德，吳建平，王麗清.NTFS文件系統(tǒng)實(shí)例詳解［M］.北京:國防工業(yè)出版社，2015.

［2］ 張鐘澍，陳代軍，李新萌.修復(fù)和維護(hù)你的硬盤［M］.北京:北京希望電子出版社，2002.

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

［4］ 唐策善，李龍澍，黃劉生.數(shù)據(jù)結(jié)構(gòu)─用C語言描述［M］.北京:高等教育出版社，2006.

［5］ 吳偉民，劉 凱，江達(dá)強(qiáng)，等.NTFS B+樹大目錄結(jié)構(gòu)動態(tài)解析［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34(4):1376-1382.

［6］ 吳偉民，林水賓，江達(dá)強(qiáng)，等.基于NTFS大目錄的文件創(chuàng)建方法［J］.計(jì)算機(jī)應(yīng)用，2014，34(2):417-420.

［7］ 吳偉民，盧 琦，王振華，等.NTFS目錄下索引B+樹結(jié)構(gòu)動態(tài)解析［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31(22):4843-4846.

［8］ Fathi B.深入解析Windows操作系統(tǒng)(英文版)［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］劉 偉.數(shù)據(jù)恢復(fù)技術(shù)深度揭秘［M］.北京:電子工業(yè)出版社，2010.

［12］馬 林.數(shù)據(jù)重現(xiàn)─文件系統(tǒng)原理精解與數(shù)據(jù)恢復(fù)最佳實(shí)踐［M］.北京:清華大學(xué)出版社，2009.

［13］汪中夏，張京生，劉 偉.RAID數(shù)據(jù)恢復(fù)技術(shù)揭秘［M］.北京:清華大學(xué)出版社，2010.

［14］戴士劍，涂彥暉.數(shù)據(jù)恢復(fù)技術(shù)［M］.北京:電子工業(yè)出版社，2005.

［15］劉乃琦，郭建東，張 可.系統(tǒng)與數(shù)據(jù)恢復(fù)技術(shù)［M］.成都:電子科技大學(xué)出版社，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">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2016-08-01

云南省科技創(chuàng)新強(qiáng)省計(jì)劃項(xiàng)目(2014AB021);云南省高校數(shù)字媒體重點(diǎn)實(shí)驗(yàn)室開放基金項(xiàng)目(2015KFKT002)

陳培德(1966-)，男，工程師，研究方向?yàn)槲募到y(tǒng)與數(shù)據(jù)恢復(fù)技術(shù)。

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