리눅스의 파일시스템에서,
ext2 : 디렉터리를 단순 연결 리스트로 관리, 디렉터리내 파일 검색 시간은 O(n), 파일 크기와 비례하여 증가
ext3 : 해쉬를 통해 접근 가능한 HTree 구조 도입, 파일 검색 시간 O(1)
구글링하여 HTree에 대하여 검색해봐도 잘 안나오네요..
어떻게 data를 탐색하는데 상수시간이 걸리는지 Htree 자료구조에 대해 설명해주실분있나요?ㅜㅜ
댓글 6
-
사앙조
2017.05.23 08:58
-
퐈니아
2017.05.27 16:17
http://aiya.ms.mff.cuni.cz/lfs/doc_html/node6.html -
쭈니
2017.06.01 16:09
해쉬 함수를 쓰면 함수 한번만 사용하면 검색이 완료 되기 때문에 O(1) 아닐까요?
-
살작
2017.06.05 12:47
저도 이렇게 생각합니다
-
Rayzin
2017.06.08 20:07
퐈니아 님이 올린 링크의 그림 5.14가 HTree의 도식도 인것 같습니다.
이경우 데이터베이스에서 주로 쓰이는 B+ 트리를 변형한 트리 구조를 가지게 되는데,
접근하고자하는 dentry 블록은 전부 리프 노드에 위치하게되며 탐색할땐 hash값을 이용합니다.
그림 5.15 아래의 Index tree limits 단락을 보면 트리 깊이는 3으로 제한되며, 이 경우 가질수 있는 최대 크기(항목 이름의 길이가 가질수 있는 최대의 길이일 때)의 디렉토리 개수는 993814개라고 나와있는 것 같습니다.
결과적으로 디렉토리의 해쉬값만 알면 트리를 2번 조회하면 해당 dentry 객체를 찾을 수 있으므로, 검색속도가 O(1)인 것 같습니다.
제가 해석을 잘못했을 수도 있으니 영어 잘하시는 분이 한번 검토를 해주셨으면 좋겠습니다 ㅠㅠ
-
김기오
2017.08.16 18:54
말씀하신대로 트리의 깊이가 일정하기때문에 검색속도가 일정하다고 첫 문단에 나와있네요.
HTREE leaves are all on the same level. Therefore the cost of resolving a block where an entry should be located, is the same for all dentries in a directory.
.
http://www.mimul.com/pebble/default/2012/04/17/1334667309783.html
이 링크에 Hash Tree의 개략적인 설명은 있으나 왜 O(1)인지, 자세한 구조나, Source등은 찾기 힘드네요..