c - 为什么 linux 中的 readdir() 调用呈非线性增长

Question

我有一个包含 1000 个文件的目录，readdir() 用时不到 1 秒，但是 10000 个文件用了大约 24 秒。

为什么？它应该是线性的。

谁能解释一下原因。 如果我只需要获取目录中的文件和子目录名称，是否有更好的解决方案？

编辑 我在我本地的 Linux 电脑上。

Answer 1

它可能是特定于文件系统的。也许使用适当配置的 Ext4或 BTRFS文件系统应该有帮助。一些文件系统使用散列或 B 树技术使大小为 N 的目录中的文件访问复杂度为 O(log N)，其他文件系统仍然是线性的，例如O(N)，内核可能会在上面做一些奇怪的事情。

您可能在大型目录中使用的 shell 通常会在 globbing 时对条目进行排序(另请参见 glob(7))。你不想要它的 auto-completion每次击键持续数秒!

我相信你不应该永远拥有巨大的目录(例如超过几百个条目)，所以一个目录中有 10000 个文件是不合理的。如果是这种情况，您最好以不同的方式组织文件，例如subdir01/file001.txt ... sbudir99/file999.txt

顺便说一句，如果您需要通过一些文本键访问很多小东西，请使用索引文件(如 gdbm )或 Sqlite “数据库”，或一个真实的数据库( PostGreSQL ， MongoDb ...)更合适，而且可能更有效。不要忘记转储数据(可能是某种文本格式)以进行备份。

请注意 readdir(3) 的文档在 Linux 和 POSIX 上 readdir不要提及任何时间复杂度或任何线性行为。这种未提及的情况很重要。 关于常用FAT文件系统(例如在许多 USB key 上)时间复杂度可能是二次方的。