해싱과 특수 인덱스

정적 해싱

해시(hash)

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

버킷(bucket)

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

충돌과 동거자

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

오버플로우(overflow)

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

해시 인덱스

인덱스 엔트리를 해시함수를 사용하여 버킷에 저장하는 형태

정적 해싱의 문제

• 데이터베이스의 크기가 커짐에 따른 성능 감소
• 미리 큰 공간을 잡을 경우 초기에 상당한 양의 공간이 낭비

동적 해싱

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

확장성 해싱

• 동적 해싱의 일종으로 디렉터리와 버킷의 2단계 구조
• 디렉터리는 디스크에 저장되는 버킷 주소 테이블
• 디렉터리 깊이를 의미하는 정수값 d를 포함하는 헤더와 데이터가 저장된 버킷에 대한 2^d개의 포인터로 구성
• 레코드 삽입에 의해 버킷이 꽉 찰 경우 오버플로우가 발생하지 않도록 버킷을 분할함

모조키(pseudo key)

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

버킷 헤더

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

비트맵 인덱스

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

비트맵

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

비트맵 인덱스의 구성

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

비트맵 인덱스의 사용

sql문의 where 절에서 조건이 and 연산이라면 비트맵끼리 and연산하면 됨
마찬가지로 or 연산이라면 비트맵끼리 or 연산!

비트맵의 활용

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

비트맵 인덱스의 크기

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