정적 해싱
해시
- 해시: 탐색키에 산술적인 연산을 통해 버킷의 주소를 계산하는 해시 함수를 사용하여 데이터 배분 및 접근하는 기법
- 버킷: 한 개 이상의 레코드를 저장할 수 있는 저장공간의 단위
- 단점: 버킷에 레코드가 몰릴 수 있음
정적 해싱의 특싱
- 버킷의 개수가 고정된 해싱 기법 (사용전 이미 고정)
- 키 값이 ki인 레코드 삽입: h(ki)를 통하여 ki에 대응하는 버킷 주소를 생성하고 레코드를 해당 버킷에 저장
- 키 값이 ki인 레코드 검색: h(ki)을 통하여 버킷 주소를 생성하고 버킷에 저장된 레코드 접근
충돌과 동거자
- 충돌: 서로 다른 두 레코드가 동일한 버킷에 대응
- 동거자: 충돌에 의해 같은 버킷 주소를 갖는 레코드
오버플로(overflow)
- 버킷에 레코드를 저장할 수 있는 여유 공간이 없는 상황에 발생
- 추가적인 버킷을 할당 또는 다음 버킷에 할당하여 처리
- 오버플로우가 발생할수록 접근시간이 길어지고 해시성능이 저하
해시 인덱스
- 해시 파일 구조와 동작 방식을 레코드가 아닌 인덱스 엔트리에 적용한 인덱스
- 단점
- 데이터베이스의 크기가 커짐에 따른 성능 감소
- 미리 큰 공간을 잡을 경우 초기에 상당한 양의 공간이 낭비
- 재구성시 새롭게 선택된 해시 함수를 사용하여 모든 레코드에 대하여 다시 계산하고 버킷에 할당하는 대량의 비용이 발생 -> 동적 해싱
동적 해싱
동적 해싱의 개념
- 버킷의 개수를 가변적으로 조절할 수 있는 해싱 기법
- 데이터베이스의 크기에 따라 버킷의 크기가 비례
- 데이터베이스의 증대 혹은 축소에 따른 인덱스의 구조를 조절하기 위해 해시 함수를 동적 변경하는 기술
- 확장성 해싱
- 동적 해싱의 일종으로 디렉터리와 버킷의 2단계 구조
- 디렉터리는 디스크에 저장되는 버킷주소 테이블
확장성 해싱
- 모조키(pseudo key)
- 레코드의 탐색키 값이 해시 함수에 의해 일정 길이의 비트 스트링으로 변환된 키
- 모조키의 첫 d 비트를 사용하여 디렉터리에 접근
- 버킷 헤더
비트맵 인덱스
- 탐색키의 중복 비율이 높은 컬럼을 대상으로 하는 질의를 효율적으로 처리하기 위해 고안된 특수한 형태의 인덱스
- 비트맵
- 간단한 비트의 배열
- 릴레이션 r의 속성 A에 대한 비트맵 인덱스는 A가 가질 수 있는 값에 대해 비트맵을 구성
- 각 비트맵은 릴레이션에 있는 레코드의 수 n개 만큼 n개의 비트로 표현
- 비트맵 활용: 컬럼에 대한 값의 범위가 유한하고 비교적 개수가 적은 규모일 때 용이
- 레코드의 크기가 수백 바이트 이상이 되어도 비트맵 인덱스에서는 하나의 비트로 표시