B 트리와 B+ 트리

M원 검색트리(M-way Search Tree)

특징

• 차수를 2에서 m으로 확장해 이진탐색트리의 높이 문제를 해결한 자료구조
• 각 노드는 m-1개의 레코드와 m개의 서브트리를 가질 수 있다.
• 각 노드의 레코드들은 정렬되어 있다.

3-원 검색 트리

---

B 트리

특징

• 높이 문제를 개선한 M원 검색트리에서 균형 문제도 해결한 자료구조
• 데이터의 삽입, 삭제 시 균형을 맞추는 알고리즘을 수행한다.

규칙

• 모든 단말 노드는 같은 레벨에 있다.
• 노드는 최대 M개, 최소 ⌈M/2⌉개의 자식을 가진다.
• 노드는 최대 M−1개, 최소 [M/2]−1개의 키를 가진다.
• 노드의 키가 X개면, 자식의 수는 X+1개다.

3차 B 트리

시간 복잡도

• 원소 삽입, 삭제, 탐색: O(logN)

Key 삽입 과정

1. 요소를 삽입할 단말 노드를 선택 후 Key 삽입
2. Key의 최대개수를 초과할 경우, 분할 실행
3. 중앙값을 부모노드에 병합하고 왼쪽 키는 왼쪽 자식, 오른쪽 키는 오른쪽 자식으로 연결
4. 부모노드를 검사하여 Key의 최대개수를 초과하지 않을 때까지 반복

Key 삭제 과정

1. 단말 노드에서 Key 삭제

1. 요소를 삭제할 노드를 선택 후 Key 삭제
2. Key의 최소개수 미만이 될 경우, 부모 Key로 대체
3. 부모 Key는 왼쪽 형제의 가장 큰 Key 혹은 오른쪽 형제의 가장 큰 Key로 대체
4. 왼쪽과 오른쪽 형제 Key가 모두 최소개수일 경우, 노드를 삭제하고 부모 Key를 형제 노드에 병합
5. 부모 Key도 최소개수라면, 재구조화 실행

2. 내부 노드에서 Key 삭제

1. 삭제할 Key를 왼쪽 서브트리의 가장 큰 Key 혹은 오른쪽 서브트리의 가장 작은 Key와 교체
2. 단말 노드 위치로 이동한 Key 삭제 (단말 노드 삭제 과정 진행)
3. 삭제할 노드와 교체할 노드의 Key가 모두 최소개수일 경우, 재구조화 실행

3. 재구조화

1. Key를 삭제하고 양쪽 자식 노드를 병합한다.
2. 부모 Key를 형제 노드에 병합하고, 병합한 자식 노드를 왼쪽 자식으로 가져온다.
3. Key의 최대개수를 초과할 경우, 분할 실행 (Key 삽입 과정 진행)

참고

[자료구조] 그림으로 알아보는 B-Tree

---

B+ 트리

특징

• 삽입, 삭제 연산이 단말 노드에서만 발생한다.
• 단말 노드들은 연결리스트로 연결되어 선형 탐색에 유리하다.

Key 삽입 과정

1. 분할 과정이 B 트리와 다르다.
2. 분할할 때 부모로 올린 중앙값을 단말 노드에 남겨둔다.

Key 삭제 과정

1. 내부 노드의 Key를 삭제해도 단말 노드의 Key를 함께 삭제한다.
2. 단말 노드 Key 삭제 후, 내부 노드 Key를 오른쪽 자식의 가장 작은 Key로 교체

참고

[자료구조] 그림으로 알아보는 B+Tree