[DB] CH11. 해싱(Hashing)

 

Hash file organization

• record를 위치시킬 bucket을 hash function을 통해 구한다.
• hash function : search key value(K)를 bucket address(B)로 매칭시켜주는 함수(h : K->B)

이상적인 hash function

• 서로 다른 search key value가 같은 bucket에 mapping될 수 있다. 하지만 이러한 collision이 많아지면 성능 저하로 이어진다. 이상적인 해시 함수의 조건은 다음과 같다.
  • uniform - 모든 bucket에 uniform하게 record를 분포시키는 것(uniform distribution)
  • random - 실제 file의 search key value의 분포에 무관하게 모든 bucket에 동일한 record 할당

Bucket overflow

• bucket에 더 이상 record를 저장할 공간이 없는 경우를 말함
• 일반적으로 bucket overflow는 다음의 두가지 요인으로 발생한다.
  • 애초에 bucket이 충분하지 않았던 경우
  • records의 분포가 균등하지 않은 경우

Record의 분포가 균등하지 않은 경우 원인은 무엇인가?

• 몇몇 records들이 동일한 search key value를 갖는 것이 원인일 수 있다.
• 혹은 사용한 해시 함수가 non-uniform distribution을 만들어낼 수 있다.

Bucket overflow handling

• Chaining(Closed hashing) : 일반적으로 DB에서 사용
• Open hashing : DB에선 deletion도 빈번하게 일어나므로 not suitable

Hash indices(해시 인덱스)

• 해싱은 file organization뿐만 아니라, index structure를 만드는 데에도 쓰인다.

해시 인덱스 예시

Static Hashing의 단점

• DB의 grow, shrink에 대응하기 어렵다. - 그래서 데이터 갯수를 이미 알고 있는 경우에 사용
• grow -> overflow로 인해 성능 저하
• shrink -> 메모리 공간 낭비(Space overhead)
• 그래서 해결책으로 나온 것이 dynamic hashing

Static Hashing vs. Dynamic Hashing

• Static Hashing : bucket 개수가 고정되어 있는 hashing
• Dynamic Hashing : bucket이 동적으로 할당되어 bucket 개수가 가변적인 hashing EX)Extendible hashing

Extendible Hashing의 장단점

• 장점
  • DB의 데이터 증가에 잘 대응
  • space overhead를 줄일 수 있다.(Minimal space overhead)
• 단점
  • 해당 record를 찾기 위해 추가적인 indirection 단계를 거치게 된다.
  • bucket address table이 매우 커질 수 있다.
  • bucket address table의 사이즈를 변경하는 cost가 든다.