[DB]해싱과 특수 인덱스

📚해싱

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

• 버킷

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

• 해시의 구조
  

• 해시의 사용
  해시 함수에 K3과 K7을 넣으면 3이라는 값이 나옵니다. h(K3) = h(K7) = 3

• 해시 함수
  해시 함수는 탐색키를 이용하여 레코드를 배분하는 역할을 합니다. 모든 탐색키값이 같은 버킷에 대응되는 경우 모든 레코드가 한 버킷안에 유지되기 때문에 순차 탐색과 성능이 차이가 나지 않아 최악의 경우가 됩니다. 따라서 가능한 레코드가 균등하게 분배될 수 있도록 해시 함수를 설계할 필요가 있습니다.

📄정적 해싱

버킷의 개수가 고정된 해싱 기법입니다.

• 키 값이 Ki인 레코드 삽입

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

• 키 값이 Ki인 레코드 검색

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

• 충돌과 동거자

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

• 오버플로

레코드 삽입에서 충돌이 발생했을 때 버킷에 빈 공간이 없는 경우 오버플로가 발생합니다. 이때 별개의 오버플로 버킷을 연결하거나 해시 함수에 지정된 버킷의 다음 버킷에 저장할 수밖에 없습니다. 오버플로가 발생하여 버킷에서 검색하는 경우 추가적인 디스크 입출력이 유발되어 레코드의 접근 시간이 길어지고 해싱의 성능이 저하되는 문제가 생깁니다.

• 해시 인덱스

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

• 정적 해싱의 문제

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

📄동적 해싱

동적 해싱은 버킷의 개수를 가변적으로 조절할 수 있는 해싱 기법입니다. 데이터베이스의 크기에 따라 버킷의 크기가 비례합니다.

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

• 확장성 해싱

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

1. 모조키(pseudo key)
   레코드의 탐색키 값이 해시 함수에 의해 일정 길이의 비트 스트링으로 변환된 키입니다. 모조키의 첫 d 비트를 사용하여 디렉토리에 접근하는데 사용됩니다.

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

• 확장성 해싱의 구조

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

📚비트맵 인덱싱

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

비트맵 인덱스를 구성하기 위해 릴레이션에 있는 각각의 레코드에 정렬된 순서에 따라 0부터 시작해서 연속적으로 번호가 매겨집니다.

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

📄비트맵 인덱스 구성

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

📄비트맵 인덱스의 사용

📍성별이 남자이고 성적이 B인 학생의 정보를 출력하시오.

SELECT * FROM 학생
  WHERE 성별 = '남자' AND 성적 = 'B'

성별의 남자와 성적의 B의 비트열에 대한 비트 논리곱 연산을 수행합니다.

이 연산의 결과로 다음과 같은 비트맵이 생성되는데 이는 첫번째와 네번째 레코드가 조건에 만족하는 레코드라는 것을 의미합니다.

📄비트맵 인덱스의 특징

• 비트맵의 활용

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

• 비트맵 인덱스의 크기

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