[Database] dynamic hashing의 종류와 방법

이전 포스팅에서 정적으로 크기를 정해놓고 하는 static hashing에 대해서 배웠다.

 

이제 동적으로 파일 확장이 가능한 dynamic hashing에 대해서 공부해보려 한다.

 

dynamic hashing은 기본적으로 2진수를 사용한다.

 

키를 2진수로 바꾸고 그 2진수를 사용하는 것이다.

 

크게 3가지 방법이 존재한다.

 

1. 확장성 해싱(extendible hashing)

 

확장성 해싱에서는 디렉토리라는 것을 사용한다.

 

디렉토리란 버킷 주소의 배열이다.

 

global depth라는 것이 존재하는데 이는 d라고 표현한다.

 

이것은 해시 값의 첫 d개의 비트를 디렉토리의 인덱스로 사용하겠다는 뜻이다.

 

그것은 곧 디렉토리의 배열의 최대 길이는 2의 d제곱 이라는 뜻이다.

 

global depth d를 3이라 가정하자.

 

예를 들어 101000, 101001, 110000, 110001이라는 해시 값이 존재할 수 있다.

 

여기서 해시 값들의 앞 3글자가 101인 해시 값이 2개, 앞 3글자가 110인 해시 값이 2개 존재한다.

 

그림으로 본다면 다음과 같다.

이렇게 디렉토리를 이욯하여 버킷들의 주소를 나타내는 것이다.

 

그림을 보면 local depth라는 것이 존재하는데 local depth의 경우 아래 그림을 보는 것이 이해가 빠르다.

 

다음과 같은 디렉토리, 버킷이 있다고 하자.

여기서 110, 111로 시작하는 버킷의 local depth를 2로 바꾼다면 둘 다 앞 두 비트가 11로 동일하다.

 

그러므로 아래와 같이 합쳐지는 것이다.

위 아래 그림을 잘 비교해보면 local depth의 의미를 바로 알게 될 것이다.

 

그리고 보다시피 local depth는 global depth보다 커질 수는 없다. 반드시 작거나 같아야 한다.

 

global depth의 길이를 늘리거나 줄여서 디렉토리 배열의 길이를 늘리거나 줄일 수 있다.

 

늘리는 것은 doubling, 줄이는 것을 halving

 

확장성 해싱의 장점

1. 파일이 커져도 성능 저하가 크지 않다.
2. 공간을 미리 할당할 필요가 없다.
3. 파일을 아예 재구성하는 것보다 부담이 적다.

 

확장성 해싱의 단점

1. 디렉토리 한 번, 버킷 한 번 총 두 번 접근해야 한다.

---

2. 동적 해싱 (dynamic hashing)

이 방법은 1번과 비슷한데 디렉토리를 트리 구조로 유지하는 것이 특징이다.

 

디렉토리의 구조는 아래와 같다.

 

 

---

3. 선형 해싱 (linear hashing)

해시 함수를 m으로 나눈 나머지 값이라고 하고 버킷의 크기를 2라고 하자.

 

만약 오버플로가 발생한다면 m의 값을 두 배씩 늘리는 방식이다.

 

아래 그림으로 이해하는 편이 좋다.

현재 버킷이 꽉 찬 상태이다. 여기서 300이 들어오려 한다면 m을 2배 곱한다.

 

그렇게 되면 100은 200으로 나눈 나머지가 100이되고 200은 200으로 나눈 나머지가 0이 되므로 아래와 같이 분할된다.