[Indexing]Dynamic Hashing

bucket의 수가 처음부터 고정되있지 않는 방식이다. 우리가 배울 방식은 extendable hashing이다.

 

리턴 값은 32bit int이어서 400만 개 정도 된다. bucket의 수를 사용하는 prefix bit수를 조절하여 결정한다. 즉, 32비트 중에 맨 앞 비트부터 몇 개를 사용할지 선택한다. 

 

bucket address table이 필요하다. 이 테이블의 크기는 hash function의 prefix에 따라 결정된다. 

 

 

i는 사용하는 bit 개수이다. 

 

insertion

record는 key 값인 k를 가지고 있을 것이다. h(k)가 j라면 bucket j에 저장한다. bucket j가 full인 경우는 split을 한다. 

split 할 때 두가지 경우가 있다.

1) i > ij

bucket address table은 변경되지 않는다.

2)i = ij

bucket address table의 크기를 늘린다.

 

deletion 

h(k)을 통해 bucket을 찾는다. record가 있다면 삭제한다. 특정 조건에 따라 bucket address table이 줄어든다.

 

 

 

i=2라고 하면 앞에서 두 개의 비트만을 사용하는 것이다. 

 

example

 

초기 상태는 다음과 같다. bucket은 2개의 레코드를 저장할 수 있다고 가정한다.

 

 

 

insert "Mozart"

 

 

h(Mozart) 첫 비트가 0 이기 때문에 첫번째 버킷에 저장되었다. 

 

 

insert "Physics"

 

h(physics)의 첫 비트가 1이기 때문에 두번째 버킷에 저장되어야 한다. 다 차있으므로 split한다. 처음 비트가 1인 데이터에서 구분을 해야하므로 비트 하나를 더 써야한다. 따라서, 두 번째, 세 번째 버킷을 구분하기 위해서 비트가 두 개 필요하게 되므로 두 번째 버킷과 세 번째 버킷의 i값을 2로 바꾼다. bucket address table도 커져야하므로 hash prefix개수인 i도 2로 바뀌었다. 

 

insert "Finance"

 이전 버킷 상태에서 두 번째 버킷에 Wu가 들어가야 하므로 split을 진행한다. 비트를 10만 쓰는 것으로는 부족하기 때문에 100, 101을 사용해야 한다. 따라서,  split 되어서 생성된 두 개의 버킷은 i=3으로 둔다. 따라서 hash prefix 개수도 3개로 늘린다. 

 

insert "Comp. Sci."

 

Insert "Comp. Csi."

Comp Sci는 비트 끼리는 더 써도 prefix가 같다. 따라서 split을 할 수 없기 때문에 overflow bucket을 만들게 된다.

 

Insert "Elec Eng"

 

address table에서 i = 3 이고 bucket의 i값에 따라 현재 prefix 값은 다음과 같다.

00

00

01

01

-----

100

101

110

111

 

위의 네 개의 address가 2개의 비트만을 사용하고 있으므로 두 개만을 표현했다. 실제적인 구현은 다를 수 있다.

 

Extendable hashing

장점

bucket의 수를 조절할 수 있기 때문에 파일의 사이즈 변화에 유연하다. overflow bucket이 생길 가능성이 적다. 쓰지 않는 버킷을 최소화 한다.

 

단점

bucket address table을 통해서 record를 참조하기 때문에 추가적인 비용이 든다.

bucket address table이 매우 커지면 메모리에 저장할 수 없고 디스크에 저장해야 할 수 있다. disk io가 발생할 수 있다.

table이 재수정되는 비용이 든다. 

 

-->linear hashing이 대안이 된다.

 

db system에서 사용할 기법을 결정할 때의 기준

1. cost of periodic re-organization: 구조를 재구성 할 때의 비용을 고려해야 한다.

2. cost of insert and delete: 삽입과 삭제에 대한 비용을 생각해봐야 한다.

3. average access time, worst-case access time : 질의에 대한 처리 시간을 고려해보아야한다.

4. expected type of querys: range 같은 질의를 많이 쓴다면 ordered indexing이 좋을 것. range기법은 hashing 기법을 통해서 사용하면 불리함. 왜냐하면 hashing을 썼을 때 key에 대해서 정렬되어 있지 않기 때문이다.