如何在Java中快速检索目录列表？

Question

假设有一个非常简单的程序，列出给定目录下所有子目录。听起来很简单吧？但在Java中列出所有子目录的唯一方法是使用FilenameFilter结合File.list()。

这对于简单情况可以工作，但当文件夹有大约150,000个文件和2个子文件夹时，等待45秒迭代所有文件并测试file.isDirectory()是愚蠢的。是否有更好的方法来列出子目录呢？

---

附注：抱歉，请不要讲授关于在同一目录中拥有太多文件的问题。这是我们实际环境的一部分要求。

- erotsppa

---

我会尽量避免陷入那种情况。目录中有大量文件很可能会导致许多文件系统操作变慢。 - Jon Skeet

NIO2（Java7）将使用延迟迭代器来列出目录，以解决这个问题。 - dfa

@Hardwareguy 不，这是懒加载。你不需要等待45秒才能访问第一个条目... - dfa

@Hardwareguy，你不会浪费150,000个数组元素，但在情况最坏的情况下，你需要做同样数量的工作。 - dfa

@erotsppa - 有没有任何答案是有帮助的？接受其中一个最有帮助的答案被认为是良好的形式。 - DVK

Answer 1

正如已经提到的，这基本上是一个硬件问题。磁盘访问总是很慢，而且大多数文件系统实际上并不设计用于处理拥有那么多文件的目录。

如果由于某种原因必须将所有文件存储在同一目录中，我认为你将必须维护自己的缓存。这可以使用本地数据库（如sqlite、HeidiSQL或HSQL）来完成。如果您想获得极高的性能，请使用一个java TreeSet并将其缓存在内存中。这意味着至少您将不需要经常读取目录，并且可能可以在后台完成。您可以通过使用操作系统本机文件更新通知API（Linux上的inotify）订阅目录更改来进一步减少刷新列表的需求。

这似乎对你来说不可能，但我曾通过将文件“哈希”到子目录中来解决类似的问题。在我的情况下，挑战是存储数百万张具有数字ID的图像。我构建了以下目录结构：

images/[id - (id % 1000000)]/[id - (id % 1000)]/[id].jpg

这对我们很有效，我会推荐这种解决方法。你可以通过仅取文件名的前两个字母，然后是接下来的两个字母，来实现与字母数字文件名类似的功能。我曾经也这样做过一次，效果也很好。

- Emil H

---

我会选择维护某种索引（内存/数据库），而不是每次想要列出文件时都进行I/O。 - Ryan Fernandes

Answer 2

你知道可能的子目录名称有限吗？如果是这样，请使用循环遍历所有可能的名称，并检查目录是否存在。

否则，在大多数底层操作系统中，您无法仅获取目录名称（例如，在Unix中，目录列表只是读取“目录”文件的内容，因此没有快速找到“仅目录”的方法，而不列出所有文件）。

然而，在Java7的NIO.2中（参见http://java.sun.com/developer/technicalArticles/javase/nio/#3），有一种方法可以获得流式目录列表，因此您不会得到完整的文件元素数组，从而减少了内存/网络的混乱。

- DVK

---

即使使用1.7版本，您仍然需要遍历整个流以查看是否获取了所有子目录，因此这只是一个微小的内存优化而已。 - Hardwareguy

我假设（由于缺乏精确的文档），流式处理将避免在内存中保留已经迭代过的内容。 - DVK

使用nio流可以提高性能，请参考以下答案和示例：https://dev59.com/slwZ5IYBdhLWcg3wNOGI - Luke

Answer 3

实际上，你得到这些讲座的原因是它们是解决你问题的正确答案。以下是背景，也许你可以在生产环境中做出一些改变。

首先：目录存储在文件系统中；把它们看作文件，因为它们确实是文件。当你遍历目录时，你必须从磁盘读取这些块。每个目录条目都需要足够的空间来保存文件名、权限以及该文件在磁盘上的位置信息。

其次：目录没有任何内部排序（至少在我使用过的文件系统中是这样）。如果你有150,000个条目和2个子目录，那么这两个子目录引用可能在这150,000个目录中的任何位置。你必须进行迭代才能找到它们，这是无法避免的。

