해싱과 비트맵 인덱스
해시(Hash)
- 탐색 키에 산술 연산을 통해 버킷의 주소를 계산하는 해시함수를 사용하여 데이터 배분 및 접근하는 기법
버킷(Bucket)
- 한 개 이상의 레코드를 저장할 수 있는 저장공간의 단위
- 크기는 일반적으로 디스크 블록의 크기와 일치
해시의 성능은 레코드가 균등하게 배분되었을 때 성능이 높다.
균등 배분은 일반적으로는 이론적으로만 가능하고 한쪽으로 몰리는 경우만 없도록 설계해야한다.
해시 파일 구조
정적해싱
- 버킷의 개수가 고정된 해싱 기법
- 키 값이 Ki인 레코드 삽입
- 버킷 주소를 해시 함수로 생성하여 해당 버킷에 저장
- 키 값이 Ki인 레코드 검색
- 해시 함수로 주소를 생성하여 버킷에 저장된 레코드 접근
충돌과 동거자
- 충돌 : 서로 다른 두 레코드가 동일한 버킷에 대응
- 동거자 : 충돌에 의해 같은 버킷 주소를 갖는 레코드
Overflow
- 충돌이 많아져서 동거자가 많아지게 되면 오버플로우가 발생한다.
해시 인덱스
정적 해싱의 문제점
- 데이터 베이스의 크기가 커짐에 따른 성능 감소
- 미리 큰 공간을 잡을 경우 초기에 상당한 양의 공간이 낭비
- 재구성 시 새롭게 선택된 해시 함수를 사용하여 모든 레코드에 대하여 다시 계산하고 버킷에 할당하는 재구성 비용이 발생
동적해싱
- 동적 해싱의 정의
- 버킷의 개수를 가변적으로 조절할 수 있는 해싱 기법
- 데이터 베이스의 크기에 따라 버킷의 크기가 비례
- 데이터베이스의 증대 혹은 축소에 따른 인덱스의 구조를 조절하기 위해 해시함수를 동적 변경하는 기술
- 확장성 해싱
- 동적 해싱의 일종으로 디렉터리와 버킷의 2단계 구조
- 디렉터리는 디스크에 저장되는 버킷 주소 테이블
- 디렉터리의 깊이는
확장성 해싱
- 모조키(pseudo key)
- 레코드의 탐색키 값이 해시 함수에 의해 일정길이의 비트 스트링으로 변환된 키
- 모조키의 첫 d 비트를 사용하여 디렉터리에 접근
- 버킷헤더
- 정수값 (i<=d) 가 저장되어 있음을 표시
- i는 버킷에 저장되어 있는 레코드의 모조키들이 처음부터 일치함을 표시
확장성 해싱의 구조
비트맵 인덱스
- 탐색키의 중복 비율이 높은 컬럼을 대상으로하는 질의를 효율적으로 처리하기 위한 고안된 특수한 형태의 인덱스