[데이터베이스] 데이터베이스의 저장과 접근 : 해싱

※  해싱(hashing) 방법 (ideal)

• 다른 레코드의 참조 없이 목표 레코드의 접근을 직접 지원 (직접 파일, direct file)
• 키(key) 값과 레코드 주소(address) 사이의 사상(mapping) 관계를 함수로 설정
• 해싱 함수(hashing function) : 키(key) 값으로부터 레코드 주소(address)를 계산, 사상 함수(mapping function) : 키 → 주소, 삽입, 검색에 모두 이용

 

1. 버킷 해싱

• 버킷(bucket) : 하나의 주소를 가지면서 하나 이상의 레코드를 저장할 수 있는 파일의 한 구역
• 버킷 크기 : 저장 장치의 물리적 특성과 한번 접근으로 채취 가능한 레코드 수를 고려
• 버킷 해싱 : 키 → 버킷 주소
• 충돌(collision) : 상이한 레코드들을 같은 주소(버킷)로 변환
• 해시 함수가 같은 주소로 변환시킨 모든 레코드들을 동거자(synonym)라 한다.
• 레코드를 삽입하는 경우에 이 충돌은 버킷에 자유 공간이 있는 한 문제가 되지 않지만, 그 버킷이 만원이 된 경우에는 오버플로우가 일어나기 때문에 별개의 오버플로우 버킷 (Linked List)을 할당하여 처리할 수 밖에 없다.
• 이것은 결국 또 한번의 디스크 입출력을 필요하게 만들기 때문에 해싱 기법에서는 이 충돌로 인한 오버플로우를 어떻게 처리하느냐가 가장 큰 관심사 중 하나.

버킷 해싱

• 퍼펙트 해싱(perfect hashing) : 키 값에 관계 없이 버킷 주소를 적절히 분산시켜주는 해싱 함수 (불가능에 가깝다)

 

2. 확장성 해싱(extendible hashing)

• 충돌에 대처하기 위해 제안된 기법
• 레코드 검색은 최대 2번의 디스크 접근만 필요

○  모조 키(pseudokey)

• 확장성 해싱 함수 : 키 값 → 일정 길이의 비트 스트링, pseudokey로 변환
• pseudokey의 처음 d 비트를 디렉터리의 인덱스로 사용

○  디렉터리(directory)

• 헤더에 현재의 디렉터리 깊이 d(전역 깊이, global depth)를 유지
• 2^d 개의 버킷들을 지시할 수 있는 포인테 엔트리로 구성
• 디스크에 저장

 

※  저장

• 모조 키의 처음 d 비트를 디렉터리에 대한 인덱스로 사용
• 접근된 디렉터리 엔트리는 목표 버킷에 대한 포인터를 제공
• 예시) 레코드 키 값  k → 모조키 101000010001
• 디렉터리의 깊이(d)가 3이므로 모조 키의 처음 3비트를 사용 - 디렉터리의 6번째(101) 엔트리로 접근
• 엔트리는 4번째 버킷에 대한 포인터, 키 값 k를 가지고 있는 레코드가 저장되어 있는 버킷, 버킷 깊이 p = 1 : 모조 키의 공통 비트 수가 1, 즉 이 버킷은 비트 1로 시작하는 레코드들을 저장

 

※  버킷 오버플로 예

• 모조키가 10으로 시작하는 레코드를 저장. 네 번째 버킷은 오버플로
• 빈 버킷을 할당하고 버킷을 분할 : 버킷의 깊이 p는 모두 2로 설정
• 디렉터리의 110과 111의 포인터 값이 새 버킷을 지시하도록 조정

디렉터리의 깊이(d)가 3일 때

디렉터리의 깊이(d)가 4일 때

• 첫 번째 버킷(000)이 만원인 경우의 레코드 삽입
• 버킷 깊이 p를 1 증가시키고 버킷을 분할
• 빈 버킷을 할당받고 p는 p+1로 설정
• 모조키가 0001로 시작되는 모든 레코드를 새로운 버킷으로 이동
• 이때 d < p+1 이 되므로 d를 d+1로 증가시켜 디렉터리 크기를 2배로 확장시킨다.
• 확장된 디렉터리의 모든 포인터를 재조정

 

※  삭제

• 삭제할 레코드를 찾아 삭제
• 한 버킷에 하나만 있는 레코드를 삭제하는 경우
• 버디(buddy) 버킷을 검사하여, 두 버디에 있는 레코드들이 하나의 버킷으로 들어갈 수 있으면 합병하고 빈 버킷은 반환
• 버디 버킷(buddy bucket) : 두 버킷이 똑같은 버킷 깊이 p를 가지고 있고 저장된 레코드 모조 키들의 처음 (p-1) 비트들이 모두 같은 버킷, 원래 하나의 버킷에서 분할된 두 버킷
• 버킷의 새로운 깊이 값은 p-1
• 모든 버킷들의 깊이, p가 디렉터리 깊이, d보다 작게 되면 디렉터리의 깊이 d를 하나 감소(d → d-1)
• 디렉터리의 엔트리 수가 반으로 감소되기 때문에 모든 포인터들을 적절히 재조정