확장 해싱: 디렉토리와 버킷으로 확장하는 동적 인덱스

데이터 증가에 맞춰 해시 구조를 키우는 방식

확장 해싱은 대용량 데이터베이스에서 데이터 접근 성능을 유지하면서 저장 구조를 동적으로 늘리기 위한 해싱 기법이다. 해시 테이블 전체를 다시 구성하는 대신, 디렉토리와 버킷을 분리해 필요한 범위만 확장한다.

디렉토리는 2^d개의 포인터로 구성되며, 여기서 d는 전역 깊이다. 실제 레코드는 버킷에 저장한다. 디렉토리는 2배씩 커지고 버킷은 선형적으로 증가하므로, 데이터가 늘어날 때 재구성 비용을 줄일 수 있다.

디렉토리는 버킷 주소를 담은 포인터 배열이다. 전역 깊이 d에 따라 2^d개의 항목을 가지며, 데이터 증가에 따라 크기가 2배로 확장된다. 헤더에는 전역 깊이 값이 기록된다.

모조키는 원본 키에 해시 함수를 적용해 얻는 비트 스트링이다.

원본 키 → 해시 함수 → 모조키(비트 스트링)

이 비트 스트링의 처음 d비트가 디렉토리 인덱스로 사용된다.

버킷은 실제 데이터 레코드를 저장하는 공간이다. 각 버킷 헤더에는 지역 깊이 p(≤d)가 저장된다. 하나의 버킷을 여러 디렉토리 항목이 함께 가리킬 수 있으며, 용량을 넘으면 분할이 필요하다.

초기 상태에서는 전역 깊이 d=1인 디렉토리가 각 비트값에 대응하는 버킷을 가리킬 수 있다.

레코드를 넣을 때는 키를 해시해 모조키를 만들고, 그 처음 d비트로 디렉토리 항목을 선택한 뒤 해당 버킷에 저장한다. 버킷이 가득 차면 전역 깊이와 지역 깊이를 비교해 다음 처리를 결정한다.

전역 깊이가 충분하지 않아 d < p+1이면 디렉토리의 전역 깊이를 1 늘리고, 디렉토리 크기를 2배로 확장한다. 새 항목은 기존 버킷들을 가리키도록 구성한다.

반대로 d ≥ p+1이면 디렉토리를 늘리지 않고 해당 버킷을 분할한다. 지역 깊이 p를 1 증가시키고 새 버킷을 만든 다음, 기존 레코드를 다시 배치한다. 이어서 디렉토리 항목이 새 버킷을 가리키도록 갱신한다.

검색은 키를 모조키로 변환하고 처음 d비트로 디렉토리 인덱스를 정한 뒤, 연결된 버킷에서 키를 찾는 순서로 이뤄진다. 시간 복잡도는 O(1)이지만, 최악의 경우 버킷 내부에서 선형 검색이 필요하다.

삽입도 동일하게 디렉토리를 경유해 대상 버킷을 찾는다. 버킷 오버플로우가 발생하면 d < p+1일 때는 디렉토리를 확장하고, d ≥ p+1일 때는 버킷을 분할한다.

삭제는 대상 버킷에서 레코드를 제거하는 방식이다. 버킷 병합은 구현 복잡성이 증가하므로 일반적으로 구현하지 않는다.

확장 해싱은 데이터 증가에 따라 점진적으로 구조를 키울 수 있고, 데이터 분포와 관계없이 버킷 활용을 균등화할 수 있다. 대부분의 경우 한 번의 디스크 접근으로 데이터를 검색할 수 있으며, 초기 공간 낭비도 줄일 수 있다.

대신 디렉토리가 매우 커지면 메모리 제약이 생길 수 있다. 디렉토리 확장에는 추가 연산이 필요하고, 특정 패턴의 데이터가 많으면 일부 버킷에 부하가 집중될 수 있다. 디렉토리를 거치는 과정 자체가 추가 I/O 비용이 될 가능성도 있다.

확장 해싱은 대용량 데이터베이스 인덱싱, 분산 파일 시스템의 파일 저장 및 검색, 동적으로 확장되는 메모리 캐시, IP 주소 라우팅 정보를 저장하는 네트워크 라우팅 테이블에 활용된다.

최근에는 클라우드와 분산 데이터베이스 환경에서의 최적화, 디렉토리 압축을 통한 메모리 사용량 감소, 다중 스레드 환경의 동시 접근 지원, 워크로드에 맞춘 자동 조정 기능이 발전 방향으로 다뤄진다.