☰

ext4 上的“cd”复杂性

tag-icon • tag-icon performance ext4 file-search tree
ext4 上的“cd”复杂性

为了存储附件，一个/path/to/atts/目录将创建许多子目录（产品 ID）（从 1 到约 10,000 个，或者将来可能更多），并且在每个子目录中，将创建 1 到约 10 个附件文件。

在/path/to/atts/

  1
  ├── file1.1
  ├── file1.2
  └── file1.3
  2
  └── file2.1
  ...
10000
  ├── file10000.1
  ├── file10000.2
  ├── file10000.3
  ├── file10000.4
  └── file10000.5

（实际上选择 1 .. 10000 是为了更简单的解释 - ID 将是 int32 数字）

我想知道，在 ext4 文件系统上，cd（实际上是路径解析）复杂性是多少，例如/path/to/atts/54321/...：

  • 路径解析是否会一一检查atts目录中的所有索引节点/名称，直到54321到达？意味着平均检查 n/2 个索引节点 (O(n))

  • 或者目录中是否存在一些可以减少搜索的树结构（例如 trie 树、字母顺序......），从而大大减少检查的 inode 数量，例如 log(n) 而不是 n/2？

如果是前者，我将更改产品树结构的实现方式。

需要明确的是：问题不是关于find在文件系统树中搜索文件（即 O(n)）。它实际上是一个路径解析（由 FS 完成），跨越包含数千个文件名（产品 ID）的目录。

答案1

您可以阅读有关用于目录的哈希树索引的信息这里。

目录项的线性数组对性能来说并不是很好，因此 ext3 中添加了一个新功能，以提供更快（但特殊）的平衡树，该树与目录项名称的哈希值无关。

相关内容