☰

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 中添加了一個新功能，以提供更快（但特殊）的平衡樹，該樹與目錄項名稱的哈希值無關。

相關內容