확장성 해싱

Extendible Hashing; 확장 해싱

데이터가 늘어나면 디렉토리와 버킷을 필요한 만큼만 늘려 가는 동적 해싱 기법

• 정적 해싱은 버킷 수를 미리 정해 두므로 데이터가 늘면 오버플로가 쌓이고 줄면 공간이 남는다.
• 확장성 해싱에서는 데이터 파일의 크기에 따라 해싱 구조 자체가 변한다.
• 해시값의 앞쪽 d비트로 디렉토리를 찾고, 디렉토리 항목이 실제 버킷을 가리킨다.

구조

• 전역 깊이(global depth, d) : 디렉토리가 사용하는 비트 수. 디렉토리 항목 수는 2^d
• 지역 깊이(local depth, d') : 각 버킷이 실제로 구분에 사용하는 비트 수
• 언제나 d' ≤ d 다. 지역 깊이가 전역 깊이보다 작으면 여러 디렉토리 항목이 같은 버킷을 함께 가리킨다.

버킷 분할

• 버킷이 가득 차면 그 버킷 하나만 둘로 나누고 안에 있던 레코드를 두 버킷에 재배치한다.
  • d' < d 인 경우 : 디렉토리는 그대로 두고 버킷만 나눈 뒤 그 버킷의 d'를 1 늘린다.
  • d' = d 인 경우 : 디렉토리를 두 배로 늘려 d를 1 늘린 뒤 버킷을 나눈다.
• 파일 전체를 다시 만드는 것이 아니라 한 번에 한 버킷만 재구성하므로 재구성 부담이 작다.

특징

• 레코드 하나를 찾는 데 디스크 접근이 디렉토리 1회 + 버킷 1회로 끝난다.
• 오버플로 버킷을 길게 매달지 않아도 된다.
• 디렉토리가 두 배씩 커지므로 데이터가 한쪽으로 치우치면 디렉토리 공간이 낭비된다.
• 디렉토리를 두지 않고 버킷을 순서대로 하나씩 늘리는 선형 해싱(Linear Hashing)도 동적 해싱에 속한다.

같이 보기

• 해시