Tree-Structured index

인덱싱의 3가지 방법. 이전 노트 참고.

Tree-structured indexing은 범위를 만족하는 것을 찾는 것(range search)과 일치하는 것을 찾는 것(equality search), 둘 다 쓰일 수 있다. 
ISAM은 정적인 구조, B+ tree는 삽입, 삭제에 유연한 동적인 구조.

ISAM
leaf page가 data entries를 포함하고 있고, 오버플로우 페이지를 갖는다.
파일생성과정 : leaf pages가 연속적으로 할당되고, 서치키에 의해 정렬된다.  인덱스 페이지가 할당되고, 오버플로우 페이지를 위한 공간을 할당한다.
삭제시 overflow 페이지가 비게되면 할당 해제.
삽입과 삭제는 leaf page에만 영향을 미친다. non-leaf page는 안변한다.

B+tree
삽입, 삭제가 logF N이다. 트리의 높이 균형을 유지한다.
루트 빼고 페이지의 최소 적재률(50%)를 유지한다. 각 노드는 d<= m  <= 2d의 entry를 포함한다. d를 order라고 한다.
data entry에 삽입할 때 공간이 없으면 노드를 분할. 중간 값이 부모노드로 복사되어 새로 생긴 노드를 가리킨다.
하지만 index entry에 삽입할 때는 중간값이 복사되지 않고 이동된다.
split되면 높이가 하나 커진다.
삭제
삭제하고 나서  최소적재율보다 작으면 이웃노드에서 엔드리들을 가져오가나(re-distribute),이게 안되면 이웃노드랑 결합(merge)한다.
data entry가 merge될 때

merge하면 부모노드에서 합쳐져서 빈 노드를 가리키는 엔트리를 삭제한다.
merge가 루트까지 영향을 미칠 수가 있고 merge는 트리 높이를 작게 한다.

인덱스 엔트리가 merge될 때 

인덱스엔트리가 merge되면 합병되는 두번째 엔트리의 맨 왼쪽의 포인터는 키 값이 없게 된다. 그래서 부모 노드에서 빈 노드를 가리키게 될 인덱스 엔트리를 삭제하고 이 엔트리의 키 값을 사용한다.

인덱스 엔트리가 re-distribute될 때

그들의 부모를 거쳐서 재분배된다.

prefix key compression
fan-out이 클 수록, 트리의 높이가 작아지고 빨리 찾기 때문에 fan-out을 크게 하는 것이 좋다.
그래서 키를 압축해서 fan-out을 늘린다.

bulk loading of a B+ tree
큰 데이터로 b+ tree만들 때 삽입연산을 계속 해주면서 만드는 것은 느리다.
bulk loading 기법을 이용한다.
data entry를 모두 정렬하고, 새로운 루트 페이지에 첫번째 leaf page를 넣는다.
인덱스 엔트리는 항상 leaf page 바로 윗 레벨의 가장 오른쪽의 index page에 삽입된다.