c - 为什么 linux 中的 stat64() 会随着目录中文件数量的增加而变慢？

Question

我stat64()在一个文件夹中运行了 1000 个文件，耗时不到 1 秒，但是当同一目录中有 5000 个文件时，时间增加到15s.

为什么stat64 ()非线性变慢？我期待的时间是5s

编辑 我正在使用 FAT 文件系统从 USB 读取数据。

Answer 1

当您stat64在包含 N 个条目的目录中调用文件时，复杂度为 O(N)，因为对于 FAT 文件系统，系统必须遍历所有目录条目并将每个条目与您要查找的条目进行比较。

当您stat64在包含 N 个条目的文件夹中调用 M 次时，复杂度为 O(M*N)，在 M=N 的情况下，您最终得到 O(N*N)。

看看你的例子：当你有stat645 个文件时，你需要 25 个时间。如果您的 1s 时间实际上是 0.6 秒，那么结果符合预期。