添付ファイルを保存するために、/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までディレクトリ内のすべての inode / 名前を 1 つずつチェックしますか? つまり、平均 n/2 個の inode がチェックされます (O(n))54321または、検索を減らすディレクトリ内のツリー構造 (トライツリー、アルファベット順など) があり、n/2 ではなく log(n) のように、チェックされる inode の数を大幅に減らすことができますか?
前者の場合は、製品ツリー構造の実装方法を変更します。
明確にしておくと、質問はfindファイルシステムツリー内のファイルの検索に関するものではありません（これは O(n) です）。これは実際には、何千ものファイル名（製品 ID）が存在するディレクトリを横断するパス解決（FS によって実行されます）です。。
答え1
ディレクトリに使用されるハッシュツリーインデックスについて読むことができますここ。
ディレクトリ エントリの線形配列はパフォーマンスにあまり良くないので、ディレクトリ エントリ名のハッシュをキーとする、より高速な (ただし特殊な) バランス ツリーを提供する新しい機能が ext3 に追加されました。