DB - hashing

Dynamic hashing

• Good for a database that grows and shrinks in size
• Allows the hash function to be modified dynamically
• Extendable hashing - one form of dynamic hashing

Example

다음과 같은 search-key를 따르는 레코드에 대한 파일이 있을 때 주어진 hash function h(x)를 통해 반환된 extendable hash structure가 아래와 같이 주어져 있다. (20점)

• (h(x) : x를 8로 나누었을 때의 나머지를 이진법으로 반환)
• (h(x) : Returns the remainder of x divided by 8 in binary number)
• (bucket_size = 3)

이때 A, B, C, D, E, F, G에 해당하는 search-key value를 각각 구하시요.

문제에서 고려해야할 사항은 x를 8로 나누었을 때의 나머지를 이진법으로 반환하는 것입니다. 그리고 버킷-사이즈는 3으로 초기화 되어있습니다. 처음에 2를 먼저 삽입하겠습니다.

2 % 8 = 2이고, 이를 이진법으로 나타내면 010입니다. 처음 버킷에는 empty-bucket이므로 그냥 insertion하면 됩니다. 혹시나 2진수와 10진수 변환하기는 다음 블로그를 참고하시면 됩니다. https://coming1007.tistory.com/205

2진수 <-> 10진수 <-> 2진수 변환하기

이제 3을 삽입하겠습니다. 3 % 8 = 3이고 이를 2진수로 변환하면 011입니다. 여전히 Bucket[0]은 Full이 아니기 때문에 똑같이 삽입하면 됩니다.

또 5를 삽입하겠습니다. 5 % 8 = 5이고 이를 이진수로 변환하면 101입니다. 버킷은 현재 2개의 데이터만 있기때문에 마찬가지로 삽입해주면 됩니다. 

이제 7을 삽입하겠습니다. 7 % 8 = 7이고 이를 2진수로 변환하면 111입니다. bucket[0]에 삽입하려고 pointer를 따라가봤더니 bucket이 full 상태이므로 overflow가 발생하여 split을 해주어야합니다. 이때, 버킷을 가리키는 pointer가 하나밖에 없기 때문에 아래와 같이 Hash prefix를 1개~2개로 split 즉, 2배 해줍니다. 그리고 i값을 1 증가시켜 i = 1이됩니다. 그리고 새롭게 생긴 pointer는 기존의 버킷을 따라 가리키게 됩니다.

이런 상태에서 이제 7이라는 값을 insert를 해야하는데 버킷의 개수는 늘어나지 않았기 때문에 여전히 overflow가 발생하게 됩니다.

그림과 같이 한개의 버킷을 두 개의 버킷으로 split 하여 overflow를 해결하였습니다. pointer도 절반 나누어서 가리키게 됩니다. 이때, 0으로 시작하는 hash value을 가지는 값들이 첫 번째 버킷에 들어가고 1로 시작하는 prefix값을 두 번째 버킷에 삽입하게 됩니다.

이제 11을 삽입해 보겠습니다. 11 % 8 = 3이고 이를 2진수로 변환하면 011입니다. 그리고 0으로 시작하기 때문에 첫 번째 버킷에 삽입 해주면 됩니다. 

또 17을 삽입해 보겠습니다. 17을 hash function을 통해 17 % 8  = 1 값이 나오면 이를 2진수로 변환하여 001이라는 얻을 수 있습니다. 그리고 001은 0으로 시작하기 때문에 첫 번째 버킷에 넣으려고 해서 봤더니 버킷이 꽉차서 overflow가 발생하게 됩니다. 또한 첫 번째 버킷을 가리키는 pointer가 하나이기 때문에 split과정을 거쳐야합니다. Hash Prefix를 split을 할 때는 2배씩 늘려줍니다. 그리고 i + 1을 해줍니다.

따라서 위 그림처럼 hash prefix를 2개에서 4개로 split을 해주고 pointer의 개수로 늘어나게 됩니다. 하지만 여전히 Bucket의 개수는 늘어나지 않아서 17을 삽입하려고 봤더니 overflow가 발생하여 Bucket을 늘려주어야합니다. split할 때는 i + 1을 잊지 말아주세요!

다음 그림과 같이 00으로 시작하는 hash prefix는 첫 번째 버킷으로 01로 시작하는 값은 두번 째 버킷으로 10, 11로 시작하는 값은 세 번째 버킷으로 넣어줍니다. 

이제 19을 삽입하겠습니다. 19를 hash function에 넣으면 19 % 8 = 3이고 이를 2진수로 변환하면 011입니다. 01로 시작하기 때문에 두 번째 버킷에 넣으려고 봤더니 Full 상태이기 때문에 overflow가 발생합니다. 그리고 두 번째 버킷을 가리키는 pointer가 하나 이기 때문에 split을 과정을 거칩니다. 이때 i + 1을 잊지 마세요! hash prefix는 2배로 총 8개로 split 됩니다. 

이렇게 split을 하고 Bucket을 살펴보면 개 수는 늘어나지 않았기 때문에 bucket로 split을 해주어야합니다. i + 1을 해주어서 i = 3인 버킷을 만들어 줍니다. 그리고 pointer의 개수도 2배씩 늘어나게 됩니다. 즉, 010과 011을 pointer로 나눠 가리키게 됩니다. 그리고 19는 011로 시작하기 때문에 해당 버킷으로 들어가게 됩니다. 

이렇게 split을 통해 값을 삽입하게됩니다. 그럼 이제 23을 삽입해 보겠습니다. 23을 hash function을 거치면 23 % 8 = 7이고 이를 이진수로 변환하면 111입니다. 따라서 111이 가리키는 pointer를 따라가 보니 버킷이 꽉차있지 않아서 그냥 삽입해 주면 됩니다. 

그 다음에 29를 삽입해 보겠습니다. 마찬가지로 29 % 8  = 5이고 이를 2진수로 변환하면 101입니다. 101이 가리키는 pointer를 따라가봤더니 버킷이 꽉차 있어서 overflow가 발생합니다. 하지만 이때 보니 해당 버킷은 pointer가 하나가 아니기 때문에 hash prefix를 2배 split할 필요가 없습니다. 그래서 바로 Bucket을 split해주면됩니다. split하는 과정에서 i+1을 잊지 마세요! 이진수가 101이기 때문에 i = 1 -> i = 2로 만들고 101로 시작하는 값을 보관할 버킷을 새로 만들어 줍니다. 

i값을 2로 증가시켜주고 가리키는 pointer또한 절반으로 나눠주는 작업을 통해 split하여 29을 삽입하였습니다. 마지막으로 31을 삽입해 보겠습니다. 31을 hash funcion에 통과시키면 31 % 8 = 7이고 이를 2진수로 변경하면 111입니다. 111이 가리키는 pointer를 따라가서 버킷을 살펴보니 버킷이 공간이 있음을 확인하여 그냥 삽입해 주었습니다. 

그래서 최종적으로 값이 17, 3, 11, 19, 7, 23, 31임을 확인할 수 있습니다.