面向高效文件訪問的目錄結構優化研究

吳陽++馮徑

摘 要：針對氣象水文應用中，大量常規觀探測報文批量訪問出現的低效問題，研究文件存儲特性，定量分析了目錄級數和文件數量對訪問性能的影響，發現文件數相對于文件大小，對于系統的訪問效率影響更大，當單個目錄下文件數目過大時，文件存取延時較大，嚴重影響用戶體驗與服務性能。根據NTFS下的實驗數據，設計了一種高效的目錄組織方法，優化用戶態文件存儲管理算法。實驗表明，優化后的文件目錄結構和組織形式，能極大地提高批量文件的讀取效率，降低20%—73%的訪問延時，改善網絡環境下的大規模文件接收處理效率。

關鍵詞：存儲優化；讀取效率；目錄結構

中圖分類號：TP302.7 文獻標識碼：A

1 引言（Introduction）

隨著互聯網、物聯網、云計算等信息與通信技術的快速發展，信息系統中的數據量呈幾何級數增長。據統計，21世紀后，人類每18個月產生的數據量是之前產生的所有數據之和。大量的數據一方面為信息的獲取提供了便利，另一方面，也對數據存儲技術提出了更加嚴峻的挑戰。

在此背景下，分布式存儲系統應運而生，它具有海量數據存儲、高擴展性、高性能、高可靠性、高可用性的特點，成為當今存儲研究與應用的熱點。然而，文件系統的主要任務是管理和完成在外存中存取和搜索文件的操作，并提供透明方便、高效安全的外存應用接口，核心算法是確定磁盤或分區上的文件存儲方法和數據結構，即在磁盤上組織文件的方法。對于普通計算機使用者來說，通常無法介入文件系統的核心態進行優化和改進，但可以通過應用程序，研究和設計高效的用戶態文件存儲管理算法，包括負載均衡、存儲資源分配、文件索引、目錄結構優化等，以改善系統訪問的總體響應時間。

本文分析了現有主流文件系統的存儲特征，分析了影響文件讀取性能的因素，針對氣象水文應用中，大量常規觀探測報文批量訪問出現的低效問題，研究文件存儲特性，通過實驗跟蹤了目錄結構對讀取效率的影響，給出了一種高效訪問文件的方法。

2 文件系統存儲特征分析（The file system storage

characteristics analysis）

文件系統是操作系統的重要組成部分，由與文件管理有關軟件、被管理文件以及實施文件管理所需數據結構三部分組成，根據系統運行和部署的方式，可分為本地和分布式兩種。

2.1 本地文件系統

NTFS（New Technology File System）、FAT（File Allocation Table）、EXT（Extended File System）是當今最為廣泛使用的文件系統，主要管理本地文件。NTFS和FAT多在WINDOWS操作系統中使用，EXT多在LINUX操作系統中使用。其中，NTFS文件系統所有的數據，包括系統信息，如引導程序、記錄整個卷的分配狀態位圖和用于文件定位和恢復的數據結構等都以文件的形式存在，而且文件和目錄是以數據庫進行組織的。

NTFS卷中的任何一個文件均由位于MFT表中的文件記錄來完全描述，主控文件表MFT是NTFS中最重要的系統文件，它是一個關系數據庫，由文件記錄的數組組成，磁盤卷上的每一個文件都有一個文件記錄[1]。

記錄描述文件的第一個記錄稱為基本文件記錄，如果一個文件無法被一個基本文件記錄完全描述，系統會在MFT表中繼續為該文件分配一個或多個文件記錄，這些文件記錄稱為擴展文件記錄。

NTFS文件系統中文件夾與它所包含的文件或文件夾的關系是通過索引來建立的，一個文件夾下文件的索引在父文件夾MFT記錄的0X90屬性或數據運行中，一個文件夾下所有文件的索引構成一個B+樹的結構，這種結構適合快速查找。

三種典型文件系統的存儲特性比較如表1所示，從中可見，NTFS的所有復雜度最小，支持的操作系統最多，也是目前應用最廣泛的本地文件存儲系統，因此本文的實驗部分主要針對NTFS進行了研究。

