개요
HTree는 디렉토리 구조 indexing에 특화된 자료구조이다. HTree는 ext3, ext4에 사용되고 있으며, 디렉토리를 해쉬를 이용하여 변형된 BTree를 사용하여 저장한다. HTree의 BTree depth는 3이하가 되도록 유지되며, BTree는 구조상 말단의 노드들이 모두 서로 연결된 형태를 취하고 있다. 따라서 Hash를 통해서 말단의 데이터가 저장된 블럭을 탐색하여 검색하면 기존의 Linear Searching 방법에 비해서 상수시간 O(1)만에 디렉토리 검색을 완료할 수 있다.
트리의 깊이가 3일때 가질수 있는 최대 디렉토리 개수는 993814개이다. 트리의 개수가 일정하기 때문에, Hash를 통해서 트리를 탐색하는 것도 트리의 깊이와 일치한다. 이때 트리의 깊이는 항상 3이하임으로, HTree의 검색은 상수시간안에 처리할 수 있다.
구조
- DX-block (Directory indices block): 블럭 아이디와 해쉬값의 쌍을 저장한다.
- DE-block (Directory entries block): 디렉토리 엔트리를 저장한다.
HTree는 다음과 같은 Operation을 지원한다.
- Lookup: Hash를 이용하여 O(1)에 디렉토리 엔트리를 검색한다.
- Insert name entry: name entry를 집어 넣는다.
- Delete name entry: name entry를 삭제 한다.
- Split DE-block: DE block에 entry로 가득차면 DE block을 쪼갠다.
- Split DX-block: Dx block이 DE block으로 가득차면 block을 쪼갠다.
- Grow htree: DE block이 어느 수준이상으로 길어지면 De Block에 추가적인 레이어를 더한다. 레이어의 깊이는 3이하여야 한다. (평균)
- Hash Collision: Hash 충돌이 발생하면 Linear search로 entry를 찾아낸다.