面向高效文件访问的目录结构优化研究

吴阳++冯径

摘 要：针对气象水文应用中，大量常规观探测报文批量访问出现的低效问题，研究文件存储特性，定量分析了目录级数和文件数量对访问性能的影响，发现文件数相对于文件大小，对于系统的访问效率影响更大，当单个目录下文件数目过大时，文件存取延时较大，严重影响用户体验与服务性能。根据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