爲什麼linux中的stat64（）會隨着目錄中文件數量的增加而變慢？

我爲一個文件夾中的1000個文件運行stat64()並花費少於1秒，但是當同一目錄中有5000個文件時，時間增加到15s。爲什麼linux中的stat64（）會隨着目錄中文件數量的增加而變慢？

爲什麼stat64()非線性變慢？我期待的時間是5s

編輯我正在從FAT文件系統的USB讀取數據。

因爲您正在使用正在掃描每個名稱查找條目列表的玩具文件系統。試試XFS（最好）或ext4或在ext3上啓用「dir_index」。 – Nemo

什麼是您的文件系統類型？ – tristan

@Insane編碼器：您是否在兩種情況下統計了1000個文件，或者您是否統計存在的每個文件？ –

當您在包含N個條目的目錄中調用stat64時，複雜度爲O（N），因爲對於FAT文件系統，系統必須遍歷所有目錄條目，並將每條條目與您所在的條目進行比較尋找。

當您在包含N個條目的文件夾中調用stat64 M時，複雜度爲O（M * N），並且在M = N的情況下，您以O（N * N）結束。看看你的例子：當你有stat64 factor 5文件時，那麼你需要25倍的時間。如果你的1秒時間實際上是0.6秒，那麼結果如預期。

2014-11-14 08:24:58

回答