[ADV_db]Chap 3. Hash index

---

# Static Hashing

---

Hashing

• 대부분 메인 메모리 내에 인덱스를 만들기 위해 사용되지만, 파일의 레코드를 정리할 때도 사용된다.
• 인덱스를 만들 때는 버켓에 레코드들의 인덱스들이 들어있지만, 파일을 관리할 때는 실제 레코드가 들어간다.
• Hash Index는 해시 함수를 통과해서 나오는 값을 Search key값으로 사용하는 방식이다.
  • Bucket이라는 디스크 블록에 같은 해시 값을 가지는 여러 엔트리가 저장되어 있다.
  • 만약 Bucket의 Index가 고정되어 있다면 Static Hashing 그렇지 않다면, Dynamic Hashing이라고 한다.
  • 다른 서치 키 값을 가지더라도 해시 함수를 통과했을 때 값이 같다면 같은 Bucket에 위치하기 때문에 어떤 엔트리를 검색하기 위해서는 해당 Bucket전체를 순차적으로 검색해야 한다.
  • 이 때 만약 Bucket의 사이즈보다 더 많은 엔트리가 해당 Bucket에 들어가야 한다면 문제가 발생한다.
    • 이런 문제는 해시 함수에서 분배가 잘 안되거나
    • 버켓 사이즈가 작아서 발생한다.
  • 이런 경우, 아래 그림처럼 Overflow Block을 통해 처리한다.

 

• 이런식으로 같은 해시 값을 가지는 Bucket의 Overflow Block들을 연결리스트로 연결하는 방식을 Overflow Chaining이라고 한다.
  • 이러한 방식을 Closed Addressing 또는 Closed Hashing이라고 부른다.
  • Open Hashing 이라고 불리는 방식은 개방형 방식으로 비어있는 공간에 두고 추가적인 해싱을 통해 구현하는데 잘 사용되지 않는다.
• Static Hasing의 경우 버킷의 사이즈가 너무 작으면 Overflow 블록이 많아져 처음보다 파일 크기가 점점 늘것이고, 그렇다고 넉넉하게 준비하면 낭비될 수 있다.
  • 따라서 더 좋은 방법은 Dynamic Hashing이다.
• 정렬된 Index와 Hashing 중에서 일반적으로 특정 레코드는 해싱이 더 빨리 처리되지만, 범위를 물어보는 쿼리가 많은 경우에는 정렬된 Index가 더 선호된다.