Extendible Hashing

Hash의 한 종류이다. 배열을 사용하여 hashed address를 저장한다. 크기는 2,4,6,8로 2의 제곱으로 커진다.

(a)는 hash의 그림이다. (b)와 (c)는 extendible hash의 그림으로 (b)는 각 노드의 값을 거치면서 bucket에 다다르는 그림이다. (c)는 (b)의 그림을 배열로 표현한 것이다. code는 (c)와 같이 구현한다.

배열이 directory이고, A, B, C, D가 bucket을 의미한다.

directory : bucket의 record address를 포함한 배열이다. 각 cello은 bucket record의 file address를 구성한다.

bucket의 기본적인 작동 방식은 index record와 유사하다. key를 bucket에 add하게 된다. search 시에는 key값으로 search하고 해당 주소를 return 한다.