ext4의 "cd" 복잡성

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개의 인덱스 노드를 검사한다는 의미(O(n))

  • 아니면 디렉토리에 검색을 줄일 수 있는 일부 트리 구조(예: 트리 트리, 알파벳순...)가 있어 검사되는 inode 수를 크게 줄일 수 있습니까? 예: n/2 대신 log(n)?

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

명확하게 말하면 문제는 find파일 시스템 트리(예: O(n))에서 파일을 검색하는 것에 관한 것이 아닙니다. 이는 실제로 수천 개의 파일 이름(제품 ID)이 포함된 디렉터리에 대한 경로 확인(FS에서 수행)입니다..

답변1

디렉터리에 대한 해시 트리 인덱싱에 대해 읽을 수 있습니다.여기.

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

관련 정보