방송대 데이터베이스시스템 - 11강. 해싱과 특수 인덱스

---

1. 정적 해싱

2. 동적 해싱

3. 비트맵 인덱스

---

1. 정적 해싱

해싱의 개념

해시(hash)/해싱(hasing)

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

마치 동물원에 영역을 구분하여 동물을 배치하는 것과 유사함.

· 정적 해싱(static hasing) : 저장 공간의 기본 단위인 버킷의 개수가 정해진 해싱 기법

· 동적 해싱(dynamic hashing) : 버킷의 개수가 데이터베이스의 크기에 따라 변하는 해싱 기법

 

버킷(bucket)

한 개 이상의 레코드를 저장할 수 있는 저장공간의 단위

크기는 일반적으로 디스크 블록의 크기와 일치 ('블럭' 대신 '버킷'이라는 용어 사용)

 

해시의 구조	해싱의 사용
K : 모든 탐색키 Ki의 집합 B : 모든 버킷 주소 Bi의 집합 해시함수(h) : K를 B에 대응(mapping)시키는 함수 탐색키 Ki를 갖는 레코드를 삽입하려면, 해시함수를 사용하여 h(Ki)를 계산해서 해당 레코드를 위한 버킷 주소를 구한 다음 레코드를 해당하는 버킷에 저장함.	탐색키 K3, K7을 갖는 서로 다른 두 레코드에 대해 해시함수가 동일하게 B3의 주소를 결괏값으로 반환하는 경우 → h(K3), h(K7)에 해당하는 버킷 B3에 두 레코드를 모두 저장 K7이 탐색키인 레코드는 버킷 B3에 있는 것을 알 수 있음. → B3 안에 있는 레코드 중 K7에 해당되는 탐색키에 해당되는 레코드를 찾아다가 결과를 제공해줄 수 있음.

---

해시 함수의 역할

	최상의 경우 · 모든 버킷에 레코드를 균등하게 저장할 수 있도록 해주는 것 · 해시 함수가 모든 입력 데이터에 대해 충돌이 없이 고유한 해시 값으로 변환되는 경우 · 해시 함수는 빠르게 입력 데이터를 해시 값으로 변환하고, 해시 테이블에서 바로 해당 위치에 데이터를 저장하거나 검색할 수 있음. · 최상의 경우에서 해시 함수의 시간 복잡도는 일반적으로 상수 시간에 가까움.
	최악의 경우 · 한쪽 버킷에만 쫙 몰려서 데이터가 저장되는 경우 · 해시 함수가 여러 입력 데이터가 동일한 해시 값으로 충돌하는 경우 · 해시 테이블에 데이터를 저장할 때 충돌이 발생하며, 충돌을 해결하기 위해 추가적인 작업이 필요함. · 가장 일반적인 충돌 해결 방법은 체이닝(Chaining)이며, 충돌이 발생한 위치에 연결 리스트를 이용하여 데이터를 저장함. ·최악의 경우에서 해시 함수의 시간 복잡도는 O(n)이 될 수 있음. (탐색키 수에 비례하여 검색 시간이 증가됨.)
	일반적인 경우 · 일반적인 입력 데이터에 대해 해시 함수가 어느 정도의 충돌을 가지고 있는 경우 · 충돌이 발생하면서도 충돌을 최소화하기 위한 해시 함수 설계가 필요함. · 평균 경우에서 해시 함수의 시간 복잡도는 일반적으로 상수 시간에 가깝지만, 충돌 해결을 위한 작업에 따라 추가적인 시간이 소요될 수 있음.

해시의 성능은 균등 배분되었을 때가 더 좋으므로 되도록 균등하게 배분해줄 수 있는 기능을 갖도록 설계되어어 함.
균등분배는 이론에서만 가능하므로 한 쪽으로만 몰리는 경우는 없도록 설계하는 경우가 일반적임.

---

파일 구조화 방법