表1 文件系統存儲特性

Tab.1 File system storage characteristics

屬性 NTFS FAT32 EXT2

簇大小 0.5kB至4kB 4kB至16kB 4kB

最大大小上限 2TB 4GB 2GB

最大分區 2TB 128GB 4TB

索引結構 B+樹 鏈式 鏈式

索引復雜度 O（logN） O（N） O（N）

支持系統 WINDOWS 2000、

WINDOWS XP DOS、WINDOWS 95

不支持 LINUX

2.2 分布式文件系統

分布式文件系統DSF（Distributed File System）是指文件系統管理的物理存儲資源不一定直接連接在本地節點上，而是通過計算機網絡與節點相連。HDFS是當今最為廣泛使用的分布式文件系統，它被設計成適合運行在通用硬件是一個高度容錯性的系統，能提供高吞吐量的數據訪問，非常適合大規模數據集上的應用[2]。

HDFS主從式的架構極大地簡化了分布式文件系統的結構，文件系統所能容納的文件數目取決于控制節點的內存大小[3]。這就導致了HDFS對海量小文件支持不理想，雖然已有技術通過小文件合并來經行優化[4]，但這一瓶頸始終限制了其在海量小文件存儲中的應用。因此HDFS在海量小文件存儲應用效率還不是很高。

3 文件存取效率分析（File access efficiency analysis）

3.1 影響存取效率的因素

不同的文件系統采用不同的索引方式進行文件定位。在NTFS文件系統中，定位文件步驟由圖1所示。endprint

圖1 NTFS的文件定位步驟

Fig.1 NTFS file access process

設文件系統定位時間為T1，與文件系統本身有關；遍歷B+樹時間為T2，與B+樹的結構有關；磁盤的控制及訪問時間為T3，與計算機的硬件性能有關。一個文件的讀取時間為TS，則

TS= T1+ T2+T3 （1）

3.2 讀取效率優化方法

在文件系統與計算機硬件條件固定的情況下，B+樹的結構對文件的存取效率影響至關重要。因此，如何減少公式（1）中T2是提高文件檢索效率的關鍵。

以NTFS為例，目錄中，文件索引放在父目錄的MFT記錄的0X90屬性中。一個文件的MFT記錄大小為1kB，當父目錄下的文件不斷增加而生成新的索引項，父目錄MFT記錄沒有足夠的空間存放時，會按照B+樹的節點分裂規則進行分裂，產生了兩層的B+目錄結構。當文件夾下的文件數量一直增加到一個臨界點，兩層的B+樹目錄不足以存放所有的索引項時，B+樹第二層的一些節點會根據B+樹的分裂規則分離出葉子節點，自身變成非葉子節點，此時變成了三層B+樹結構[5]。

樹的深度對檢索的效率有著極為關鍵的影響，理論上，B+樹的層數越大，檢索文件的所需的遍歷時間將越長，但定量的分析未見文件報道。不同的文件數量下系統中目錄會產生不同的樹結構，從而對對文件的檢索效率產生影響：

第一層B+樹存放的索引項數目為：30

第二層B+樹存放的索引項數目為：900

第三層B+樹存放的索引項數目為：27930

4 實驗及分析（Experiment and analysis）

在第3節中，已討論了讀取效率的影響因素，式（1）中T1與文件系統本身有關，視為定量，為了減少對T2的影響，在實驗中將文件進行連續的寫入以控制T3。因此，通過測量TS，便可間接得到目錄組織結構對T2的影響。

結合氣象水文應用中，常規觀探測報文特點，本文對小文件在計算機中的組織形式對檢索效率的影響進行了實驗。將大量的小文件連續寫入計算機，將其組織在不同的目錄結構中，編程實現了對每個文件的遍歷，遍歷完成后自動記錄時間。

4.1 實驗環境

操作系統：Microsoft Windows Server 2003；計算機系統配置：CPU為Intel（R）、Xeon（R）、1.86GHz，RAM為2.00GB；文件系統：NTFS；實驗分區容量：30GB。

