분야
pptB-트리
균형 m-원 탐색 트리
차수 m인 B-트리의 특성 (m-원 탐색트리)
① 루트와 리프를 제외한 노드의 서브트리 수
m/2 ≤ 개수 ≤ m
② 루트는 리프가 아닌 이상 적어도 두 개의 서브트리를 갖는다.
③ 모든 리프는 같은 레벨에 있다.
④ 키값의 수
리프 : m/2 - 1 ~ (m-1)
리프가 아닌 노드 : 서브트리수 - 1
⑤ 한 노드 내의 키 값들은 오름차순을 유지함.
▶ B-트리 구조
노드 구조
Ki → (Ki, Ai)
n
P1
K1
P2
K2
P3
…
Pn-1
Kn-1
Pn
* 차수 3인 B-트리 구조
▶ B-트리 연산
연산
직접 탐색 - 키 값에 의존한 분기
순차 탐색 - 중위 순회
삽입, 삭제 - 트리의 균형 유지
분할 → 높이 증가
합병 → 높이 감소
삽입
(a) 노드 l에 22 삽입
▶ B-트리 삽입
(b) 노드 n에 41 삽입
(c) 노드 o에 59 삽입