[자료구조, 데이터베이스] 트리(Tree)

목차

1. B트리
1) 삽입
2) 삭제
3) 검색
4) 특성

2. B+ 트리
1) 삽입
2) 삭제
3) 검색
4) 특성

3. B*트리
1) m차 B* 트리의 속성
2) 3차 B*-트리에서 항목 삽입
3) 오버플로의 처리
4) 재분배

4. B 트리에서의 삽입과 삭제연산 알고리즘
1) m차 B트리에서 삽입 알고리즘
2) m차 B트리에서 삭제 알고리즘
3) 언더플로 처리 방법

5. B트리와 B+트리 삽입 알고리즘의 차이점

6. B트리와 B+트리 삭제 알고리즘의 차이점

7. B+트리 삽입 알고리즘

8. B+트리 삭제 알고리즘

본문내용

3. B*트리
<정의>: B* 트리
B* 트리는 키 항목이 명시적으로 트리와 리프노드에 포함되어 있는 B-트리의 변형으로 각 노드는 2/3 이상 채워지도록 함으로서 분열횟수를 줄이는데 목적이 있는 트리이다.

- 노드의 분열을 지연하여 연속적인 화일 액세스를 줄임
- 노드의 공간 이용 효율을 개선

1) m차 B* 트리의 속성
(1) 루트를 제외한 모든 노드의 서브트리 수는 m개를 초과할 수 없음
(2) 루트와 리프를 제외한 모든 노드는 적어도 (2m-2)/3 + 1개의 서브트리를 가짐
(3) 루트는 리프가 아닌 이상 최소 2개, 최대 2 (2m-2)/3 + 1개의 서브트리를 가짐
(4) 모든 리프는 같은 레벨에 있음
(5) 리프가 아닌 노드에 저장되는 키 수는 그 노드의 서브트리 수보다 하나 적으며, 최소 (2m-2)/3 , 최대 m-1개의 키를 가짐

2) 3차 B*-트리에서 항목 삽입
(1) B* 트리에서 삽입 연산은 B트리에서와 마찬가지로 항목을 삽입할 리프노드를 찾은 후 검색된 리프 노드에 삽입

참고자료

· 없음