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

陳培德，吳建平，王麗清

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

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

陳培德，吳建平，王麗清

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

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

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

0 引言

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

1 B－樹(shù)的定義

一棵m階的B-樹(shù)滿足下列5個(gè)條件:

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

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

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

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

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

在B-樹(shù)中每個(gè)節(jié)點(diǎn)的關(guān)鍵字從小到大排列。因?yàn)槿~節(jié)點(diǎn)不包含關(guān)鍵字，所以，葉節(jié)點(diǎn)實(shí)際上是樹(shù)中并不存在的外部節(jié)點(diǎn)，且指向這些外部節(jié)點(diǎn)的指針為空，葉節(jié)點(diǎn)的總數(shù)正好等于樹(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對(duì)目錄的管理采用B-樹(shù)結(jié)構(gòu)，該屬性是實(shí)現(xiàn)NTFS的B-樹(shù)的根節(jié)點(diǎn)［1］。

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

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

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

3 NTFS中的B－樹(shù)

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

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

(2)分析工具:WinHex 15.08。

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

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

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

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

對(duì)圖1說(shuō)明如下:

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

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

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

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

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

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

4 NTFS的B－查找分析

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

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

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

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

5 NTFS中B－樹(shù)的刪除

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 NTFS中B－樹(shù)的插入

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

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

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

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

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

7 結(jié)束語(yǔ)

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

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

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

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

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

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

［5］ 吳偉民，劉 凱，江達(dá)強(qiáng)，等.NTFS B+樹(shù)大目錄結(jié)構(gòu)動(dòng)態(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+樹(shù)結(jié)構(gòu)動(dòng)態(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">文章編號(hào):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)室開(kāi)放基金項(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