All
해시(Hash)
•
탐색 키를 해시 함수를 통해 버킷 주소로 변환해 데이터를 빠르게 접근하는 기법
버킷(bucket)
•
한 개 이상의 레코드를 저장할수 있는 저장공간의 단위
•
일반적으로 버킷의 크기는 디스크 블록의 크기와 일치
해시 함수
h(k) = k % 6 과 같이 주어진 키 k에 대해 산술 연산을 수행하여 버킷 주소를 반환
해시의 구조
1.
해시 함수가 모든 키를 고르게 분산시킨 이상적인 경우
2.
해시 함수가 비효율적이거나 데이터가 쏠릴 경우, 하나의 버킷에 몰려 충돌이 발생하는 최악의 케이스
3.
현실에서는 적절한 수준의 충돌이 존재하는 형태
정적 해싱
•
버킷의 개수가 고정된 해싱 기법
•
키값이 인 레코드 삽입
◦
를 통해 에 대응하는 버킷 주소를 생성하고 레코드를 해당 버킷에 저장
•
키 값이 인 레코드 검색
◦
을 통해 버킷 주소를 생성하고 버킷에 저장된 레코드 접근
◦
인 경우가 발생하기 때문에 버킷 m에 저장된 모든 레코드 탐색하여 선택하는 과정 필요 (선형탐색)
충돌과 동거자(Collision & Synonym)
•
충돌 : 서로 다른 키가 동일한 버킷에 할당되는 현상
•
동거자: 충돌로 인해 같은 버킷에 저장된 서로 다른 레코드들
오버플로우(overflow)
•
버킷에 레코드를 저장할 수 있는 여유 공간이 없는 상황에 발생
•
버킷에 저장 공간이 부족할 경우 추가 버킷을 할당하는 방식
•
오버플로우가 잦아질수록 접근 시간이 증가하고 성능 저하 발생
해시 인덱스
•
해시 파일 구조의 동작 방식을 레코드가 아닌 인덱스 엔트리에 적용한 인덱스
•
특정 컬럼 값을 키로 사용해 해시 버킷을 구성하고, 버킷에는 해당 키를 가진 레코드의 포인터 목록이 저장
•
등가 조건(=) 검색에 매우 빠르지만 범위 조건(>, <, BETWEEN)에는 부적합 → 해시 함수를 통해 위치를 찾으니까 당연함
정적 해싱의 문제
•
데이터베이스 크기가 커짐에 따른 성능감소
•
사전에 큰 공간을 잡을 경우 초기에 상당한 양의 공간이 낭비
•
재구성 시 새롭게 정의된 해시함수를 사용해 모든 인덱스 엔트리에 대해 다시 계산하고 버킷에 재할당하는 대량의 비용이 발생
→ 해시 구조의 크기가 동적으로 결정되는 동적 해싱 기법 제안
동적 해싱
•
데이터 증가/감소에 따라 버킷 수를 동적으로 조절할 수 있는 해싱 기법
확장성 해싱
모조키(pseudo key)
•
해시 함수 h(k)를 통해 이진 비트 문자열로 변환된 값
•
모조키의 첫 d 비트를 사용하여 디렉터리에 접근
•
예:
k=7 → h(7) = 101110
버킷 헤더
•
디렉터리는 개의 포인터를 가지며 각 포인터는 버킷을 가리킴
•
버킷 헤더에 저장된 i값은 해당 버킷 내 모든 레코드가 처음 i비트까지는 동일함을 의미
확장성 해싱 구조와 분할
•
레코드 삽입에 의해 분할된 확장성 해싱 파일
비트맵 인덱스
•
탐색키의 중복 비율이 높은 컬럼을 대상으로 하는 질의를 효율적으로 처리하기 위한 특수한 형태의 인덱스
비트맵
•
간단한 비트의 배열
•
릴레이션 r의 속성 A에 대한 비트맵 인덱스는 A가 가질 수 있는 값에 대해 비트맵을 구성
•
각 비트맵은 릴레이션에 있는 레코드의 수 n개 만큼 n개의 비트로 표현
비트맵 인덱스 구성
•
i 번째 레코드가 컬럼 A에 해당 값을 가지면 비트맵의 i번째 비트를 1로, 아니면 0으로 설정
구조 예제
학번 | 성별 | 성적 |
1 | 남 | B |
2 | 여 | C |
3 | 여 | A |
4 | 남 | B |
5 | 여 | D |
6 | 남 | F |
성별 비트맵
•
남자 100101
•
여자 011010
성적 비트맵
•
A 001000
•
B 100100
•
C 010000
•
D 000010
•
F 000001
사용 예제
SELECT * FROM 학생
WHERE 성별='남자' AND 성적='B'
SQL
복사
성별 ‘남자’와 성적 ‘B’의 비트열에 대한 비트 논리곱 연산 수행
100101 & 100100 = 100100
→ 1번 , 4번 학생 선택됨
비트맵 인덱스의 장점
•
작은 저장 공간: 레코드가 크더라도 1비트만 사용
•
빠른 계산: AND, OR, NOT 같은 비트 연산으로 빠르게 조건 처리
•
다중 조건 처리에 유리 (특히 AND/OR 조합 질의)
•
적용: 직책 , 학과, 혈액형 등 카디널리티(고유값 개수) 가 적은 컬럼