从Linux文件系统读取文件的时间复杂度是多少？

Question

假设我的100.000文件系统中有很多目录(比方说),并且每个目录中都有相似数量的目录.每个目录可以包含任意数量的文件,但通常不会超过几个.该结构变为恒定深度(10).

我的问题是,如果我从这个目录结构中读取一个文件,那么时间复杂度(在读取操作中)是否存在差异:/dir-34/dir-215/dir-345/file1使用Paths.get() 与从这样的简单文件系统读取文件相比:

/dir1
  /dir2
  /dir3
    file1
  /dir4
    file2

注意:这只是一个理论问题我只想知道我尝试打开文件的目录中的目录/文件数是否对读取操作的速度有任何影响.

Answer 1

如果/path/to/file可用，（注意：性能和时间复杂度仍然很大程度上取决于磁盘结构和底层文件系统实现。例如 btrfs，一切都是 b 树，ext4 和 XFS 使用 H 树）

因此，遍历目录结构直到叶节点（包含文件的目录），平均情况时间复杂度应为 O(logN)，而最坏情况为 O(N)，N = 树中的目录数。最坏的情况是，您在 N-1 下创建了第 N 个目录，在 N-2 中创建了第 N-1 个目录，依此类推……直到根目录，形成树中的单个分支。理想情况下，如果您有完整路径，则不必从根目录遍历树中的所有目录。

然后，如果您的底层 FS 支持目录索引和散列，则每次查找都需要另一个 O(1) 来查找目录中的文件。因此，O(logN) + O(1)，即忽略低阶项，它应该仅为 O(logN)，其中 N 是级别。