파일 구조화 : 특정 레코드에 대한 접근을 위해 어떤 레코드가 어느 블럭에 저장되어야 하는지 관리하는 것

---

해시 파일 구조

해시 파일 구조 : 각각의 레코드가 어느 버킷, 즉 디스크 블록에 저장되어야 하는 건지 해시함수가 결정하도록 만들어진 구조

해시 인덱스 (X), 실제 레코드를 해시함수를 통해 저장하는 방식 (O)

---

정적 해싱

버킷의 개수가 고정된 해싱 기법

· 키 값이 Ki인 레코드 삽입

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

· 키 값이 Ki인 레코드 검색

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

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

 

충돌과 동거자

· 충돌 : 서로 다른 두 레코드가 동일한 버킷에 대응되도록 하는 결과가 만들어진 것, 동거자의 생성

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

출처 : 11강 강의록

레코드 ri와 rj가 모두 동일한 버킷 B1안에 대응되므로 충돌함.
ri와 rj의 관계를 '동거자'라고 함.

 

오버플로(overflow)

버킷에 레코드를 저장할 수 있는 여유 공간이 없는 상황에 발생

추가적인 버킷을 할당 또는 다음 버킷에 할당하여 처리

오버플로우가 발생할수록 접근시간이 길어지고 해시 성능이 저하

출처 : 11강 강의록

만약 탐색키 값이 K5라고 가정하면, 탐색키 값이 K5인 레코드 어딨는지 요청하면 해시함수가 B2라고 알려줌.
그럼 B2 버킷을 메모리로 올려서 그 안의 레코드 중 K5가 있는지 확인해야함.
만약 없으면 연결된 또다른 버킷을 메모리로 올려서 찾아봐야됨.
연결된 버킷이 5개라고 하면, K5 하나를 찾기 위해서 연결된 버킷 5개를 모두 조회해야하므로 디스크 I/O가 발생해서 성능이 저하됨. 
→ 오버플로 발생률이 얼마인지 따져보고, 오버플로가 발생되지 않는 형태의 해시함수를 사용해 볼 필요가 있음.

 

해시 인덱스

해시 파일 구조화의 동작 방식을 레코드가 아닌 인덱스 엔트리(탐색키와 포인터)에 적용한 인덱스

해시 함수는 '학번끝자리수 % 5'로 적용했으며, 탐색키를 해시 함수에 적용하고 그 결과 버킷(나머지 0부터 4까지)에 인덱스 엔트리를 저장함.

학번이 학생 파일의 기본키가 되므로 각 탐색키와 연관된 포인터는 단 한 개로만 구성됨.

· 다른 학생들 : 해시 함수에 학번을 순차적으로 적용하여 해당 학생 레코드에 인덱스 엔트리가 저장됨.

· 윤봉길, 정용호, 강신영 : 해시함수가 나타내는 버킷이 아닌 다음 버킷에 저장되어 탐색 시 다른 레코드에 비해 더 많은 시간 소요됨.

- 윤봉길 학생은 B0부터 연결된 B2에 있으므로 3번의 I/O를 발생시켜야 윤봉길 학생의 데이터에 접근을 하게 됨.

---

정적 해싱의 문제

데이터베이스의 크기가 커짐에 따라 오버플로우, 버킷 안 재검색 횟수가 증가하여 성능 감소

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

· 재구성 시 : 새롭게 선택된 해시 함수를 사용하여 모든 레코드에 대하여 다시 계산하고 버킷에 할당하는 대량의 비용이 발생

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

---

2. 동적 해싱

동적 해싱

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

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

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

 

확장성 해싱

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

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

· 헤더 : 디렉터리 깊이를 의미하는 정수값 d를 포함

· 포인터 : 디렉터리가 저장된 버킷에 대한 2^d개의 포인터

확장성 해싱에서 가장 중요한 것 : 디렉터리의 구조

 

모조키(pseudo key)

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

