해싱

# 정적 해싱
- 해시 파일 만들 때 버킷 수가 정적으로 결정 (static)
- 듬성듬성하게 채워짐
- 버킷은 연속, 그 안에 데이터는 연속되지 않음

# 정적 해싱 한계
- 해시 함수는 검색 키 값을 고정된 수의 버킷으로 매핑
- 데이터베이스는 성장, 축소함
- 성장하면 오버플로우 버킷 증가 -> 성능 저하
- 미리 공간 확보 -> 초기에 과도한 공간 수요 발생
- 축소하면 -> 공간 낭비
- 해결책 1 : 주기적으로 재구성(새로운 해시함수) -> 고비용, 재구성 중 연산처리 불가
- 해결책 2 : 버킷 개수를 동적으로 변화 -> 동적 해싱

 

# 해싱 
- 인덱스 구조를 액세스 하는 것을 피하게 해 줌

 

 

# 버킷 (bucket)
- 1개 이상의 레코드를 저장할 수 있는 저장 공간의 단위
- 저장 공간의 물리적 크기는 디스크 블록과 동일
- 파일에서 블록 : 증가됨에 따라 블록 단위로 파일이 증가
- 해시에서 버킷 : 처음부터 버킷 수 정해짐

 

# 해시 파일 구조
- 해시 함수를 통하여 직접 접근되는 버킷을 가지고 있음
- 주소 얻음

# 해시 인덱스 구조
- 검색 키들과 관련된 포인터들을 해시 파일 구조로 조직화할 수 있음

 

# 충돌 (collision)
- 서로 다른 검색키 값들이 동일한 주소를 가지는 버킷에 매핑시킬 수 있음
- 원하는 레코드를 접근하기 위하여 해당 버킷에 있는 모든 레코드들을 순차적으로 조사
- 조사는 메인 메모리가 하므로 성능적 문제없음
- 버킷이 넘치면 성능 저하

 

 

# 해시 함수 h
- 검색키 값 K를 입력으로 받아 주소 B를 가지는 버킷들로 매핑
- 레코드를 접근, 삽입, 삭제하는 데 사용
- h(k) = 정수(몇 번째)
- 검색에 대한 시행착오 없음
- 빠른 접근 속도(저장, 검색)
- 최악의 경우 : 모든 검색 키 값을 똑같은 버킷에 대응 (충돌)
- 일반적으로 검색 키 값의 이진 표현 결과에 대하여 계산 수행
- 신중한 디자인 요구함 : 잘 설계된 함수는 독립적인(적은) 상수의 평균 검색 시간 제공

 

# 해시 함수 조건 : 충돌이 최대한 적게 발생하도록
1. 균등(uniform)
- 각 버킷에 동일한 수의 검색 키 배정
2. 임의적(random)
- 각각의 버킷에 배정된 검색 키 값들이 서로 연관성이 없어야 함
- 알파벳 순이나 검색키 길이 등에서 규칙이 성립하지 않아야 함
- 어떤 형태의 검색 키 값이 들어와도 골고루 들어가야 함

 

# 버킷 오버플로우(Bucket Overflow) 발생 원인
1. 부족한 버킷 개수(insufficient buckets) : 파일 크기 작음
2. 일부 버킷으로 레코드 배정 몰림(치우침 skew)
- 많은 레코드가 동일한 검색 키 값 가짐(중복된 데이터 많음)
- 해시 함수가 검색 키를 균등하게 분배하지 않음

 

# 버킷 오버플로우 처리
- 오버플로우 버킷으로 처리
- 발생은 줄일 수 있어도 완전히 없애는 건 불가능
- 버킷의 개수를 (nr/fr)*(1+d(0.2))이 되도록 선택
1. 오버플로우 체인(overflow chaining)
- 오버플로우 버킷들을 연결 리스트 방식으로 구성
- 닫힌 해싱 방식(Closed Hashing)
- 검색 키 중복(몇 번째 주소에 모여있음)
- 처음부터 버킷 크기 작았을 때 사용

2. 열린 해싱(open hashing)
- 버킷의 집합이 고정, 오버플로우 버킷을 사용하지 않음
- 가득 차면 바로 밑 버킷에 넣음
- 선형 탐사(Linear Probing), 2차 해싱(Second Hashing) 등의 방식 적용
- 데이터베이스 시스템에서는 적용이 부적절
- 성능 상의 문제

 

# 해시 인덱스 (hash index)
- 인덱스 엔트리 (검색 키, 포인터)를 해시 파일 구조 안에 구성
- 2차 인덱스 (주 키 인덱스 구조로 요구되지 않음)