1. 확장성 해싱(Extendible Hashing)의 개요
가. 개념
해시 함수 결과값의 일부 비트를 사용하여 **디렉터리(Directory)**를 구성하고, 데이터 양에 따라 디렉터리와 **버킷(Bucket)**을 동적으로 분할/병합하는 가변 크기 해싱 기법입니다.
정적 해싱과 달리 재구성(Rehashing) 시 전체 데이터를 이동시키지 않고 특정 버킷만 분할하여 효율적입니다.
2. 가. 확장성 해싱의 주요 구성요소
확장성 해싱은 전역 깊이와 지역 깊이의 비교를 통해 분할 여부를 결정합니다.
| 구성요소 | 상세 설명 | 비고 |
| 디렉터리 (Directory) | 버킷의 주소 포인터를 저장하는 테이블 | $2^d$ 개의 엔트리 보유 |
| 전역 깊이 (Global Depth, $d$) | 디렉터리 엔트리를 식별하는 데 사용하는 비트 수 | 디렉터리 크기 결정 |
| 버킷 (Bucket) | 실제 데이터 레코드(또는 키)가 저장되는 공간 | 고정된 크기 보유 |
| 지역 깊이 (Local Depth, $p$) | 특정 버킷에 저장된 레코드들이 일치하는 비트 수 | $p \le d$ 유지 |
| 해시 함수 (Hash Function) | 키 값을 이진수 비트열로 변환하는 함수 | 하위/상위 $d$비트 참조 |
3. 나. 충돌 및 오버플로우 회피 기법 (분할 메커니즘)
데이터 삽입 시 버킷이 가득 차면($Full$), **전역 깊이($d$)**와 해당 버킷의 지역 깊이($p$) 관계에 따라 대응 방식이 달라집니다.
(1) Case 1: 지역 깊이 < 전역 깊이 ($p < d$)
상황: 디렉터리의 크기는 충분하지만, 특정 버킷에 데이터가 집중된 경우입니다.
회피 기법 (버킷 분할):
해당 버킷을 2개로 분할하고 지역 깊이를 $p+1$로 증가시킵니다.
디렉터리의 크기는 유지하며, 포인터만 재배열하여 분할된 버킷을 가리키게 합니다.
전체 데이터를 재해싱하지 않고 해당 버킷 내 데이터만 재배치합니다.
(2) Case 2: 지역 깊이 = 전역 깊이 ($p = d$)
상황: 현재 디렉터리 구조로는 더 이상 버킷을 분할하여 수용할 수 없는 경우입니다.
회피 기법 (디렉터리 확장):
전역 깊이를 $d+1$로 증가시켜 디렉터리 크기를 2배로 확장합니다.
기존 디렉터리 엔트리들을 복사하고 포인터를 업데이트합니다.
가득 찬 버킷을 분할하고 지역 깊이를 $p+1$로 수정하여 할당합니다.
4. 확장성 해싱의 장단점 및 비교
| 구분 | 장점 | 단점 |
| 확장성 해싱 | * 데이터 증가에 따른 성능 저하가 적음 * 보조 기억장치 액세스 횟수 최소화 (대개 2회) | * 디렉터리 관리에 따른 추가 메모리 소모 * 데이터 편중 시 디렉터리만 급격히 커질 위험 |
5. 기술사적 제언: 실무 적용 및 고도화 방향
인덱스 설계 최적화: 대용량 데이터베이스의 물리 설계 시, 데이터의 분포가 고르지 않을 경우 확장성 해싱보다는 **선형 해싱(Linear Hashing)**이 디렉터리 관리 오버헤드 측면에서 유리할 수 있으므로 비교 검토가 필요합니다.
메모리 내 해싱 활용: 최근 인메모리 DB나 캐시 시스템에서는 고정된 해시보다는 확장성 해싱의 원리를 이용하여 Lock-Free한 동적 확장 구조를 설계하여 동시성을 높이는 추세입니다.
보안 고려: 해시 충돌을 의도적으로 유발하는 Hash DoS 공격에 대비하여, 솔트(Salt)를 추가하거나 암호화 해시 함수를 결합하는 보안 거버넌스 체계가 병행되어야 합니다.
댓글 없음:
댓글 쓰기