B-트리 동작 실제 사이트

http://slady.net/java/bt/view.php?w=800&h=600

*검색

- 직접탐색 : 키 값에 의존한 분기

- 순차탐색 : 중위순회(Inorder traversal), 성능저하

*삽입

- 여유공간이 있을 경우 : 단순히 순서에 맞게 삽입

- 여유공간이 없을 경우 : Overflow발생, split 작업(높이 증가)

①해당 노드를 두개의 노드로 분할

②해당 노드의 키 값에 새로운 키 값을 삽입했다고 가정

③중간 키 값을 중심으로 큰 키들은 새로운 노드에 저장

④중간키값 은 분할된 노드의 부모 노드로 올라가서 삽입

⑤이 때, 다시 Overflow 발생 시 위와 같은 분할(split) 작업 반복

*삭제

- 삭제될 키 값이 내부노드에 있는 경우

①해당 키의 후행키 값과 교환 후 리프 노드에서 삭제

②리프노드에서의 삭제 연산 간단

③후행키값 대신 선행키값을 사용 가능

- 최소 키값 수(m/2-1)보다 작은 경우 : underflow

-재분배(redistribution)

Ø 최소키 값보다 많은 키를 가진 형제 노드에서 차출

Ø 부모 노드에 있던 키 값을 해당 노드로 이동, 빈자리에 차출된 형제 노드의 키값을 이동

Ø 트리 구조를 변경시키지 않음

-합병(merge)

Ø 재분배가 불가능한 경우에 적용

Ø 형제 노드와 합치하는 방법으로 합병 결과 빈 노드 제거

트리구조가 변경됨