[공학]B트리 구현

소개글

1. 차수(order)가 m인 B-트리의 특성
2. 노드 구조
3. B-트리의 장점
4. 3차 B-트리 구조
5. 삽입 알고리즘의 이해
6. 소스
7. 실험 결과
8. 느낀 점

목차

1. 차수(order)가 m인 B-트리의 특성
2. 노드 구조
3. B-트리의 장점
4. 3차 B-트리 구조
5. 삽입 알고리즘의 이해
6. 소스
7. 실험 결과
8. 느낀 점

본문내용

1. 차수(order)가 m인 B-트리의 특성
① B-트리는 노드가 없거나 높이가 1 이상인 m-원 탐색 트리 이다.
② 루트 노드를 제외하고 터미널 노드가 아닌,
즉, Si != 0 인 노드는(내부노드) 최소 m/2 , 최대 m개의 서브 트리를 갖는다.

③ 루트는 터미널 노드가 아니면 적어도 두 개의 서브 트리를 가진다.
④ 모든 터미널 노드, 즉 Si = 0을 만족하는 노드는 같은 레벨에 있다.
즉, 균형을 유지한다.


2. 노드 구조

① n : 키 값의 수(1≤n<m)
P0, … , Pn : 서브 트리에 대한 포인터
K1 …. , Kn: 키 값,
각 키 값(Ki) : 키 값 가진 레코드에 대한 포인터(Ai) 포함
② 한 노드 안의 키 값은 오름차순(1≤i ≤n-1 Ki < Ki+1)
③ Pi가 지시하는 서브 트리의 모든 키 값 < Ki+1
④ Pn이 지시하는 서브 트리의 모든 키 값 > Kn
⑤ Pi(0≤i≤n)가 지시하는 서브 트리 : 모두 m-원 서브 탐색 트리




3. B-트리의 장점
- 삽입, 삭제 뒤에도 균형 상태 유지
- 저장 장치의 효율성
․ 각 노드는 적어도 반 이상 키 값이 저장되어 있다.
․ 최악 O(logn(N+1)) 번의 노드 접근 = 완전 균형 트리에 준함


4. 3차 B-트리 구조
․ 키값 42 검색과정
a노드 -> b노드 -> e노드 -> n노드 -> n 노드 내에서는 순차검색


5. 삽입 알고리즘의 이해
: 균형을 유지하면서 항상 단말 노드에 삽입
- 여유 공간이 있는 경우 : 단순히 순서에 맞게 삽입한다.
- 여유 공간이 없는 경우 : 노드에서 overflow가 발생되며 split()으로 해결한다.
해당 노드를 두 개의 노드로 분할해야 한다.
해당 노드의 키 값에 새로운 키 값 삽입했다고 가정한다.
중간 키 값( m/2 번째)을 중심으로 왼편 작은 키들은 해당 노드에 남겨두고,
오른편 큰 키들은 새로운 노드에 저장한다.
중간 키 값 : 분할된 노드의 부모 노드로 올라가 삽입한다.
분할된 두 개의 노드를 중간 키 값의 왼쪽과 오른쪽 서브 트리가 되도록 조정한다.
부모 노드로 올라간 중간 키 값을 삽입할 때 overflow가 발생되면,
다시 overflow 발생 시 위와 같은 마디분리(split()) 작업을 반복 한다.

참고 자료

없음