데이터베이스 11강 :: 해싱, 정적 해싱, 동적 해싱, 비트맵 인덱스

데이터베이스 11강을 보며 배운내용

 

 

해싱이 뭐지?

탐색키의 산술적인 연산으로 버킷의 주소를 계산하는 것을 해싱이라고 한다

 

🤔 조금 더 쉽게

해시 함수가 탐색키 집합을 어떤 버킷에 저장될 지 알려준다

그러면 해시를 이용해서 버킷에서 데이터 찾을 수도 있겠지.

 

해싱을 통해서 버킷에 저장될 때,

균등하게 저장되면 좋지만, 보통 일정 버킷으로 몰린다고 한다

 

해시 함수

이런 해시 함수를 이용해서 버킷에 넣어줄 수 있다

h(k) = k % 6 

 

버킷(bucket)?

데이터를 저장하는 곳의 단위

 

 

정적 해싱

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

 

충돌과 동거자?

서로 다른 두 레코드가 동일한 버킷으로 가면 충돌,

이렇게 충돌난 레코드를 동거자라고 한다

=> 한 곳에 몰리면 오버플로우가 발생할 수 있다

 

오버플로우(overflow)?

버킷에 레코드 더 이상 저장공간이 없는 상황

추가적인 버킷 할당 또는 다음 버킷에 할당

오버플로우가 발생하면 접근시간이 길어져서 해시 성능이 저하된다.

 

🚩 정적 해싱 문제점

• 데이터베이스 크기가 커지면 버킷도 커지고,
  버킷이 커지면 버킷 내 재검색이 많아져서 성능 감소
• 데이터가 많을 것을 예상하고 미리 큰 공간을 잡아놓으면,
  초반에 상당한 공간이 낭비된다
• 데이터가 많아져서 재구성을 할 때,
  해시 함수로 모든 레코드를 다시 계산하고 버킷에 할당한다
  대량의 비용이 발생한다

 

👉 이런 문제로 동적 해싱 기법이 나왓다

 

 

동적 해싱

버킷의 개수를 가변적으로 조절 가능

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

 

데이터베이스 크기에 따라 인덱스 구조를 조절하기 위해,

해시 함수를 동적으로 변경하는 기술이 필요하다

 

🖖 동적 해싱의 대표주자 확장성 해싱

디렉터리를 통해 버킷에 접근한다

 

모조키(pseudo key)

탐색키 값을 해시 함수로 일정 길이의 비트 스트링으로 변환한 키

 

확장성 해싱 구조

디렉터리를 이용해서 버킷에 저장

 

확장성 해싱의 분할

오버플로우가 나오면 디렉터리를 분할해줄 수 있다

 

 

비트맵 인덱스

탐색키 중복이 많은 컬럼의 질의를 효율적으로 처리하기 위한 특수한 형태의 인덱스

 

비트맵?

간단한 비트의 배열

 

비트맵 생성 예시

해당 값이 있으면 1, 없으면 0

 

비트맵은 어디에 사용하나?

컴럼값이 범위가 유한하고, 비교적 개수가 적은 규모일 때

중복된 값이 많을 때 사용하면 좋다

예시) 직책, 학과, 혈액형

 

비트맵의 장점

비트맵 인덱스에서는 하나의 비트로 표시하다보니

레코드가 많아져도 크기가 작다

 

 

index by Maksym Kaharlytskyi @unsplash