모조키의 첫 d 비트를 사용하여 디렉터리에 접근하여 해당 버킷의 위치를 알아낼 수 있음.

 

버킷 헤더

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

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

키 값이 k인 레코드를 해싱 파일에서 검색하기 위해 변환시킨 모조키가 101000010001이라고 가정함.

 

· 디렉터리의 깊이가 3

→ 모조키의 처음 3비트를 이용하여 디렉터리의 여섯 번째(101) 엔트리에 접근

→ 네 번째 버킷(키값 k를 가지고 있는 레코드가 저장)에 대한 포인터를 가지고 있음.

 

· 버킷 B4의 깊이(i)는 1

= 이 버킷에 저장되어 있는 모든 레코드 모조키의 처음 1비트가 모두 같음.

 

버킷 B4에 갔는데 모조키에 해당되는 인덱스 엔트리를 저장할 공간이 없음. (오버플로 발생)

정적해싱의 경우 오버플로가 발생하면 버킷의 개수를 바꾸지 못하기 때문에 그 다음 버킷에 삽입하든가 추가적인 버킷 연결을 해야하는데, 확장성 해싱은 버킷 개수를 새롭게 추가할 수 있음.

 

B4가 만원인 상태에서 모조키가 10으로 시작하는 레코드를 삽입하려고 함.

→ 해당 버킷이 분할됨.

→ 비어 있는 버킷을 할당 받아 모조키가 11로 시작되는 모든 레코드를 새로운 버킷으로 이동시킴.

→ 해당 버킷에 모조키가 10으로 시작하는 레코드를 삽입함.

→ 디렉터리 110과 111의 포인터값은 새로운 버킷을 지시하도록 변경됨.

→ 분할된 버킷의 깊이는 각각 2로 변경됨. (1에서 10, 11 → 숫자 두 자리를 봐야하니까)

 

즉, 버킷이 포화상태인 경우 디렉터리 깊이를 하나 증가시켜 디렉터리를 확장시킨 후 포인터가 적절히 조정됨.

 

이때 버킷 B1부터 B3까지는 어떤 영향도 받지 않음.
새롭게 버킷을 추가해도 조정되는 것은 디렉터리에 대한 부분과 포인터 부분, 그 다음에 버킷을 새롭게 추가해서 기존 버킷의 인덱스 엔트리가 양쪽으로 분할되어 저장된 부분만 영향을 받은 것임.

디렉토리는 항상 메모리에 적재되어 있어서 별도의 디렉토리 디스크 IO를 발생시키는 것도 아니며,
이 버킷에 대한 재조정 부분도 향후 어떤 오버플로를 발생시키지 않는 걸 감안한다고 하면 버킷 1개에 대한 재분배는 성능 저하에 영향을 미치지 않음.
→ 이러한 이유로 확장성 해싱은 굉장히 자주 사용되는 해싱 기법임.

---

3. 비트맵 인덱스

비트맵 인덱스

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

비트맵

- 간단한 비트의 배열

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

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

→ 컬럼값의 종류만큼 비트맵이 생성, 각 비트맵은 릴레이션의 레코드 수만큼 비트를 가짐.

 

비트맵 인덱스의 구성

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

 

성별이 남자이고 성적이 B인 학생의 정보를 출력

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

 

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

첫번째 레코드와 네 번째 레코드가 조건을 만족하는 레코드라는 것을 알 수 있음.

해당 레코드가 저장된 블럭들을 메모리에 적재시켜줌으로써 빠르게 결과를 제공할 수 있는 인덱스 역할을 수행할 수 있는 것

 

비트맵 인덱스의 특징

비트맵의 활용

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

종류가 가장 많은 기본키에 적용하면 성능이 저하될 수 있음

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

 

비트맵 인덱스의 크기

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

비트맵 인덱스의 전체 크기는 실제 릴레이션 크기에 비해 매우 작은 것이 장점