선형 리스트
파일 이름과 데이터 블록에 대한 포인터들의 선형 리스트를 만드는 것
프로그램은 쉽지만 실행 시간이 길다.
새 파일이 생성하려면 다음 과정을 거친다.
- 먼저 디렉터리를 탐색, 겹치는 파일 이름이 있는지 확인
- 디렉터리의 끝 부분에 새 항목을 첨가.
특정 파일을 삭제하려면 해당 디렉터리에서 이름을 찾아 그 파일에 할당된 공간을 방출.
이때, 검색 시간을 줄이기 위해 연결 리스트를 사용하기도 한다.
디렉터리 항목을 재사용하기 위해서는 여러가지를 할 수 있음.
- 항목을 미사용으로 표기
- 이름을 모두 공백으로 만들기
- 유효하지 않음 i-node 번호 지정하기
- 항목마다 사용-미사용 비트를 넣어 지정 (디렉터리의 길이를 줄이는 방법)
- 가용 디렉토리 항목 리스트에 추가
단점 : 파일을 찾기 위한 선형탐색 시간
- 디렉터리가 빈번하게 사용되는 만큼, 탐색 시간이 느리면 체감이 쉬움.
- 그래서 캐시를 써서 가장 최근에 쓴 디렉토리 정보를 저장함
- 이를 통해 캐시 속 정보가 매번 보조 저장장치에서 불려오는 것을 방지
- 리스트를 정렬시키면 이진 탐색으로 평균 탐색 시간을 줄일 수 있음
- 단, 정렬하는 것 자체가 더 많은 정보 이동을 야기
- 그래서 처음부터 정렬이 되는 자료구조를 사용할 수도 있음.
해시 테이블
파일 이름을 제시하면 → 해시로부터 값을 얻어 → 그 값으로 리스트에 접근
- 즉, 해시 함수의 결과값 = 포인터.
- 이를 이용해 검색 시간이 개선됨
- 충돌에 대한 보완만 해주면, 삽입과 삭제가 쉬워짐
단점 : 해시 테이블의 고정된 크기
- 해시 테이블의 크기에 따라 해시 기능도 제한을 받음
- 64개의 항목만 가진 해시 테이블이라면, 65번째 파일을 만들 때 새로운 해시 테이블이 필요
- 이때, 기존 디렉터리도 새 해시 값에 맞추어 조직해야 함.
해결책 : 체인 오버플로우 해시 테이블
- 각 해시 항목 = 연결리스트
- 새 항목을 연결리스트에 추가해 충돌을 해결함
- 찾기 작업은 좀 느려져도 여전히 선형 리스트보단 빠름.