Performance
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目錄中的所有 inode / 名稱，直到54321達到？平均檢查 n/2 個 inode 的含義 (O(n))- 或者目錄中是否有一些樹結構可以減少搜尋（例如，trie 樹、字母順序…），這會大大減少檢查的 inode 數量，例如 log(n) 而不是 n/2？
如果是前者，我將更改產品樹結構的實現方式。
需要明確的是：問題不在於
find在文件系統樹中搜尋文件（即 O(n)）。它實際上是一個路徑解析（由 FS 完成），跨越一個包含數千個文件名（產品 ID）的目錄。
您可以在此處閱讀有關用於目錄的雜湊樹索引的資訊。
目錄條目的線性數組不利於性能，因此在 ext3 中添加了一個新功能，以提供更快（但特殊）的平衡樹，以目錄條目名稱的雜湊為鍵。