所以，假设你无法避免大目录。你唯一的选择是尝试将组成目录文件的块保留在内存缓存中，这样每次访问它们时就不会命中磁盘。你可以通过定期在后台线程中迭代目录来实现这一点，但这将对你的磁盘造成不必要的负载，并干扰其他进程。或者，你可以扫描一次并跟踪结果。

另一种选择是创建分层目录结构。如果你看一下商业网站，你会看到像/1/150/15023.html这样的URL——这意味着每个目录中的文件数量很少。把它看作数据库中的BTree索引。

当然，你可以隐藏那个结构：你可以创建一个文件系统抽象层，它接收文件名并自动生成包含这些文件名的目录树。

- kdgregory

---

我被踩是因为我给了一个无效的答案（如果是的话，请纠正我），还是因为我给了一个你不喜欢的答案？ - kdgregory

我并没有给你的帖子点踩，但是你在没有任何参考资料的情况下对文件系统的内部工作原理提出了许多观点，而且还不知道实际使用的是哪种文件系统。这使我对你的帖子正确性有些怀疑，尽管我很愿意被证明是错误的。 - Emil H

@emil - 所有目录结构都具有相似的特征：它们维护文件列表。一些操作系统可能具有特殊的“检索所有子目录”系统调用；我从未在Unix或Windows中看到过这样的调用，但是两个系统的系统调用已经发展到了我甚至无法跟踪的地步。正如我在评论中指出的那样，我更喜欢一个真实的例子，而不是匿名的负评。无论如何，它并没有通过Java API公开。 - kdgregory

关于引用，这里有一个关于EXT2的引用，它（与其兄弟EXT3一起）是Linux上更常见的文件系统之一：http://www.nongnu.org/ext2-doc/ext2.html#DIRECTORY -- 这是谷歌的顶部结果，但我无法证明作者的资质。就个人而言，自从Linux SVR3以来，我就没有处理过目录数据。 - kdgregory

我认为尽管没有回答特定的问题，但这仍然是有用的。它退后一步并提供了一些关于为什么目录查询很慢以及一些解决方案的背景信息。有时候，回答一个问题的方法就是询问您是否在问“正确”的问题（如果这听起来有点“元”，请原谅）。 - Brian Agnew

Answer 4

当我在调试一个遍历大量文件的Java应用程序时，我遇到了类似的问题。它使用了一种旧的方法。

for (File f : new File("C:\\").listFiles()) {
    if (f.isDirectory()) {
        continue;
    }        
}

看起来每个 f.isDirectory() 都是对本地文件系统的调用，而至少在 NTFS 上，这种调用非常缓慢。Java7 NIO 有额外的API，但并不是所有方法都很好用。我将在此提供 JMH 基准测试结果。

Benchmark                  Mode  Cnt  Score    Error  Units
MyBenchmark.dir_listFiles  avgt    5  0.437 ?  0.064   s/op
MyBenchmark.path_find      avgt    5  0.046 ?  0.001   s/op
MyBenchmark.path_walkTree  avgt    5  1.702 ?  0.047   s/op

这段代码的执行结果是数字:

java -jar target/benchmarks.jar -bm avgt -f 1 -wi 5 -i 5 -t 1

static final String testDir = "C:/Sdk/Ide/NetBeans/src/dev/src/";
static final int nCycles = 50;

public static class Counter {
    int countOfFiles;
    int countOfFolders;
}

@Benchmark
public List<File> dir_listFiles() {
    List<File> files = new ArrayList<>(1000);

    for( int i = 0; i < nCycles; i++ ) {
        File dir = new File(testDir);

        files.clear();
        for (File f : dir.listFiles()) {
            if (f.isDirectory()) {
                continue;
            }
            files.add(f);
        }
    }
    return files;
}

@Benchmark
public List<Path> path_walkTree() throws Exception {
    final List<Path> files = new ArrayList<>(1000);

    for( int i = 0; i < nCycles; i++ ) {
        Path dir = Paths.get(testDir);

        files.clear();
        Files.walkFileTree(dir, new SimpleFileVisitor<Path> () {
            @Override
            public FileVisitResult visitFile(Path path, BasicFileAttributes arg1) throws IOException {
                files.add(path);
                return FileVisitResult.CONTINUE;
            }

            @Override
            public FileVisitResult preVisitDirectory(Path path, BasicFileAttributes arg1) 
                    throws IOException {
                return path == dir ? FileVisitResult.CONTINUE : FileVisitResult.SKIP_SUBTREE;
            }
        });
    }

    return files;
}

