12강. 해싱과 특수 인덱스

1. 해싱의 개념

• 해시( hash )
  • 탐색키에 산술적인 연산을 통해 버킷의 주소를 계산하는 해시 함수를 사용하여 데이터를 배분 및 접근하는 기법
• 버킷( bucket )
  • 한 개 이상의 레코드를 저장할 수 있는 저장공간의 단위
  • 일반적으로 버킷의 크기는 디스크 블록의 크기와 일치

2. 해시의 구조

• 레코드 탐색키의 집합( K ) 내의 레코드를 해시 함수( h )에 입력하면, 해시 함수의 결과값( 출력 )이 특정 버킷( B ) 을 가리킴
• 해시 함수(h)
  • 탐색키 K를 입력받아 해시 연산 수행
  • 결과값에 따라 여러 개의 버킷 중 하나를 선택하여 저장 또는 검색
• 버킷(B₁ ~ Bₙ)
  • 해시 함수 결과에 따라 선택되는 저장 공간
  • 각 버킷은 하나 이상의 레코드를 저장 가능

3. 정적 해싱의 특징

• 버킷의 개수가 고정된 해싱 기법
• 키 값이 Kᵢ인 레코드 삽입
  • h(Kᵢ)를 통해 Kᵢ에 대응하는 버킷 주소를 생성하고 레코드를 해당 버킷에 저장
• 키 값이 Kᵢ인 레코드 검색
  • h(Kᵢ)를 통해 버킷 주소를 생성하고 버킷에 저장된 레코드에 접근
  • h(Kᵢ) = h(Kⱼ) = m인 경우가 발생하기 때문에 버킷 m에 저장된 모든 레코드를 탐색하여 선택하는 과정이 필요

4. 충돌과 동거자

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

5. 오버플로우( overflow )

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

6. 해시 인덱스

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

7. 정적 해싱의 문제

• 데이터베이스의 크기가 커짐에 따른 성능 감소
• 사전에 큰 공간을 잡을 경우 초기에는 상당한 양의 공간이 낭비
• 재구성 시 새롭게 정의된 해시 함수를 사용하여 모든 인덱스 엔트리에 대해 다시 계산하고 버킷에 재할당하는 대량의 비용이 발생
• 해결 방안 제안
  • 해시 구조의 크기가 동적으로 결정되는 동적 해싱 기법 제안

8. 동적 해싱의 개념

• 동적 해싱의 정의
  • 버킷의 개수를 가변적으로 조절할 수 있는 해싱 기법
  • 데이터베이스의 크기에 따라 버킷의 크기가 비례
• 데이터베이스의 증대 혹은 축소에 따른 인덱스의 구조를 조절하기 위해 해시 함수를 동적 변경하는 기법
• 확장성 해싱
  • 동적 해싱의 일종으로 디렉터리와 버킷의 2단계 구조
  • 디렉터리는 디스크에 저장되는 버킷 주소 테이블
  • 디렉터리 깊이를 의미하는 정수값 d를 포함하는 헤더와, 데이터가 저장된 버킷에 대한 2ᵈ개의 포인터로 구성

9. 확장성 해싱

• 모조키( pseudo key )
  • 레코드의 탐색키 값이 해시 함수에 의해 일정 길이의 비트 스트링으로 변환된 키
  • 모조키의 첫 d 비트를 사용하여 디렉터리에 접근
• 버킷 헤더
  • 정수값 i (≤ d) 가 저장되어 있음을 표시
  • i는 버킷에 저장되어 있는 레코드의 모조키들이 처음부터 i 비트까지 일치함을 표시

10. 확장성 해싱의 구조

• 디렉터리는 비트 문자열( ex. 3비트 )로 구성되며, 각 디렉터리는 버킷을 가리킨다.
• 디렉터리의 각 엔트리는 모조키의 앞 비트들과 매칭되어 해당 버킷으로 연결됨
• 각 버킷은 시작 비트 문자열에 따라 구분되며, 버킷마다 해시 깊이가 존재함
• 예시:
  • B₁: 시작 비트 문자열 000, 깊이 3
  • B₂: 시작 비트 문자열 001, 깊이 3
  • B₃: 시작 비트 문자열 01, 깊이 2
  • B₄: 시작 비트 문자열 1, 깊이 1

11. 확장성 해싱의 분할

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

12. 비트맵 인덱스의 개념

• 탐색키의 중복 비율이 높은 컬럼을 대상으로 하는 질의를 효율적으로 처리하기 위해 고안된 특수한 형태의 인덱스
• 비트맵
  • 간단한 비트의 배열
  • 릴레이션 r의 속성 A에 대한 비트맵 인덱스는 A가 가질 수 있는 값에 대해 비트맵을 구성
  • 각 비트맵은 릴레이션에 있는 레코드의 수 n개 만큼의 비트로 표현

13. 비트맵 인덱스 구성

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

14. 비트맵 인덱스의 사용

• 성별이 남자이고 성적이 B인 학생의 정보를 출력
  • SELECT * FROM 학생 WHERE 성별 = '남자' AND 성적 = 'B'
• 성별 '남자'와 성적 'B'의 비트열에 대한 비트 논리곱 연산을 수행
  • 100101 * 100100 = 100100

15. 비트맵 인덱스의 특징

• 비트맵의 활용
  • 컬럼에 대한 값의 범위가 유한하고 비교적 개수가 적은 규모일 때 유용
  • 적용 : 직책, 학과, 혈액형 등
• 비트맵 인덱스의 크기
  • 레코드의 크기가 수백 바이트 이상이 되어도 비트맵 인덱스에서는 하나의 비트로 표시
  • 실제 릴레이션 크기에 비해 매우 작은 것이 장점
• 단점
  • 기본키 또는 UNIQUE 제약이 있는 키에 비트맵 인덱스를 적용할 경우, 인덱스의 크기가 굉장히 커질 수 있음