List
Search
1. 정적 해싱
1.1. 해싱의 개념
•
해시
◦
해시 함수
▪
탐색키에 연산을 통해 버킷 주소를 연산
▪
하나의 버킷에 몰리는 경우(핫스팟) 지양 해야함. 균등분배를 위한 알고리즘 설계 필요
◦
해시 함수를 사용하여 데이터 배분 및 접근
•
버킷
◦
한개 이상의 레코드를 저장할 수 있는 저장 공간 단위
◦
일반적으로 디스크 블록 크기와 일치
1.2. 해시의 구조 및 사용
•
해시의 구조
•
해시의 사용
◦
h(k3) = h(k7) = 3
•
해시 파일 구조
◦
예시)
1.3. 정적 해싱
•
버킷의 개수가 고정된 해싱 기법
•
키 값인 Ki인 레코드 삽입
◦
h(Ki)를 통하여 Ki에 대응하는 버킷 주소를 생성하고 레코드를 해당 버킷에 저장
•
키 값인 Ki 레코드 검색
◦
h(Ki)를 통해 버킷 주소 생성 후 버킷에 저장된 레코드 접근
◦
h(Ki) = h(Kj) = m 인 경우가 발생하기 때문에 버킷 m에 저장된 모든 레코드 탐색하여 선택 과정 필요
1.4. 충돌과 동거자
•
충돌
◦
서로 다른 두 레코드가 동일한 버킷에 대응
•
동거자
◦
충돌에 의해 같은 버킷 주소를 갖는 레코드
•
오버플로우
◦
버킷에 레코드를 저장할 수 있는 여유 공간이 없는 경우에 발생
◦
추가적인 버킷을 할당 또는 다음 버킷에 할당하여 처리
◦
오버 플로우가 발생할수록 접근 기간이 길어지고 해시 성능 저하
1.5. 해시 인덱스
•
해시 파일 구조와 동작 방식을 레코드가 아닌 인덱스 엔트리에 적용한 인덱스
◦
예시)
•
해시 인덱스에도 동일하게 오버 플로우 발생 가능
◦
버킷에 여유 공간이 없어서 다음 버킷에 할당하여 처리
1.6. 정적 해싱의 문제
•
데이터베이스 크기가 커짐에 따라 성능 감소
•
미리 큰 공간을 잡을 경우 초기에 상당한 양의 공간 낭비
•
재구성시 새롭게 선택된 해시 함수 사용할 경우 모든 레코드에 대하여 재정의 필요 → 대량 비용 발생
→ 해시 구조의 크기가 동적으로 결정되는 동적 해싱 기법 제안
2. 동적 해싱
2.1. 동적 해싱의 개념
•
동적 해싱
◦
버킷의 개수를 가변적으로 조절 가능한 해싱 기법
◦
데이터베이스의 크기에 따라 버킷의 크기가 비례
•
데이터베이스의 증대/축소에 따른 인덱스의 구조를 조절하기 위해 해시 함수 동적 변경 기술
•
확장성 해싱
◦
동적 해싱의 일종으로 디렉토리와 버킷의 2단계 구조
◦
디렉토리는 디스크에 저장되는 버킷 주소 테이블
◦
구성
▪
헤더 - 디렉토리 깊이를 의미하는 정수값 d를 포함
▪
포인터 - 데이터가 저장된 버킷에 대한 2^d개
2.2. 확장성 해싱
•
모조키 (pseudo key)
◦
레코드 탐색키 값이 해시 함수에 의해 일정 길이의 비트 스트링으로 변환된 키
◦
모조키 첫 d 비트를 사용하여 디렉토리에 접근
•
버킷 헤더
◦
정수값 i (≤d)가 저장되어 있음을 표시
◦
i는 버킷에 저장되어 있는 레코드의 모조키들이 처음부터 i비트까지 일치함을 표시
2.3. 확장성 해싱의 구조
•
예시
2.4. 확장성 해싱의 분할
•
레코드 삽입에 의해 분할된 확장성 해싱 파일
3. 비트맵 인덱스
3.1. 비트맵 인덱스의 개념
•
탐색키의 중복 비율이 높은 컬럼을 대상으로 질의를 효율적으로 처리하기 위한 특수 인덱스
◦
카디널리티가 낮은 컬럼의 레코드에 대한 인덱스
•
비트맵
◦
간단한 비트의 배열 (예. 010111)
◦
릴레이션 r의 속성 A에 대한 비트맵 인덱스는 A가 가질 수 있는 값에 대한 비트맵 구성
◦
각 비트맵은 릴레티션에 있는 레코드 수 n개 만큼 n개의 비트로 표현
3.2. 비트맵 인덱스의 구성
•
i번째 레코드가 컬럼 A에 해당 값을 가지면 비트맵의 i 번째 비트를 1로, 그렇지 않으면 0으로 설정
•
특정 컬럼이 가질 수있는 값의 개수(카디널리티 수) 만큼 비트맵 생성
•
예시 1)
•
예시 2)
3.3. 비트맵 인덱스의 사용
1.
성별이 남자이고 성적이 B인 학생의 정보 출력
SELECT * FROM 학생 WHERE 성별='남자' AND 성적='B'
SQL
복사
2.
성별의 남자 와 성적의 B 의 비트열에 대한 논리곱 연산 수행
•
성별 비트맵
•
성적 비트맵
•
논리곱 연산
3.
결과 확인
•
첫번째와 네번째 레코드가 조건을 만족하는 것을 알 수 있음
3.3. 비트맵 인덱스의 특징
•
비트맵의 활용
◦
컬럼에 대한 값의 범위가 유한하고 비교적 개수가 적은 규모일때 용이
◦
예) 성별, 학과, 혈액형 등 카디널리티가 적은 레코드
•
비트맵 인덱스의 크기
◦
레코드의 크기는 수백바이트 이상이 되어도 비트맵 인덱스에서는 하나의 비트로 표시
◦
실제 릴레이션 크기에 비해 매우 작은 것이 장점