확장성 해싱(동적 해싱)

# 동적 해싱 (dynamic hashing)
- 데이터베이스 성장, 축소를 조절하기 위해 해시 함수가 동적으로 변경
- 확장성 해싱

 

# 확장성 해싱 (extendable hashing)
- 해시 함수는 큰 범위의 숫자를 생성함 : 일반적으로 32비트 정수
- 버킷 주소 테이블 운영
- 해시함수 결과 중 일부 prefixi 비트 (0 <= i <= 32) 만 사용
- 버킷 주소 테이블 크기: 2^i. (i = 0 으로 초기화)
- 데이터베이스가 성장, 축소됨에 따라 i 값도 증가, 감소
- 버킷 주소 테이블의 여러 엔트리들이 동일한 버킷을 가리킬 수 있음
- 버킷의 개수는 2^i 보다 적음
- 버킷의 개수도 버킷을 합병, 분할함에 따라 동적으로 변할 수 있음
- 버킷j를 가리키는 버킷 주소 테이블의 엔트리 개수는 2^(i-ij)

 

 

# 확장성 해싱 구조 운영
- 각 버킷 j 마다 ij 값을 저장

- 버킷 주소 테이블의 엔트리들이 동일한 버킷을 가리키고 있을 경우 
  -> 해당 엔트리의 해시 값의 처음 ij 비트는 동일함

- 검색키 값 Kj 를 가지는 레코드가 포함된 버킷의 포인터 값을 구하는 과정
  1. h(Kj) = X 를 구함
  2. X의 처음 i 비트 값에 해당하는 번째의 버킷 주소 테이블 엔트리를 찾음
  3. 해당 엔트리의 포인터를 확보

- 검색키 값 Kj 를 가지는 레코드를 insert 하는 과정
  1. 검색키 값 Kj 를 가지는 레코드 위치를 구하는 과정을 수행하여 버킷 주소 테이블 엔트       리를 찾음 
  2. 해당 버킷이 새로운 레코드를 수용할 여유가 있으면 해당 레코드 추가
  3. 여유 없으면 버킷을 분할 재분배(오버플로우 버킷을 사용하는 경우도 있음)

 

 

# 확장성 해싱 : 삽입과정에서의 분할
- 검색키 값 Kj 를 가지는 레코드를 수용하기 위하여 버킷 j를 분할
- 버킷 j에 있는 레코드에 대해서만 해시 함수를 다시 계산

1. 버킷 j를 가리키는 포인터가 2개 이상인 경우 (i > ij)
- 새로운 버킷 z를 확보한 후 ij  = iz  = ij + 1로 수정
- 분할 후 버킷 j와 버킷 z를 가리키기 위한 비트 크기를 1개 증가
- 버킷 j가 분할됨에 따라 원래 있던 레코드들을 버킷 j와 버킷 z에 재분배
- 검색키 값 Kj 에 대하여 1비트 증가한 크기 기준으로 버킷 번호를 다시 계산
- 계산된 버킷(버킷j 혹은 버킷 z)으로 검색키 값 Kj 를 가지는 레코드를 배정
- 버킷 j를 가리키던 포인터들의 second half를 버킷 z를 가리키도록 수정

2. 버킷 j를 가리키는 포인터가 1개 경우 (i  = ij)
- 버킷 주소 테이블의 i를 1비트 증가  버킷 주소 테이블의 크기가 2배로 증가
- 동일한 버킷을 가리키고 있던 테이블 엔트리는 2개 엔트리로 확장
- 2배로 증가된 버킷 주소 테이블을 기준으로 검색키 값 Kj 에 대한 버킷 주소를 구함 
  -> “버킷 j를 가리키는 포인터가 2개 이상인 경우 (i > ij)” 인 경우로 처리

 

 

# 확장성 해싱 : 삭제
- 삭제할 레코드를 버킷에서 찾아서 삭제 (검색 키도 삭제)
- 레코드 삭제에 따라 버킷도 비워지는 경우 -> 버킷도 삭제
- 버킷 삭제에 따라 버킷 주소 테이블도 적절하게 수정

 

 

# 확장성 해싱 장점
- 파일의 성장, 감소에 따라 해싱 성능 저하되지 않음
- 공간 소요를 최소화

# 확장성 해싱 단점
- 원하는 레코드를 찾기 위하여 버킷주소테이블을 통한 간접 접근을 하여야 함(부가적 단계)
- 버킷주소테이블 자체가 지나치게 커질 수 있음(주기억장치에 모두 적재할 수 없게 될 수도)
- 버킷주소테이블 자체를 B+ 트리 형태로 구성하면 보다 효율적
- 버킷주소테이블에 대한 변경에 따른 추가 부담 발생