Linear Hashing

Search 25 and 44

현재 level=0이므로 마지막 두 binary만 본다. next pointer가 1이므로 bucket 0는 이미 split된 것이다. split된 bucket 0는 보라색으로 색칠된 곳에 있다. next가 가리키는 곳에 25가 있으므로 1 I/O가 든다.

44를 찾는다 생각하면, 일단 h0를 적용해서 마지막 두 숫자를 보면 00다. 그것은 next pointer보다 위에 있다. 그것은 그 bucket이 split된 것을 의미한다. 그러면 44가 원래 bucket에 있는지 split된 곳에 있는지 알 수 없다. 그것을 알기 위해 h1을 적용해야하고, 마지막 세 자리 숫자를 보게된다. 그러면 split 된 곳에 있다는 것을 알게된다. original에 없으면 split에 있는 것을 읽는 것이 아니다. 둘 중하나만 읽으니 1 I/O다.

Linaer Hashing (Conted.)

Inserting 43* (=101011)

N=4 는 현재 bucket의 수가 4라는 것을 의미한다. level0이므로 h0를 적용해서 마지막 두 자리를 본다. 11 bucket은 next 포인터 밑에 있다. 그래서 아직 split안됐다는 것을 알 수 있다. 하지만 11 bucket은 이미 꽉 찼다. 11 bucket을 split 하기 위해서 현재 next 0가 가리키고 있는 bucket부터 split한다. 그러고43*은 11 bucket의 overflow page에 저장한다. round robin 방식으로 진행하다보면 11 bucket도 split될 것이다.

Inserting 22, 29

위의 그림에서 next가 가리키는 01버킷은 스플릿 됐다. 그 다음은 enxt=2로 10을 가리키고 있다. 현재 level=0이므로 h0를 적용한다. 22는 10 버킷에 할당된다. overflow page에 할당된다. 29*는 마지막 자리가 01인데, 01 버킷은 스플릿 된 것을 알 수 있다. 왜냐하면 next 포인터보다 위에있기 때문이다. 29*의 마지막 세자리는 101이므로 101 버킷에 넣는다.

Inserting 34*, 38*, 42*, 46*

34, 38, 42의 마지막 두 자리는 10다. 그래서 3개다 overflow page에 넣는다. 하지만 46까지 넣어버리면 overflow의 overflow가 발생해서 split한다.

Inserting 50*

50의 마지막 두 자리 수는 10이다. 하지만 10은 next 포인터의 위이고, 50의 마지막 세 자리 수는 010이므로 010 버킷에 overflow 페이지에 들어간다. 기존의 4 bucket이 모두 split 되었으므로 한 사이클이 돌았다. 그러면 N=8이되고 level=1이된다.