동적 해싱과 확장 해싱의 버킷 분할 구조

레코드 증가가 해시 구조를 흔들 때

정적 해싱은 데이터량이 늘어나면 버킷 오버플로우와 검색 성능 저하에 부딪힌다. 동적 해싱은 이 문제를 다루기 위해 버킷 크기와 구조를 변화시키는 해싱 기법이다.

해시값과 실제 버킷의 연결은 디렉토리, 즉 버킷 주소 테이블이 맡는다. 레코드가 늘면 버킷을 분할하고, 삭제로 데이터가 줄면 버킷을 병합할 수 있다. 데이터 분포 변화에 맞춰 해시 구조를 조정하는 방식이다.

오버플로우를 처리하는 방식

충돌이나 버킷 초과를 다루는 방법은 구조에 따라 다르다.

Direct Chaining

같은 해시 테이블 안에서 충돌한 레코드를 링크드 리스트로 연결하는 방식이다. 구현은 단순하지만 체인이 길어질수록 검색 성능이 떨어질 수 있다.

⤢✕

Indirect Chaining

메인 해시 테이블과 분리된 오버플로우 공간을 마련하는 방법이다. 동일 해시값(synonym)을 가진 레코드는 별도 공간에서 링크드 리스트로 관리하므로, 메인 테이블과 오버플로우 영역을 나누어 다룰 수 있다.

⤢✕

별도 오버플로우 영역

링크 없이 지정된 오버플로우 영역에 레코드를 순차 저장하는 방식도 있다. 구조는 단순하지만, 그 영역을 관리하기 위한 추가 비용이 발생한다.

확장 해싱

확장 해싱(Extendible Hashing)은 동적 해싱을 구현하는 대표적인 방식이다. 디렉토리와 버킷으로 나뉜 구조에서 버킷이 넘치면 해당 버킷을 분할하고, 필요하면 디렉토리를 확장한다.

해시 비트와 깊이로 버킷을 가리키는 방법

확장 해싱은 키에 해시 함수를 적용해 비트 스트링(해시값)을 만들고, 해시값 앞부분의 비트로 디렉토리 엔트리를 선택한다.

여기에는 두 깊이가 있다.

• 글로벌 깊이(Global Depth)는 디렉토리가 사용하는 비트 수다.
• 로컬 깊이(Local Depth)는 각 버킷이 사용하는 비트 수다.

버킷 오버플로우가 생기면 버킷을 두 개로 분할하고 로컬 깊이를 늘린다. 로컬 깊이가 글로벌 깊이와 같다면 디렉토리 크기를 두 배로 확장하며 글로벌 깊이도 증가한다.

⤢✕

검색 성능과 공간 관리의 균형

동적 해싱은 파일 크기가 커도 디스크 접근을 최대 2번으로 제한한다. 첫 접근은 디렉토리, 두 번째 접근은 실제 데이터 버킷에 해당한다.

버킷 분할은 데이터 증가 중에도 검색 성능을 일정하게 유지하는 데 쓰인다. 디렉토리는 상대적으로 크기가 작아 전체를 메모리에 유지할 수 있고, 데이터 삭제 시에는 버킷 병합으로 공간을 회수할 수 있다. 확장 해싱에서는 트리 깊이가 2로 제한되며, 구조 재구성도 한 번에 한 버킷에서만 발생해 상대적 부하를 줄인다.

반대로 디렉토리 생성과 관리는 추가 비용을 만든다. 디렉토리 크기가 두 배가 되는 시점에는 상당한 오버헤드가 생길 수 있다. 초기 버킷 크기에 따라 데이터가 적을 때 디스크 공간이 낭비될 수 있고, 디렉토리를 거치는 간접 검색은 직접 주소 지정보다 추가 메모리 접근을 요구한다. 버킷 분할·병합, 디렉토리 확장, 동시성 제어까지 구현해야 한다는 점도 정적 해싱보다 복잡하다.

데이터베이스와 분산 저장소에서의 활용

PostgreSQL, MySQL 등의 DBMS는 인덱싱 메커니즘에 이를 활용하며, 대용량 데이터 처리에서 검색 성능 향상에 기여한다.

분산 시스템에서는 일관된 해싱(Consistent Hashing)과 함께 분산 데이터 저장소를 구성하는 데 사용된다. 노드가 추가되거나 제거될 때 데이터 재분배를 최소화하는 목적이다.

Redis, Memcached 등의 인메모리 캐시 시스템에서는 키-값 저장 메커니즘으로 활용되어 빠른 액세스와 동적 확장성을 제공한다. 대용량 파일 시스템에서도 파일 색인과 관리에 적용하며, 파일 증가에 따라 디렉토리 구조를 동적으로 확장한다.

확장 해싱 의사 코드

아래 의사 코드는 디렉토리 확장, 버킷 분할, 레코드 재분배의 흐름을 보여준다.

class ExtendibleHashTable:
    global_depth = 1
    directory = [Bucket(), Bucket()]  // 초기 디렉토리 크기 2

    function insert(key, value):
        hash_val = hash_function(key)
        index = extract_bits(hash_val, global_depth)
        bucket = directory[index]

        if bucket.has_space():
            bucket.insert(key, value)
        else:
            if bucket.local_depth == global_depth:
                // 디렉토리 확장 필요
                double_directory()
                global_depth += 1

            // 버켓 분할
            split_bucket(bucket, index)
            // 재귀적으로 삽입 시도
            insert(key, value)

    function double_directory():
        old_size = 2^global_depth
        for i from 0 to old_size-1:
            directory[i + old_size] = directory[i]

    function split_bucket(bucket, index):
        bucket.local_depth += 1
        new_bucket = Bucket(local_depth = bucket.local_depth)

        // 기존 버켓의 항목들을 재분배
        for each (k, v) in bucket:
            hash_val = hash_function(k)
            new_index = extract_bits(hash_val, bucket.local_depth)
            if new_index != index:
                new_bucket.insert(k, v)
                bucket.remove(k)

        // 디렉토리 포인터 업데이트
        update_directory_pointers(bucket, new_bucket, index)

동적 해싱은 데이터 증가에 따른 성능 저하를 줄이면서 데이터 접근을 유지하려는 구조다. 다만 디렉토리 관리 비용, 초기 공간 낭비 가능성, 간접 검색과 구현 복잡성까지 함께 고려해 데이터 특성과 시스템 요구사항에 맞춰 설계해야 한다.