[Indexing]Static Hashing

hash table의 크기가 처음부터 고정되어 있는 것을 static hashing이라고 한다. 크기가 고정되어 있기 때문에 약점이 존재한다.

 

hash file organization

bucket: 여러 개의 record를 저장한다. bucket크기는 disk block로 사용할 수 있다.

여러 개의 버킷 중에서 버킷의 선택 기준은 hash function이 된다. record의 key 값을 hash function에 넣으면 버킷을 골라준다. 레코드를 추가할 때 뿐 아니라 search시에도 hash function을 사용한다. hash function의 input은 key 값이고 output은 bucket address이다. 다른 키여도 같은 output을 낼 수 있다.

 

deptname이 key이고 h(Music)= 1이다. 

 

hash function

worst hash function은 모든 key가 같은 bucket인 경우이다. best한 경우는 모두 균일하게 bucket에 할당하는 것이다. 

 

bucket overflow

bucket 크기가 고정되어 있기 때문에 발생하는 문제이다. 원인은 bucket 크기가 너무 작은 경우나 hashing function을 잘못 만들어서 특정한 bucket에 집중되는 경우이다. 또한, 특정한 키가 많이 존재하는 경우도 있다. 

해결책으로 새로운 bucket을 만들어서 link를 해주는 방법이 있다. 

 

hash file

bucket i 가 full 이 되면 bucket을 하나 추가한다. 이런 기법은 closed hashing이라고 한다.

 

open hashing은 추가 bucket 없이 사용하는 방법이다. full이 발생하면 linear programming이나 double hashing을 사용한다. linear programming은 bucket이 full이 되면 다음 bucket에 저장한다. 이렇게 되면 검색시 다음 bucket까지 검색해야 한다.

double hashing은 2개의 hash function을 두고 h1(k)의 bucket이 full이면 h2(k)의 bucket에 저장한다. 검색할 때도 h1으로 하고 없으면 h2로 검색하게 된다.

 

bucket에 record들이 전부 저장되어 있고 key에 대한 검색으로 해당 버킷을 찾아가는 방식에 대해 살펴보았다. 이 때 이 bucket들의 모음을 hashfile이라고 한다.

 

hash index

hash index를 사용할 수도 있는데 이 구조에서는 hash index에는 (key, address)를 저장하고 record는 별도로 저장하는 방식이다. hash index는 secondary index이다.

 

bucket에는 key와 address를 가지고 있다. 즉, hash index이다.

 

deficiencies of static function

db는 사용하면서 크기가 변할 수 있다. 크기가 커지면 overflow가 발생하고 크기가 작아지면 underflow가 발생한다. overflow시에 관리가 쉽지 않아지고 underflow가 발생하면 낭비가 생긴다. 관리를 위해 주기적으로 구조를 바꾸는 것은 비용이 많이 발생한다. 

 

따라서, dynamic hashing을 사용한다.