디렉토리의 파일 수가 늘어남에 따라 linux의 stat64()가 느려지는 이유는 무엇입니까?

Question

폴더의 1000 개 파일에 대해 stat64()을 실행하고 1 초 미만의 시간이 걸렸지 만 동일한 디렉토리에 5000 개가있는 경우 시간은 15s으로 증가했습니다.

stat64()이 비선형 적으로 느린 이유는 무엇입니까? 나는 5 초가 될 것으로 예상했다.

EDIT 나는 FAT 파일 시스템으로 USB에서 데이터를 읽는다.

Answer 1

N 항목이 들어있는 디렉토리의 파일에 stat64을 호출하면 FAT 파일 시스템에서 시스템이 모든 디렉토리 항목을 검토하고 각각을 비교해야하기 때문에 복잡성은 O (N)입니다. 찾고.

N 항목이 들어있는 폴더에서 stat64 번을 M 번 호출하면 복잡성은 O (M * N)이고 M = N이면 O (N * N)이됩니다.

예제를 보면 : stat64 요소가 5 개일 때, 요인 25가 필요합니다. 사실 1 초의 시간이 0.6 초라면 예상대로 결과가 나옵니다.