当您在包含大量文件的目录中搜索文件时 ( n)，找到此文件的最坏情况运行时间是多少？我的意思是操作系统 (linux) 是否按顺序检查目录中的所有文件名以找到匹配项 ( O(n)) 还是它支持一种更智能的字典索引？
答案1
这是答案的开始。每个文件都有一个与之关联的 inode 对象。inode 是文件系统特定的，这就是为什么您通常不能拥有跨文件系统的硬链接。内核维护一个 inode 缓存，每当操作系统必须打开/引用不在缓存中的文件时，该缓存可能会更新。在第一次访问后，通过“索引”或哈希访问 inode 编号。
因此，一个简单的ls命令就可以读取所有目录条目以获取文件 - 线性时间 - 或者它可以使用 inode 缓存。我相信 McKusick 的 BSD ffs 实现是第一个使用这种缓存的实现。
较新的文件系统在处理大型目录时表现更好，但是一旦项目数量变得非常大（如数百万），ls响应时间可能会大幅下降。这是因为缓存大小限制。或者因为文件未缓存。ufs（ffs 的较新版本）就是这样。在我看来，ext4（Linux）要好得多。大多数操作系统都会维护查找效率的统计数据 - 尝试使用您的 iostat 版本。这是文件系统调整的一部分，即调整 inode 缓存的大小。
所以，归根结底，没有一个答案适合所有情况。而且通常有缓存。但它保持 LRU，因为大多数内核都有 inode 缓存大小限制，因此每月使用一次的 inode 可能会被移出缓存。