三層B+樹目錄結構可以存放27930個索引項，滿足一個超大文件夾下文件數量的要求。當索引項超過27930時，會產生四層B+樹結構。因此分別設計了文件數為10000和100000的文件檢索實驗，代表了三層與四層B+樹的結構，也覆蓋了一般大目錄應用的條件。

4.2 實驗分析

將1萬個147kB的小文件平均存儲在N個目錄中，并統計其檢索速度，N的值為5、10、20、50、100、200、500、1000。用同樣的方法，我們還研究了10萬個文件時的檢索效率走勢，統計其結果如圖2所示。

圖2 文件檢索效率

Fig.2 File retrieval efficiency

分析實驗數據，發現目錄數在[20，50]之間時，總體檢索時間處于一個最小值的區間，因為B+樹在此區間內目錄結構的查找效率已達到最優，因此要將目錄數控制在此范圍內才能達到最優的檢索效率。

通過算法人為設置最大目錄數，從而改變系統的默認。將目錄改進后與目錄改進前的時間作對比，得到圖3和圖4。

將本文的方法與普通方法對比可得，1萬個文件時，性能提升了20%，10萬個文件時，性能提升了71.3%。

綜上所述，改進后的目錄在文件讀取上的效率有明顯，特別是在文件數目較多時，性能有顯著的提升。

圖3 1萬個文件的檢索時延對比

Fig.3 Delay contrast of 10000 files

圖4 10萬個文件的檢索時延對比

Fig.4 Delay contrast of 100000 files

5 結論（Conclusion）

本文針對大量文件訪問時出現的性能下降問題，對常用的文件系統的存儲方法進行研究，發現不論是集中式存儲還是分布式存儲，最終的讀取效率與本地數據文件的存儲結構有很大關系。在基于文件名檢索的文件系統中，文件數相對于文件大小，對于系統的訪問效率影響更大。因為，其名字空間的管理隨文件數量的變化形成數據結構上的量變到質變，這種變化使得不同操作系統隱含了最佳的目錄數和單個目錄下存放的文件數。據此，以最常用的NTFS文件為對象，通過實驗，定量分析了不同數量目錄和文件的讀取效率和變化趨勢，得出了一種簡單易行的優化方法，有效改善了海量文件存儲訪問的響應時間，特別是存在大量小文件的情形。研究結果對于提高某些應用系統性能，特別是自動文件保存和緩沖，如氣象水文觀探測報文的接收處理和批量數據交換等，有重要的工程指導意義。下一步將結合具體應用案例，將本文提出的優化存儲方法在不同文件系統中進行檢驗，并與分布式環境下的負載均衡和備份服務相結合。

參考文獻（References）

[1] 尤晉元，史美林.Windows操作系統原理[M].北京：機械工業

出版社，2001.

[2] 張春明，芮建武，何婷婷.一種Hadoop小文件存儲和讀取的方

法[J].計算機應用與軟件，2012，29（11）：95-100.

[3] 趙躍龍，等.一種性能優化的小文件存儲訪問策略的研究[J].

計算機研究與發展，2012，49（7）：1579-1586.

[4] Bo Dong，etc.A Novel Approach to Improving the Efficiency

of Storing and Accessing Small Files on Hadoop：a Case Study by

PowerPoint Files. 2010 IEEE International Conference on

Services Computing[R].

[5] 吳偉民，等.NTFS B+樹大目錄結構動態解析[J].計算機工程

與設計，2013，34（4）：1376-1382.

作者簡介：

吳 陽（1989-），男，碩士，學生.研究領域：信息與通信工程.

馮 徑（1952-），女，博士，教授.研究領域：系統集成與應用.endprint

圖1 NTFS的文件定位步驟

Fig.1 NTFS file access process

設文件系統定位時間為T1，與文件系統本身有關；遍歷B+樹時間為T2，與B+樹的結構有關；磁盤的控制及訪問時間為T3，與計算機的硬件性能有關。一個文件的讀取時間為TS，則

