확장성 해싱(Extendible Hashing)

확장성 해싱은 동적인 데이터 저장을 위해서 주로 사용합니다. 따라서, 안정적인 자체 재배열을 지원하는 파일구조를 필요로합니다. 데이터 사이즈가 동적으로 변하기때문에, 정적 해싱에는 부적합합니다.

 

정적 해싱이란, 고정된 크기의 해시 공간을 확보하여 진행하고, 동적 해싱은 동적으로 해시 공간을 확장 혹은 축소하여 진행합니다.

 

확장성 해싱에는 Tries (Radix Searching)을 사용합니다. 분기 노드와 정보 노드를 가지고, 마지막에 위치한 정보 노드에만 실제 데이터가 존재합니다. 그 중에서도 분기점이 적은 Radix 2 trie를 사용합니다. (즉, Binary를 사용)

 

셀 주소와 셀의 배열로 이루어진 디렉토리로 데이터 버킷을 연결합니다.

 

Overflow가 발생하게 되면, 버킷을 Split하게 되는데 이때 균등하게 Split하는것은 불가능합니다.

먼저 깊이의 개념이 존재하는데, 디렉토리의 주소를 구분하는데 사용하는 비트의 크기를 뜻하는 Gloabl Depth와 버킷 내의 키들에 대한 해시 주소의 공통 비트 수를 의미하는 Local Depth가 있습니다. Overflow는 overfllow된 버킷의 Local Depth가 Global Depth와 같아진 경우 overflow의 발생으로 보고 확장을 할 수 있게됩니다. 확장하며 Split하게 되면 분리된 버킷의 Local Depth는 1 증가하게 됩니다.

 

디렉토리의 초기값은 Global Depth는 0, 셀 또한 1개로 고정됩니다.

 

삭제가 되어 디렉토리가 축소되는 경우, 삭제 대상의 주소 마지막 비트를 반전합니다. 그리고 버디 버킷을 찾아서 Merge가 되는지 검사한 후, Merge를 수행하고 Local Depth는 1 줄어듭니다. 버디 버킷의 조건은 Global Depth와 Local Depth가 같은 버킷을 의미합니다. 셀이 두 쌍씩 모두 이루게 되면 이때, Halfing이 일어나 디렉토리의 축소가 발생합니다.

 

확장성 해싱은 디렉토리가 메모리에 적재되어 있는 경우, 레코드 탐색은 1번의 접근으로 가능합니다. 반대로 적재되어 있지 않은 경우 2번의 디스크 접근으로 가능합니다. 그 외는 O(1)을 보장합니다. 하지만, Range Search에는 불리합니다.