☰

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 숫자입니다.)

cdext4 파일 시스템에서 예를 들어 도달할 때 (실제로 경로 확인) 복잡성 은 무엇인지 궁금합니다 /path/to/atts/54321/....

  • 경로 확인은 도달할 atts때까지 디렉토리 에서 모든 inode/이름을 하나씩 확인합니까 ? 54321평균적으로 n/2개의 inode가 검사된다는 의미입니다(O(n)).

  • 아니면 n/2 대신 log(n)과 같이 검색을 줄이는 일부 트리 구조(예: 트리 트리, 알파벳 순서...)가 디렉터리 내에 검사된 inode 수를 극적으로 줄여주나요?

전자라면 제품 트리 구조가 구현되는 방식을 변경하겠습니다.

분명히 말하면 문제는 find파일 시스템 트리(O(n))에서 파일을 검색하는 것에 관한 것이 아닙니다. 이는 실제로 수천 개의 파일 이름(제품 ID)이 있는 디렉터리를 통과하는 경로 확인(FS에 의해 수행됨)입니다..

답변1

디렉터리에 사용되는 해시 트리 인덱스에 대해 읽을 수 있습니다.여기.

디렉토리 항목의 선형 배열은 성능에 좋지 않습니다. 따라서 디렉토리 항목 이름의 해시를 기반으로 하는 더 빠른(그러나 특이한) 균형 트리를 제공하기 위해 새로운 기능이 ext3에 추가되었습니다.

관련 정보