TS= T1+ T2+T3 （1）

3.2 讀取效率優化方法

在文件系統與計算機硬件條件固定的情況下，B+樹的結構對文件的存取效率影響至關重要。因此，如何減少公式（1）中T2是提高文件檢索效率的關鍵。

以NTFS為例，目錄中，文件索引放在父目錄的MFT記錄的0X90屬性中。一個文件的MFT記錄大小為1kB，當父目錄下的文件不斷增加而生成新的索引項，父目錄MFT記錄沒有足夠的空間存放時，會按照B+樹的節點分裂規則進行分裂，產生了兩層的B+目錄結構。當文件夾下的文件數量一直增加到一個臨界點，兩層的B+樹目錄不足以存放所有的索引項時，B+樹第二層的一些節點會根據B+樹的分裂規則分離出葉子節點，自身變成非葉子節點，此時變成了三層B+樹結構[5]。

樹的深度對檢索的效率有著極為關鍵的影響，理論上，B+樹的層數越大，檢索文件的所需的遍歷時間將越長，但定量的分析未見文件報道。不同的文件數量下系統中目錄會產生不同的樹結構，從而對對文件的檢索效率產生影響：

第一層B+樹存放的索引項數目為：30

第二層B+樹存放的索引項數目為：900

第三層B+樹存放的索引項數目為：27930

4 實驗及分析（Experiment and analysis）

在第3節中，已討論了讀取效率的影響因素，式（1）中T1與文件系統本身有關，視為定量，為了減少對T2的影響，在實驗中將文件進行連續的寫入以控制T3。因此，通過測量TS，便可間接得到目錄組織結構對T2的影響。

結合氣象水文應用中，常規觀探測報文特點，本文對小文件在計算機中的組織形式對檢索效率的影響進行了實驗。將大量的小文件連續寫入計算機，將其組織在不同的目錄結構中，編程實現了對每個文件的遍歷，遍歷完成后自動記錄時間。

4.1 實驗環境

操作系統：Microsoft Windows Server 2003；計算機系統配置：CPU為Intel（R）、Xeon（R）、1.86GHz，RAM為2.00GB；文件系統：NTFS；實驗分區容量：30GB。

三層B+樹目錄結構可以存放27930個索引項，滿足一個超大文件夾下文件數量的要求。當索引項超過27930時，會產生四層B+樹結構。因此分別設計了文件數為10000和100000的文件檢索實驗，代表了三層與四層B+樹的結構，也覆蓋了一般大目錄應用的條件。

4.2 實驗分析

將1萬個147kB的小文件平均存儲在N個目錄中，并統計其檢索速度，N的值為5、10、20、50、100、200、500、1000。用同樣的方法，我們還研究了10萬個文件時的檢索效率走勢，統計其結果如圖2所示。

圖2 文件檢索效率

Fig.2 File retrieval efficiency

分析實驗數據，發現目錄數在[20，50]之間時，總體檢索時間處于一個最小值的區間，因為B+樹在此區間內目錄結構的查找效率已達到最優，因此要將目錄數控制在此范圍內才能達到最優的檢索效率。

通過算法人為設置最大目錄數，從而改變系統的默認。將目錄改進后與目錄改進前的時間作對比，得到圖3和圖4。

將本文的方法與普通方法對比可得，1萬個文件時，性能提升了20%，10萬個文件時，性能提升了71.3%。

綜上所述，改進后的目錄在文件讀取上的效率有明顯，特別是在文件數目較多時，性能有顯著的提升。

圖3 1萬個文件的檢索時延對比

Fig.3 Delay contrast of 10000 files

圖4 10萬個文件的檢索時延對比

Fig.4 Delay contrast of 100000 files

5 結論（Conclusion）

