확장성 해싱: 디렉터리와 버킷으로 동적 데이터를 찾는 방법
확장성 해싱의 디렉터리·버킷 구조와 전역 깊이, 지역 깊이의 관계를 정리하고 분할·확장 과정 및 선형 해싱과의 차이를 설명한다.
2026-08-14 · 최초 발행 2025-08-10
동적 해시 테이블에서 디렉터리가 맡는 역할
확장성 해싱(Extendible Hashing)은 데이터베이스 시스템에서 데이터 양의 변화에 대응하기 위해 설계된 동적 해싱 기법이다. 1978년 Fagin 등에 의해 제안됐으며, 정적 해싱에서 문제가 되는 고정된 버킷 구조를 디렉터리와 버킷의 2단계 구조로 풀어낸다.
디렉터리는 해시 결과를 바탕으로 버킷을 찾는 인덱스이고, 실제 레코드는 버킷에 들어간다. 이 구조는 공간 활용과 검색 성능을 함께 다루기 위한 방식이다.
- 전역 깊이(Global Depth)는 디렉터리 크기를 결정하는 비트 수다.
- 지역 깊이(Local Depth)는 개별 버킷에 도달하는 데 필요한 비트 수다.
해시값에서 버킷까지 가는 경로
키를 찾을 때는 먼저 해시 함수를 적용해 해시값을 만든다. 그 뒤 전역 깊이만큼의 상위 비트로 디렉터리 엔트리를 선택하고, 해당 엔트리가 가리키는 버킷에서 데이터를 검색한다.
오버플로우가 발생했을 때의 처리
버킷이 가득 차면 해당 버킷을 분할한다. 이때 지역 깊이가 증가하고 새 버킷이 만들어지며, 기존 레코드는 해시값에 따라 두 버킷으로 다시 배치된다.
분할하려는 버킷의 지역 깊이가 전역 깊이보다 커져야 한다면 디렉터리도 확장해야 한다. 전역 깊이는 1 증가하고 디렉터리 크기는 2배가 된다. 새 디렉터리 엔트리는 각 버킷을 적절히 가리키도록 설정한다.
초기 상태에서 전역 깊이가 1이면 디렉터리는 다음처럼 구성될 수 있다.
디렉터리:
[0] -> 버킷 A (지역 깊이=1, 데이터: 8, 24)
[1] -> 버킷 B (지역 깊이=1, 데이터: 5, 21)
버킷 A에 40을 넣어 오버플로우가 발생하면 전역 깊이는 1 -> 2로 증가하고, 디렉터리는 2배로 확장된다.
디렉터리:
[0] -> 버킷 A' (지역 깊이=2, 데이터: 8)
[1] -> 버킷 B (지역 깊이=1, 데이터: 5, 21)
[2] -> 버킷 A'' (지역 깊이=2, 데이터: 24, 40)
[3] -> 버킷 B (지역 깊이=1, 데이터: 5, 21)
버킷 A는 A'와 A''로 나뉘고, 버킷 B는 계속 디렉터리의 [1]과 [3] 항목을 함께 사용한다.
선형 해싱과 달라지는 지점
| 특성 | 확장성 해싱 | 선형 해싱 |
|---|---|---|
| 구조 | 디렉터리-버킷 2단계 | 단일 해시 테이블 |
| 분할 방식 | 오버플로우 발생한 버킷만 분할 | 미리 정해진 순서로 분할 |
| 확장 비율 | 2배씩 확장 | 점진적 확장 |
| 공간 효율 | 디렉터리 오버헤드 발생 | 상대적으로 더 효율적 |
| 검색 성능 | 항상 2단계 접근 | 1-2단계 접근 |
| 구현 복잡도 | 상대적으로 복잡 | 상대적으로 단순 |
확장성 해싱은 필요한 버킷만 재구성해 데이터 증가를 처리한다. 검색은 디렉터리와 버킷을 거쳐 최대 2단계 접근으로 수행할 수 있고, 버킷 간 데이터 분포도 상대적으로 균등하게 유지된다.
다만 디렉터리는 메모리에 상주해야 하므로 공간을 크게 차지할 수 있다. 분할과 병합 로직도 복잡하며, 특정 패턴의 데이터가 몰리면 효율이 떨어질 수 있다. 전역 깊이가 커질수록 디렉터리 크기가 기하급수적으로 증가한다는 점도 제약이다.
디렉터리와 버킷을 다루는 최적화
같은 버킷을 가리키는 디렉터리 엔트리가 여럿이라면 하나의 엔트리로 압축할 수 있다. 디렉터리 크기와 메모리 사용량을 줄일 수 있지만, 구현 복잡도는 늘어난다. 검색 성능은 유지된다.
작은 버킷 여러 개를 논리적으로 그룹화하는 방법도 있다. I/O 비용과 공간 효율성을 개선할 수 있는 대신, 그룹 안의 데이터 분포를 관리해야 한다.
데이터 분포에 따라 해시 함수를 동적으로 조정하는 적응형 해시 함수는 편향된 데이터 분포에서도 효율적인 성능을 유지하는 방식이다. 추가 연산 오버헤드는 고려 대상이다.
인덱스와 분산 데이터 구조에서의 활용
PostgreSQL, MySQL InnoDB 등의 DBMS에서는 인덱스 구조로 활용할 수 있으며, 동적 데이터 환경에서 빠른 레코드 접근을 제공한다. B+ 트리와 결합해 복합 인덱싱 구조를 구현하는 데도 쓰인다.
분산 해시 테이블(DHT) 구현 기법으로도 활용되며, 노드 추가와 제거에 효율적으로 대응할 수 있다. Chord, Pastry 등의 P2P 시스템이 응용 대상이다.
Redis, Memcached 등의 메모리 캐시 시스템에서는 데이터 색인과 빠른 키-값 조회를 지원한다. 대규모 파일 시스템의 디렉터리 구조 관리에서도 파일 개수 증가에 따른 동적 확장과 균형 잡힌 파일 분포를 위해 활용할 수 있다.
비용을 볼 때 확인할 복잡도
검색은 O(1)로 고정된 단계 안에서 끝난다. 삽입은 평균 O(1)이고, 디렉터리 확장 시 최악 O(n)이 될 수 있다. 삭제도 평균 O(1)이지만 버킷 병합에서는 추가 비용이 발생한다.
공간 복잡도는 디렉터리 O(2^d), 버킷 O(n), 전체 O(2^d + n)이다. 여기서 d는 전역 깊이이고 n은 총 데이터 수다. 데이터가 증가하면 확장 비용은 로그 스케일로 증가하며, 버킷 분할 때는 재분배 비용이 들고 디렉터리 확장 시에는 일시적인 성능 저하가 가능하다.