HTree
HTree |
HTree는 B-트리와 유사한 디렉토리 인덱싱을 위한 특수한 트리 데이터 구조입니다.1레벨 또는 2레벨의 일정한 깊이로 팬아웃계수가 높고 파일명의 해시를 사용하여 [1]밸런싱을 필요로 하지 않습니다.HTree 알고리즘은 여러 리프 블록과 인덱스블록에 걸쳐 오버플로가 발생할 수 있는 해시 콜리전을 처리함으로써 표준 B-트리 메서드와 구별됩니다.HTree 인덱스는 ext3 및 ext4 Linux 파일 시스템에서 사용되며 2.5.[2]40년경 Linux 커널에 통합되었습니다.HTree 인덱스는 Linux ext2 기반 파일 시스템의 확장성을 실질적으로 수천 개의 파일 제한에서 디렉토리당 수천만 개의 파일 범위로 향상시켰습니다.
역사
HTree 인덱스 데이터 구조와 알고리즘은 2000년에 Daniel Phillips에 의해 개발되어 2001년 2월에 ext2 파일 시스템에 구현되었습니다.2002년에 Christopher Li와 Andrew Morton이 2.5 커널 시리즈 중 ext3 파일 시스템에 포트를 설치함으로써 저널 기반의 크래시 일관성이 향상되었습니다.약간의 개선으로 인해 HTree는 Linux 3.x.x 커널 시리즈의 ext4에서 계속 사용됩니다.
사용하다
- ext2 HTree 인덱스는 원래 ext2용으로 개발되었지만 패치는 정식 브랜치에 도달하지 못했습니다.ext2 파일시스템을 작성할 때 dir_index 기능을 이노블로 할 수 있지만 ext2 코드는 이 기능에 영향을 주지 않습니다.
- ext3 HTree 인덱스는 dir_index 기능이 네이블일 때 ext3에서 사용할 수 있습니다.
- ext4 HTree 인덱스는 ext4에서 기본적으로 켜져 있습니다.이 기능은 Linux 커널 2.6.23에 구현되어 있습니다.HTree 인덱스는 파일에 inode에 저장되어 있는 4개 이상의 익스텐트가 필요한 경우 파일 익스텐트에도 사용됩니다.
PTree
PHTree(물리적으로 안정된 HTree)는 [3][unreliable source?]후계자를 위한 파생물이다.쓰기 [citation needed]곱셈을 제외한 HTree의 기존 문제를 모두 해결합니다.Tux3 파일 [4]시스템에서 사용됩니다.
레퍼런스
- ^ Mingming Cao. "Directory indexing" (PDF). Features found in Linux 2.6.
- ^ tytso@mit.edu. "Add ext3 indexed directory (htree) support".
- ^ http://phunq.net/pipermail/tux3/2013-January/000026.html
- ^ "Archived copy". Archived from the original on 2015-01-13. Retrieved 2014-12-28.
{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)
