[Database] 해싱과 비트맵 인덱스

cateto·2022년 6월 5일
0

해싱과 비트맵 인덱스

해시(Hash)

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

버킷(Bucket)

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

해시의 성능은 레코드가 균등하게 배분되었을 때 성능이 높다.
균등 배분은 일반적으로는 이론적으로만 가능하고 한쪽으로 몰리는 경우만 없도록 설계해야한다.

해시 파일 구조

정적해싱

  1. 버킷의 개수가 고정된 해싱 기법
  2. 키 값이 KiKi인 레코드 삽입
  • 버킷 주소를 해시 함수로 생성하여 해당 버킷에 저장
  1. 키 값이 KiKi인 레코드 검색
  • 해시 함수로 주소를 생성하여 버킷에 저장된 레코드 접근

충돌과 동거자

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

Overflow

  • 충돌이 많아져서 동거자가 많아지게 되면 오버플로우가 발생한다.

해시 인덱스

정적 해싱의 문제점

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

동적해싱

  1. 동적 해싱의 정의
  • 버킷의 개수를 가변적으로 조절할 수 있는 해싱 기법
  • 데이터 베이스의 크기에 따라 버킷의 크기가 비례
  1. 데이터베이스의 증대 혹은 축소에 따른 인덱스의 구조를 조절하기 위해 해시함수를 동적 변경하는 기술
  2. 확장성 해싱
  • 동적 해싱의 일종으로 디렉터리와 버킷의 2단계 구조
  • 디렉터리는 디스크에 저장되는 버킷 주소 테이블
  • 디렉터리의 깊이는

확장성 해싱

  1. 모조키(pseudo key)
  • 레코드의 탐색키 값이 해시 함수에 의해 일정길이의 비트 스트링으로 변환된 키
  • 모조키의 첫 d 비트를 사용하여 디렉터리에 접근
  1. 버킷헤더
  • 정수값 (i<=d) 가 저장되어 있음을 표시
  • i는 버킷에 저장되어 있는 레코드의 모조키들이 처음부터 일치함을 표시

확장성 해싱의 구조

비트맵 인덱스

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

0개의 댓글