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

해싱(Hasing)의 개념

해시(Hash)

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

아래 이미지와 같다고 생각하시면 됩니다.

여기서 버킷(Bucket)이란

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

해시의 구조

아래 이미지처럼 탐색키가 해시 함수를 거치면 어느 버킷에 저장되는지 정해지는 것

해시의 사용

그렇다면 어떻게 데이터를 꺼낼 수 있는가?

아래처럼 값을 입력하면 그에 상응하는 버킷을 알려줌

 

그렇다면 해시 함수의 역할은 자연스럽게, 여러 버킷에 균등하게 제공해야 한다, 만약 한 버킷에 모든 레코드를 저장하다면 해시의 성능이 확 떨어짐 => 실제 해시 인덱스에서는 완벽한 균등은 힘들다.

 

해시 파일 구조

파일 구조는 테이블의 레코드가 어느 디스크의 블록에 저장하지에 대한 구조를 의미하는데, 거기서 물리적 저장 위치를 해시 함수를 통해 결정하는 것을 의미함 => 해시 파일 구조화 작업

 

해싱의 종류

정적 해싱

정의

버킷의 개수가 고정된 해싱 기법으로 해시 인덱스를 사용 가능

 

특징

- 충돌 : 서로 다른 두 레코드가 동일한 버킷에 대응

- 동거자 : 충돌에 의해 같은 버킷 주소를 갖는 레코드

- 오버플로(overflow) : 꽉 차있는 버킷에 레코드를 저장되는 경우를 의미하고 추가적인 버킷 또는 다음 버킷에 처리하게 되며,  접근 시간이 길어지고 해시의 성능이 저하됨

- 해시 인덱스 : 해시 파일 구조와 동작 방식을 레코드가 아닌 인데스 엔트리에  적용한 것(원래는 버킷에 레코드를 저장하지 않고 인덱스 엔트리를 해시함수를 통해 버킷에 저장)

 

단점 

- 데이터베이스의 크기가 커짐에 따라 성능 감소

- 미리 큰 공간을 잡을 경우 초기에 상당한 양의 공간을 낭비

- 재구성 시 선택된 해시 함수를 사용하여 모든 레코드에 대하여 다시 계산하고 버킷에 할당해야 하므로 대량의 비용 발생

 

동적 해싱

정의

- 버킷의 개수를 가변적으로 조절할 수 있는 해싱 기법 (정적 해싱의 단점을 해결)

- 데이터베이스의 크기에 따라 버킷 크기 비례 (정적 해싱의 단점을 해결)

- 레코드 삽입시  그에 맞게 확장성 해시 파일을 나눔

 

동적 해싱의 대표적인 구조 : 확장성 해싱

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

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

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

 

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

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

아래 이미지에서 처럼 디렉터리와 모조키가 사용됨

디렉터리 표시 아래가 확장성 해시 파일들

비트맵 인덱스 해싱

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

=> 성별같이 값이 크게 안 나눠지는 값을 효율적인 처리하기 위해 고안된 인덱스다

 

비트맵이란?

- 간단한 비트의 배열

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

- 각 비트맵은 릴레이션에 있는 레코드의 수 n개만큼 n개의 비트로 표현 (i 번째 레코드가 컬럼에 A에 해당 값을 가지면 1번째 비트를 1, 아니면 0으로 )

즉 아래의 이미지와 같다

위 와 같이 비트맵을 가지고 sql문의 조건이 and일 경우 & 연산을 or 일 경우 | 연산을 하는 것이다 (각 열끼리 비트 연산을 한다)

=> 위와 같이 직책, 학과, 성별, 성적 등급, 혈액형 등 고정된(중복 비율이 높은) 값에 인덱스로 쓰이면 매우 빠른 속도를 보장해줌

=> 또한 각 레코드의 크기가 매우 크더라도 비트로 표시하므로 시간도 단축