本文針對大量文件訪問時出現的性能下降問題，對常用的文件系統的存儲方法進行研究，發現不論是集中式存儲還是分布式存儲，最終的讀取效率與本地數據文件的存儲結構有很大關系。在基于文件名檢索的文件系統中，文件數相對于文件大小，對于系統的訪問效率影響更大。因為，其名字空間的管理隨文件數量的變化形成數據結構上的量變到質變，這種變化使得不同操作系統隱含了最佳的目錄數和單個目錄下存放的文件數。據此，以最常用的NTFS文件為對象，通過實驗，定量分析了不同數量目錄和文件的讀取效率和變化趨勢，得出了一種簡單易行的優化方法，有效改善了海量文件存儲訪問的響應時間，特別是存在大量小文件的情形。研究結果對于提高某些應用系統性能，特別是自動文件保存和緩沖，如氣象水文觀探測報文的接收處理和批量數據交換等，有重要的工程指導意義。下一步將結合具體應用案例，將本文提出的優化存儲方法在不同文件系統中進行檢驗，并與分布式環境下的負載均衡和備份服務相結合。

參考文獻（References）

[1] 尤晉元，史美林.Windows操作系統原理[M].北京：機械工業

出版社，2001.

[2] 張春明，芮建武，何婷婷.一種Hadoop小文件存儲和讀取的方

法[J].計算機應用與軟件，2012，29（11）：95-100.

[3] 趙躍龍，等.一種性能優化的小文件存儲訪問策略的研究[J].

計算機研究與發展，2012，49（7）：1579-1586.

[4] Bo Dong，etc.A Novel Approach to Improving the Efficiency

of Storing and Accessing Small Files on Hadoop：a Case Study by

PowerPoint Files. 2010 IEEE International Conference on

Services Computing[R].

[5] 吳偉民，等.NTFS B+樹大目錄結構動態解析[J].計算機工程

與設計，2013，34（4）：1376-1382.

作者簡介：

吳 陽（1989-），男，碩士，學生.研究領域：信息與通信工程.

馮 徑（1952-），女，博士，教授.研究領域：系統集成與應用.endprint

圖1 NTFS的文件定位步驟

Fig.1 NTFS file access process

設文件系統定位時間為T1，與文件系統本身有關；遍歷B+樹時間為T2，與B+樹的結構有關；磁盤的控制及訪問時間為T3，與計算機的硬件性能有關。一個文件的讀取時間為TS，則

TS= T1+ T2+T3 （1）

3.2 讀取效率優化方法

在文件系統與計算機硬件條件固定的情況下，B+樹的結構對文件的存取效率影響至關重要。因此，如何減少公式（1）中T2是提高文件檢索效率的關鍵。

以NTFS為例，目錄中，文件索引放在父目錄的MFT記錄的0X90屬性中。一個文件的MFT記錄大小為1kB，當父目錄下的文件不斷增加而生成新的索引項，父目錄MFT記錄沒有足夠的空間存放時，會按照B+樹的節點分裂規則進行分裂，產生了兩層的B+目錄結構。當文件夾下的文件數量一直增加到一個臨界點，兩層的B+樹目錄不足以存放所有的索引項時，B+樹第二層的一些節點會根據B+樹的分裂規則分離出葉子節點，自身變成非葉子節點，此時變成了三層B+樹結構[5]。

樹的深度對檢索的效率有著極為關鍵的影響，理論上，B+樹的層數越大，檢索文件的所需的遍歷時間將越長，但定量的分析未見文件報道。不同的文件數量下系統中目錄會產生不同的樹結構，從而對對文件的檢索效率產生影響：

第一層B+樹存放的索引項數目為：30

第二層B+樹存放的索引項數目為：900

第三層B+樹存放的索引項數目為：27930

4 實驗及分析（Experiment and analysis）

在第3節中，已討論了讀取效率的影響因素，式（1）中T1與文件系統本身有關，視為定量，為了減少對T2的影響，在實驗中將文件進行連續的寫入以控制T3。因此，通過測量TS，便可間接得到目錄組織結構對T2的影響。

結合氣象水文應用中，常規觀探測報文特點，本文對小文件在計算機中的組織形式對檢索效率的影響進行了實驗。將大量的小文件連續寫入計算機，將其組織在不同的目錄結構中，編程實現了對每個文件的遍歷，遍歷完成后自動記錄時間。

