해싱과 특수 인덱스

해시함수

1. 해시(hash) : 탐색키에 산술적인 연산을 통해 버킷의 주소를 계산하는 해시 함수를 사용하여 데이터 배분 및 접근하는 기법
   

2. 버킷(bucket)

• 한개이상의 레코드를 저장할 수 있는 저장공간의 단위
• 크기는 일반적으로 디스크 블록의 크기와 일치

3. 구조
   

4. 사용
   

5. 역할
   
   
   

6. 해시 파일 구조
   

정적해싱

1. 버킷의 개수가 고정된 해싱 기법
2. 키겂아 Ki인 레코드 삽입

• h(Ki)를 통하여 Ki에 대응하는 버킷주소를 생성하고 레코드를 해당 버킷에 저장

3. 키값이 Ki인 레코드 검색

• h(Ki)을 통하여 버킷 주소를 생성하고 버킷에 저장된 레코드 접근
• h(Ki) = h(Kj) = m인 경우가 발생하기 떄문에 버킷 m에 저장된 모든 레코드를 탐색하여 선택하는 과정이 필요

충돌과 동거자

1. 충돌 : 서로다른 두 레쿠드가 동일한 버킷에 대응
2. 동거자 : 충돌에 의해 같은 버킷 주소를 갖는 레코드
   

오버플로

1. 버킷에 레코드를 저장할 수 있는 여유공간이 없는 상황에 발생
2. 추가적인 버킷을 할당 또는 다음 버킷에 활당하여 처리
3. 오버플로우가 발생할수록 접근시간이 길어지고 해시 성능 저하
   

해시인덱스

1. 해시파일 구조와 동작방식을 레코드가 아닌 인덱스 엔트리에 적용한 인덱스
   

-> 파란선은 오버플로우가 발생했을때 처리

정정해싱의 문제

1. 데이터베이스의 크기가 커짐에 따른 성능 감소
2. 미리 큰 공간을 잡을 경우 초기에 상당한 양의 공간이 낭비
3. 재구성시 새롭게 선택된 해시함수를 사용하요 모든 레코드에 대하여 다시 계산하고 버킷에 할당하는 대량의 비용 발생

=> 동적해싱

동적해싱

1. 동적 해싱의 정의

• 버킷의 개수를 가변적으로 조절할 수 있는 해싱기법
• 데이터베이스의 크시에 따라 버킥의 크기가 비례

2. 데이터베이스의 증대 혹은 축소에 따른 인덱스의 구조를 조절하기 위해 해시 함수를 동적 변경하는 기숭

3. 확장성 해싱

• 동적해싱의 일종으로 디렉터리와 버킷의 2단계구조
• 디렉터리는 디스크에 저장되는 버킷 주소 테이블
• 디렉터리 깊이를 의미하는 정수값 d를 포함하는 헤더와 데이터가 저장된 버킷에 대한 2의 d승 개의 포인터로 구성

확장성 해싱

1. 모조키(pseudo key)

• 레코드의 탐색키 값이 해시 함수에 일정 길이의 비트 스트링으로 변횐된 키
• 모조키의 첫 d비트를 사용하여 디렉터리에 접근

2. 버킷헤더

• 정수값 i(≤d)가 저장되어있음을 표시
• i는 버킷에 저장되어 있는 레코드의 모조키들이 처음부터 i비트까지 일치함을 표시

구조

-> 오버플로우가 있을경우

확장성 해싱의 분할

1. 레코드 삽입에 의해 분할된 확장성 해싱 파일
   

비트맵 인덱스

1. 탐색키의 중복 비율이 높은 컬럼은 대상으로 하는 질의를 효율적으로 처리하기위해 고안된 특수한 형태의 인덱스
2. 비트맵

• 간단한 비트의 배열
• 릴레이션 r의 속성 A에 대한 비트맵 인덱스는 A가 가질 수 있는 값에 대해 비트맵 구성
• 각 비트맵은 릴레이션에 있는 레코드의 수 n만큼 n개의 비트로 표현

구성

1. i번째 레코드가 컬럼 A에 해당 값을 가지면 비트맵이 i번쨰 비트를 1, 아니면 0
   

특징

1. 비트맵의 활동

• 컬럼에 대한 값의 범위가 유한하고 비교적 개수가 적은 규모일 떄 용이
• 적용 : 직책, 학과, 혈액형 등

2. 비트맵 인덱스의 크기

• 레코드의 크키가 수백 바이트 이상이 되어도 비트맵 인덱스에서는 하나의 비트로 표기
• 실제 릴레이션 크기에 비해 매우 작은 것이 장점