Hash-based indexes

hash-based indexes는 equality selection에 가장 좋은 인덱스.
range search는 성능이 아주 않좋아 사용하지 않는다.

static hash
primary bucket pages가 고정, 연속적으로 할당되어 있다. 절대 해제되지 않고, 필요하면 오버플로우 페이지를 만든다.
hash값으로 data entry가 들어갈 버켓을 정한다.

dynamic hashing
extensible hashing, linear hashing

extensible hashing
버켓을 가리키는 디렉토리를 사용한다.
버켓이 가득차면 디렉토리 크기를 2배로 하고, 오버플로우 된 버켓에 있는 데이터엔트리들을 분산시킨다.
하지만 버켓이 가득찬다고 해서 항상 디렉토리 크기가 2배가 되는 것이 아니다.
오버플로우된 버켓의 데이터엔트리가 분산될 때, global depth, local depth를 비교해서 local depth가 커질경우 디렉토리 크기를 2배로 늘리고, global depth도 1 커진다.
global depth는 엔트리가 어떤 버켓에 속할지 구분할 때 필요한 최대 bit의 갯수이다.
local depth는 이 버켓에 속한 엔트리들을 구분하는데 이용되는 bit수이다.
최소유효비트로 구별하는 것의 좋은 점 : 디렉토리가 2배가 될때 그냥 이전 디렉토리를 복사하고, 분산되는 버켓부분의 포인터만 수정해준다.
데이터 엔트리를 삭제할 때, bucket이 비면 합칠 수 있다. 그리고 모든 directory element가 분산되기 전처럼 같은 bucket을  가리키면 디렉토리가 반으로 줄어든다.

linear hashing
여러개의 hash function을 이용.
hi+1 은 hi의 해시값 범위의 두배이다.
overflow page를 사용한다.
나눌 버켓을 round-robin으로 차례대로 정한다.
한 라운드의 버켓의 수는 라운드 시작할 때 존재하는 버켓의 수(NR)이다.
각 라운드를 level이라고 한다.
한 라운드를 끝내면 버켓의 수는 시작할 때보다 2배가 되며(점진적으로 증가)
level이 하나 증가하고, 해쉬함수도 다음 것을 사용한다.
나눠지는 시점을 적재률로도 할 수 있고, 아니면 오버플로우 될 때로 할 수 있다.
찾기 할 때 해쉬값이 이전에 나눠진 버켓을 가리킬 때에는 다음 단계 해쉬값을 사용한다.
입력할 때 level 또는 level+1의 해시함수의 값을 통해 버켓을 찾고 버켓이 가득 찼을 경우 오버플로우 페이지가 생기고,
나눠지는 시점을 오버플로우가 발생될 때로 했다면, 이번 차례의 버켓을 level+1의 해쉬함수를 이용하여 엔트리들을 분할 한다.