[Database] DBA급 개발자로 - #6 Hash Table

이전 포스팅에서 DBMS가 디스크의 데이터를 메모리의 버퍼 풀에 어떻게 로드해서 사용하는지와 버퍼 풀에 로드된 페이지를 제거하는 여러 정책에 대해 살펴봤습니다. 이번 포스팅에서는 버퍼 풀에 로드된 페이지를 효과적으로 읽고 쓰기 위해서 사용하는 자료구조인 Hash table에 대해 살펴보겠습니다. 

 

Hash Table 

해시 테이블은 배열을 활용해 정렬되지 않은 key와 value를 저장하는 자료구조입니다. Key에 해시함수를 적용한 결괏값을 사용해서 해당 key와 value를 저장할 배열의 offset을 구할 수 있습니다. DBMS에서 사용되는 해시 테이블에 대해 알아보겠습니다. 

Static Hash Table 

저장하고자 하는 데이터 수를 N이라 할 때, 길이 N의 배열을 사용하는 해시 테이블입니다. 대표적으로 Linear Probe Hashing, Robin Hood Hashing과 Cuckoo Hashing 등이 있습니다. 

Linear Probe Hashing 

데이터를 저장할 때 해시 충돌이 발생하면 그다음 비어있는 slot을 찾을 때까지 스캔해서 데이터를 저장하는 방식입니다. 

해시 테이블에는 A가 저장된 상태

위의 사진과 같이 A가 저장된 해시 테이블에 B를 저장한다고 합시다. hash(B) = hash(A)라고 가정합시다. B가 저장될 수 있는 위치에는 이미 A가 저장됐기 때문에 3번째 offset 이후에 빈 슬롯을 찾아서 B를 저장합니다. 

빈 slot에 B를 저장

hash(C)도 3번째 slot에 대응된다고 하면 C를 저장했을 때 해시 테이블은 다음과 같습니다. 

C를 저장

만약 여기서 해시 테이블의 B에 대응되는 key, value를 삭제하면 어떻게 될까요? 

B제거 후 C 탐색 시도

여기서 C에 대응되는 key와 value가 있는지 어떻게 확인할까요? hash(C)는 3번째 slot에 대응되지만 기존에 A와 B가 먼저 저장됐었기 때문에 현재 5번째 slot에 저장돼있습니다. 하지만 4번째 slot에 위치했던 B가 삭제되면서 C를 확인하기 위해 5번째 slot까지 탐색할 수 없습니다. 그렇게 되면 C가 존재하지 않는다고 판단하게 됩니다. 이 문제를 해결하기 위해서 다음과 같은 방법을 사용할 수 있습니다. 

Tombstone

첫 번째 방법은 Tombstone을 사용하는 것입니다. Tombstone은 해당 slot에 데이터가 삭제됐음을 표시하고 이후의 탐색 요청은 tombstone을 기점으로 탐색을 멈추는 게 아니라 tombstone 이후의 slot에 대해서도 탐색을 진행할 수 있습니다.

삭제 시 이동

두 번째 방법은 빈 공간 이후에 저장된 데이터를 빈 공간을 차지하도록 이동시키는 방법입니다. 

 

지금까지 살펴본 linear probe hashing은 저장하고자 하는 대상이 unique key만 가졌다고 가정했을 때의 동작 방식입니다. 그럼 non-unique key를 저장할 때는 어떻게 동작할지 살펴보겠습니다. 

Linked List

첫 번째 방법은 위와 같이 특정 key와 관련된 value를 linked list 형태로 저장하는 방법입니다. 

Redundant Keys

두 번째 방법으로는 위와 같이 key와 value를 함께 저장해서 구분하는 방식입니다. 

Robin Hood Hashing

Linear probe hashing과 유사하지만 해시 충돌을 처리하는 방식이 다릅니다. 각 키는 원래 저장돼야 하는 슬롯으로부터 떨어진 거리(최적 위치로부터의 거리)를 함께 저장합니다. (새로 저장할 데이터의 최적 위치로부터의 거리 > 기존에 저장된 데이터의 최적 위치로부터의 거리) 조건을 만족하면 기존 키를 밀어내고 그 위치에 새로운 키를 저장할 수 있습니다. 하단의 이미지는 robin hood hashing 이 동작하는 원리입니다. 

Robin Hood Hashing

Cuckoo Hashing 

2개의 해시 테이블을 사용하는 방식입니다. 빈 슬롯이 있다면 키는 해당 슬롯에 저장됩니다. 만약 빈 슬롯이 없다면 기존에 저장된 키를 제거하고 해당 키를 저장합니다. 제거된 키는 다른 해시 테이블에 저장을 시도합니다(재귀적으로 반복). 

Cuckoo Hashing

지금까지 살펴본 방식들을 사용하려면 저장하려는 데이터의 수를 미리 알 수 있어합니다. 만약 데이터의 수를 미리 알 수 없다면 해시 테이블의 크기를 조절해야 합니다. 다음으로 살펴볼 Dynamic 해시 테이블은 데이터의 수에 따라 자동적으로 그 크기를 조절합니다. 

 

Dynamic Hash Table

Dynamic 해시 테이블은 데이터의 수에 따라 자동으로 크기를 조절합니다. 대표적인 Dynamic 해시 테이블의 동작원리에 대해 살펴보겠습니다. 

Chained Hashing 

해시 테이블의 각 슬롯은 linked list 형태의 bucket을 가리키는 포인터를 저장합니다. 동일한 해시 키를 가진 값은 동일한 bucket에 저장합니다. 특정 데이터를 조회하기 위해서 해당 해시 키를 통해 bucket을 찾고, bucket에 저장된 데이터를 순차 탐색하면 됩니다. 삽입과 삭제의 성능은 bucket의 크기에 따라 달라집니다. 

Chained Hashing

Extendible hashing 

Chained hashing의 경우 bucket의 linked list수가 무한히 증가할 수 있습니다. Extendible hashing은 bucket이 무한히 커지는 것을 방지하기 위해 bucket을 분리하고 bit count를 통해 관리합니다. Bit count를 증가시켜 bucket을 분리할 수 있습니다. 

 

Linear Hashing 

Linear hashing에 대해서는 다음 링크를 참고하세요. 

 

마무리 

이번 포스팅을 통해 DBMS에서 사용하는 해시 테이블에 대해 살펴봤습니다. 다음 포스팅에서는 DBMS가 사용하는 대표적인 자료구조인 B+Tree에 대해 살펴보겠습니다.