[데이터베이스] Linear Hashing(선형 해싱)

 

거진 한 학기 동안 데이터 베이스 설계에 대해 배우면서 느끼기에 데이터 베이스의 물리적 설계에서 중요한 것은, 아니 어쩌면 컴퓨팅 성능 전반에 있어서 중요한 것은 시간과 공간을 효율적으로 활용하느냐 인 것 같다.

 

시간에 관하여서는 빠를수록 좋다.

공간은 관하여서는 많은 공간을 쓸 수 있다면, 즉 용량이 클 수록 좋다. 

 

그러나 이 두 가지 모두 '돈'이 고려된다. 더 빠른 연산을 위해 더 좋은 성능의 프로세서를 산다는 것, 더 많은 용량을 갖기 위해 서버를 늘리는 것 모두 돈이 들어간다. 

 

그럼에도 사람들은 언제나 방법을 연구하고 찾아낸다. 더 효율적인 코드, 알고리즘으로 어느 정도의 시간, 공간적 효율성을 증대시킬 수 있다. 

 

해싱도 그러한 중요한 기법 중 하나라 생각된다. 자료 구조 시간에 배웠을 땐 잘 감이 오질 않았는데, 물리적 DB 설계와 블록체인까지 교수님도 위대한 발명(?) 중 하나라 하셨으니 말 다했다.

 

쨌든, 이 선형 해싱이라는 것은 데이터 베이스의 File organization 중 하나이며, 파일 접근 기법(File Access method) 중 하나이기도 하다. 

 

해싱 구조로 파일을 구성해 놓음으로써 우리는 O(1)만에 레코드에 접근할 수 있으며, 이 글에서 설명할 선형 해싱은 동적 해싱 기법 중 하나로 공간을 레코드의 양에 맞게 자동으로 조절되게 하여(scalable) 공간적 효율성을 증대시킨다. 

 

선형 해싱의 장점에 대해 설명하려면 확장 가능 해싱(extendable hashing)과 비교해야 하는데, 짧게 하자면, 확장 가능 해싱은 directory를 이용해 동적으로 bucket을 split하는데, 선형 해싱은 directory 없이 split이 가능하여 공간적으로 더 효율적이라 할 수 있다. 

 

동작 방식은 다음과 같다. 

 

• 우선 초기에 M개의 버킷(bucket)을 가정한다. (0~M-1)
• 초기 해시 함수는 $h_i(k)$ = K mod M 이다.
• record overflow가 발생하면 충돌이 발생한 버킷을 분할(split)한다.

->예를 들어 0번 버킷에서 충돌이 발생하면 0과 M버킷으로 분할한다. 3번 버킷에서 충돌이 발생하면 3과 M+3으로 분할한다. 이렇게 분할된 버킷은 서로 $h_{i+1}(k)$ = K mod 2M 해시 함수로 구분될 수 있다. 

 

• n은 분할이 실시되면 1을 더한다. 
• 해시 값이 n보다 작은 경우, $h_i(k)$ < n는 이미 분할이 된 버킷들이므로 $h_{i+1}(k)$를 적용시켜 준다. 
• n=M이 되면, 초기의 M개의 버킷(0~M-1)은 모두 분할이 된 것이므로 모든 버킷에 $h_{i+1}(k)$이 적용될 것이다. 
• j번 분할한다면 해시함수는 다음과 같다. $h_{i+ㅓ}(k)$ = K mod $2^{j} M$

알고리즘 (pseudo code)

 

n = 0;

if n = 0; 

   then m <- $h_j(K)$;

else begin:

    m <- $h_j(K)$;

    if m < n then m <- $h_{j+1}(K)$;

    end;

 

 

 

초기에 다음과 같이 M개의 버킷이 있다고 하자. (각 버킷에는 하나의 레코드만 들어갈 수 있다 가정. bfr = 1)

 

 

각 버킷에는 다음과 같이 데이터가 들어올 수 있다. 

 

 

0번 인덱스의 경우 M 역시 해싱값이 0이기에 0번 버킷에 들어가게 되는데 이때 overflow가 발생하게 된다. 그 결과 0번 버킷을 새 해싱함수(k mod 2M)를 써 버킷을 분할한다. 

 

 

이 새 해싱함수에 따라 M은 M번 버킷으로 0은 0번 버킷으로 split된다. 이후 n을 1 증가시켜 준다. 

현재는 0번 버킷만 K mod 2M 해싱이 적용되고, 나머지 버킷(1~M-1)은 K mod M 해싱이 적용된다. 

 

 

초기 M개의 버킷이 모두 해싱이 되고 난 후 (해싱은 uniform distribution을 갖기에 확률이 모두 동등하여 한 버킷에서만 계속 overflow가 일어나진 않을 것이다.) 다음과 같이 overflow가 발생하게 되는 상황에서는 위의 방식과 마찬가지로 진행하되, 해싱 함수는 K mod 4M으로 하여 0번 버킷을 분할한다. 

 

분할된 결과는 다음과 같다.