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

Question

我为一个文件夹中的 1000 个文件运行 stat64()，用时不到 1 秒，但当同一目录中有 5000 个文件时，时间增加到 15s。

为什么 stat64 () 非线性地变慢？我原以为时间是5秒

编辑 我正在从带有 FAT 文件系统的 USB 读取数据。

Answer 1

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

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

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