4.1 實驗環境

操作系統：Microsoft Windows Server 2003；計算機系統配置：CPU為Intel（R）、Xeon（R）、1.86GHz，RAM為2.00GB；文件系統：NTFS；實驗分區容量：30GB。

三層B+樹目錄結構可以存放27930個索引項，滿足一個超大文件夾下文件數量的要求。當索引項超過27930時，會產生四層B+樹結構。因此分別設計了文件數為10000和100000的文件檢索實驗，代表了三層與四層B+樹的結構，也覆蓋了一般大目錄應用的條件。

4.2 實驗分析

將1萬個147kB的小文件平均存儲在N個目錄中，并統計其檢索速度，N的值為5、10、20、50、100、200、500、1000。用同樣的方法，我們還研究了10萬個文件時的檢索效率走勢，統計其結果如圖2所示。

圖2 文件檢索效率

Fig.2 File retrieval efficiency

分析實驗數據，發現目錄數在[20，50]之間時，總體檢索時間處于一個最小值的區間，因為B+樹在此區間內目錄結構的查找效率已達到最優，因此要將目錄數控制在此范圍內才能達到最優的檢索效率。

通過算法人為設置最大目錄數，從而改變系統的默認。將目錄改進后與目錄改進前的時間作對比，得到圖3和圖4。

將本文的方法與普通方法對比可得，1萬個文件時，性能提升了20%，10萬個文件時，性能提升了71.3%。

綜上所述，改進后的目錄在文件讀取上的效率有明顯，特別是在文件數目較多時，性能有顯著的提升。

圖3 1萬個文件的檢索時延對比

Fig.3 Delay contrast of 10000 files

圖4 10萬個文件的檢索時延對比

Fig.4 Delay contrast of 100000 files

5 結論（Conclusion）

本文針對大量文件訪問時出現的性能下降問題，對常用的文件系統的存儲方法進行研究，發現不論是集中式存儲還是分布式存儲，最終的讀取效率與本地數據文件的存儲結構有很大關系。在基于文件名檢索的文件系統中，文件數相對于文件大小，對于系統的訪問效率影響更大。因為，其名字空間的管理隨文件數量的變化形成數據結構上的量變到質變，這種變化使得不同操作系統隱含了最佳的目錄數和單個目錄下存放的文件數。據此，以最常用的NTFS文件為對象，通過實驗，定量分析了不同數量目錄和文件的讀取效率和變化趨勢，得出了一種簡單易行的優化方法，有效改善了海量文件存儲訪問的響應時間，特別是存在大量小文件的情形。研究結果對于提高某些應用系統性能，特別是自動文件保存和緩沖，如氣象水文觀探測報文的接收處理和批量數據交換等，有重要的工程指導意義。下一步將結合具體應用案例，將本文提出的優化存儲方法在不同文件系統中進行檢驗，并與分布式環境下的負載均衡和備份服務相結合。

參考文獻（References）

[1] 尤晉元，史美林.Windows操作系統原理[M].北京：機械工業

出版社，2001.

[2] 張春明，芮建武，何婷婷.一種Hadoop小文件存儲和讀取的方

法[J].計算機應用與軟件，2012，29（11）：95-100.

[3] 趙躍龍，等.一種性能優化的小文件存儲訪問策略的研究[J].

計算機研究與發展，2012，49（7）：1579-1586.

[4] Bo Dong，etc.A Novel Approach to Improving the Efficiency

of Storing and Accessing Small Files on Hadoop：a Case Study by

PowerPoint Files. 2010 IEEE International Conference on

Services Computing[R].

[5] 吳偉民，等.NTFS B+樹大目錄結構動態解析[J].計算機工程

與設計，2013，34（4）：1376-1382.

作者簡介：

吳 陽（1989-），男，碩士，學生.研究領域：信息與通信工程.

馮 徑（1952-），女，博士，教授.研究領域：系統集成與應用.endprint