@Benchmark
public List<Path> path_find() throws Exception {
    final List<Path> files = new ArrayList<>(1000);

    for( int i = 0; i < nCycles; i++ ) {
        Path dir = Paths.get(testDir);

        files.clear();
        files.addAll(Files.find(dir, 1, (path, attrs) 
                -> true /*!attrs.isDirectory()*/).collect(Collectors.toList()));
    }

    return files;
}

- Xtra Coder

Answer 5

关键问题可能是在循环中调用了 File.isDirectory() 函数。

File.isDirectory() 可能非常缓慢。我曾经看到 NFS 处理 200 个文件目录需要 10 秒的时间。

如果你能尽可能避免调用 File.isDirectory() 函数（例如测试扩展名，没有扩展名 == 目录），你可以极大地提高性能。

否则，我建议使用 JNA/JNI/编写本地脚本来完成此操作。 jCifs 库使您更有效地操作 Windows 网络共享。我不知道是否有一个库可以为其他网络文件系统做到这一点。

- Roman Zenka

---

目录可以有扩展名，文件可以省略扩展名。因此，你的答案不完整。 - BalusC

@BalusC 是的。但有时您可以控制命名 - 例如，您知道文件是具有给定集合的扩展名的图像，并且目录总是不带点生成的。如果是这种情况，您可以大大加快速度。 - Roman Zenka

Answer 6

如果这150k个文件（或其中大部分）都有类似的命名约定，那么您可以进行黑客攻击。

*.jpg
*Out.txt

只为那些你不确定是否是文件夹的对象实际创建文件对象。

- Hardwareguy

---

这会有帮助吗？与其在 FilenameFilter 中为每个文件测试 isDirectory()，我应该测试 isNameSimilarTo("*.jpg") 吗？ - erotsppa

您将进行一些字符串操作，虽然不快，但应该比创建150k个文件对象并调用.isdirectory要快。您需要进行一些计时以确定真正的减速在哪里。 - Hardwareguy

这实际上改善了我的性能，从10秒降至1秒。在我的情况下，我有1000个文件和10个目录，存储在网络驱动器上。使用FilenameFilter并跳过所有以“.jpg”结尾的文件的“new File().isDirectory”就解决了问题！ - Thomas Jacob

Answer 7

我不确定使用 cmd.exe 是否会增加额外负担，但是可以有以下一种可能的方式：

...
Runtime r = Runtime.getRuntime();
Process p = r.exec("cmd.exe /k dir /s/b/ad C:\\folder");
BufferedReader br = new BufferedReader(new InputStreamReader(p.getInputStream()));
for (;;) {
    String d = br.readLine();
    if (d == null)
        break;
    System.out.println(d);
}
...

• /s 表示搜索子目录
• /ad 表示只返回目录
• /b 表示从根目录返回完整路径名

- lavinio

---

你甚至可以保持一个 cmd.exe 进程处于活动状态，并针对想要搜索的每个目录将命令传输到该进程。 - finnw

Answer 8

如果你的操作系统比较“稳定”，可以试试JNA：

• UNIX上使用opendir/readdir
• Windows上使用FindFirstFile 及相关API
• Java7带有NIO2

这些都是“流式API”。在开始搜索之前，它们不会强制你分配一个150k的列表/数组。在我看来，在您的情况下，这是一个很大的优势。

- dfa

Answer 9

这是一个不太寻常的解决方案，完全没有经过任何测试。它还依赖于支持符号链接的文件系统。这不是一个Java解决方案。我怀疑你的问题与文件系统/操作系统有关，而不是与Java有关。

是否可能创建一个平行的目录结构，其中子目录基于文件名的首字母，然后通过符号链接到实际文件？下面是一个示例：

/symlinks/a/b/cde

将链接到

/realfiles/abcde

（其中/realfiles是您的150,000个文件所在的位置）

您需要创建和维护此目录结构，我没有足够的信息来确定是否实用。但是上述操作将为您的非分层（且较慢）目录创建一个快速索引。

- Brian Agnew

Answer 10

还有一个递归并行扫描 http://blogs.oracle.com/adventures/entry/fast_directory_scanning。基本上兄弟节点是并行处理的。还进行了鼓舞人心的性能测试。

- dfa