[DB] Hash

⚪Static Hashing

보통 Hashing이라고만 말하면 Static Hashing을 의미하는 것임

• bucket은 1개 이상의 엔트리를 포함하고, 보통 bucket 1개가 disk block 1개임
• h가 해시함수라 했을때 h(k1)=h(k2), k1≠k2면 k1과 k2는 동의어라함 (synonym)
  • 동의어가 발생할때 충돌(collison)이 발생했다고 함
• 해시 함수는 대표적으로 모듈러 함수를 이용해서 많이 함
  • h(k) = k mod 10 …이런식(버켓이 10개일 경우. 0~9번 버켓으로 분배해줌)
• 
  hash index에서는 bucket이 레코드에 대한 포인터를 갖는 엔트리를 저장하고 있음
• 
  hash file-organization에서는 bucket이 레코드 자체를 저장하고 있음

⚪Bucket Overflows

버켓이 불충분하거나, 레코드가 특정 값만 너무 많이 갖고 있다거나, 해시 함수가 균등히 분배를 못하는 등의 상황때 발생함.

overflow bucket을 완전히 막을순 없고 이를 적절히 다루는 방법이 있음

🔹Overflow chaining (closed addressing)

bucket이 overflow되면 위 그림처럼 링크를 걸어서 이어주는 기법

closed addressing 이라고도 불림

🔹Open addressing

보통 db에서는 사용되지 않는 방법인데, 오버플로우 체인처럼 추가 공간을 마련하지않고 기존 파일의 있는 공간을 최대한 활용하는 방법임.

여러가지 방법이 있긴함.

⚪Dynamic Hashing

static hashing을 사용하면,

삽입에 의한 오버플로우 체인이 생기는 단점으로 인해 검색 시간복잡도가 O(1)이라는 해시의 장점이 사라지게 된다

또는 처음부터 버킷의 크기를 너무 크게 잡아버리면 공간 낭비가 심해짐

따라서 이런점을 해결하기 위해 새로운 해시 함수를 사용해서 file을 주기적으로 아예 re-organization을 한다던가 (그러나 비용이 큼)

dynamically하게 buckets의 수를 조절하면 됨

대표적인 dynamic hashing 방법으로 Linear Hashing과 Extendable Hashing이 있는데 자세한 설명은 생략

🔹Linear Hashing

🔹Extendable Hashing