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番号です。）

cdext4ファイルシステムでは、次のような複雑さ（実際にパスを確認する）が何であるか疑問に思います/path/to/atts/54321/...。

• パスチェックは、ディレクトリに到達するattsまでディレクトリ内のすべてのinode / nameを1つずつ確認しますか？54321平均的にn/2個のインデックスノードを調べるという意味(O(n))

• それとも、ディレクトリに検索を減らすことができるいくつかのツリー構造（ツリーツリー、アルファベット順など）があるため、検査されるinodeの数を大幅に減らすことができますか？例: n/2 の代わりに log(n)?

前者の場合は、製品ツリー構造の実装方法を変更します。

明確に言えば、問題はfindファイルシステムツリー（たとえばO（n））からファイルを検索することではありません。これは、実際には何千ものファイル名（製品ID）を含むディレクトリへのパス解決（FSで実行）です。。