[데이터베이스시스템] 해싱과 특수 인덱스

정적 해싱

해싱의 개념

1. 해시(hash)

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

탐색키 → <해시함수> → 버킷ID

1. 버킷(bucket)

→ 한 개 이상의 레코드를 저장 할 수 있는 저장 공간의 기본적인 단위

→ 크기는 일반적으로 디스크 블록의 크기와 일치

해시의 구조

강의내용중

해시의 사용

h(K3) = h(K7) = 3

강의내용중

해시 함수의 역할

여러개의 레코드와 여러개의 버킷이 있을 경우

최상의 경우

모든 버킷에 균등하게 위치 할 수 있게 나눠주는 경우

최악의 경우

한 버킷에 모든 레코드를 넣어주는 경우

일반적인 경우

여러 버킷 적당히 분배가 되는 경우 한쪽으로만 몰리지 않도록 해준다.

정적 해싱의 특징

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

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

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

→ h(Ki) 을 통하여 버킷 주소를 생성하고 버킷에 저장된 레코드 접근

→ h(Ki) = h(Kj) = m 인 경우가 발생하기 때문에 버킷 m에 저장된 모든 레코드를 탐색하여 선택하는

과정이 필요

충돌과 동거자

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

오버플로(overflow)

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

해시 인덱스

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

정적 해싱의 문제

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

→ 해시 구조의 크기가 동적으로 결정되는 동적 해싱 기법 제안

동적해싱

동적 해싱의 정의

→ 버킷의 개수를 가변적으로 조절할 수 있는 해싱 기법

→ 데이터베이스의 크기에 따라 버킷의 크기가 비례

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

확장성 해싱

→ 동적해싱의 일종으로 디렉터리와 버킷의 2단계 구조

→ 디렉터리는 디스크에 저장되는 버킷 주소 테이블

→ 디렉터리 깊이를 의미하는 정수 값 d를 포함하는 헤더와 데이터가 저장된 버킷에 대한 2d개의 포인터로 구성

모조키(pseudo key)

→ 레코드의 탐색키 값이 해시 함수에 의해 일정 길이의 비트 스트링으로 변환된 키

→ 모조키의 첫 d 비트를 사용하여 디렉터리에 접근

버킷 헤더

→ 정수 값 i(≤d) 가 저장되어 있음을 표시

→ i는 버킷에 저장되어 있는 레코드의 모조키들이 처음부터 i비트까지 일치함을 표시

확장성 해싱의 구조

• 디렉터리

header - 3

000
001
010
011
100
101
110
111

• 버킷 모조키 (시작비트스트링)

b1 - header 3 000

b2 - header 3 001

b3 - header 2 01

b4 - header 1 1

모조키가 101000010001 라면?

해시 함수를 붙여 모조키를 만들어 낸다 h(k3)

→ 디렉터리로 이동하여 버킷에 찾아간다. : b4 버킷으로 간다.

확장성 해싱의 분할

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

비트맵 인덱스

비트맵 인덱스의 개념

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

비트맵

→ 간단한 비트의 배열

→ 릴레이션 r의 속성 a에 대한 비트맵 인덱스는 a가 가질 수 있는 값에 대해 비트맵을 구성

→ 각 비트맵은 릴레이션에 있는 레코드의 수 n개 만큼 n개의 비트로 표현

비트맵 인덱스 구성

i번째 레코드가 컬럼 A에 해당 값을 가지면 비트맵의 i번째 비트를 1로, 그렇지 않으면 0으로 설정

비트맵 인덱스의 특징

• 비트맵의 활용

→ 컬럼에 대한 값의 범위가 유한하고 비교적 개수가 적은 규모일 때 용이

→ 적용 : 직책, 학과, 혈액형 등

• 비트맵 인덱스의 크기

→ 레코드의 크기가 수백 바이트 이상이 되어도 비트맵 인덱스에서는 하나의 비트로 표시

→ 실제 릴레이션 크기에 비해 매우 작은 것이 장점