B+ Tree 구현 1일차

---

동기

• C++의 많은 STL에서 R/B트리와 같은 균형 트리를 사용하는데 그 이해도를 높여보고자 B+ Tree를 직접 공부하고 구현해고자 합니다.

---

개념

B트리?

• Balanced tree 라고도 불리며 모든 leaf노드가 동일한 깊이를 가진다.
• m은 트리의 차수로 정의한다.
• root 노드는 최소 1개부터 m-1개의 키를 가질 수 있다.
• 각 노드는 최소 m/2개에서 최대 m-1개의 키를 가진다.
• 각 노드의 자식 수는 노드의 키 수보다 1개 더 많다.

삽입

1. 삽입 위치 탐색

• Root부터 시작하여 적절한 Leaf노드를 찾아서 키를 삽입한다.

2. 노드 분할

• 분할 조건 : 키의 개수가 m개를 초과하는 경우
• 분할 방법

1. 노드를 두개로 분할하고 중간 키를 부모 노드로 올린다.
2. 오버플로우가 발생하지 않을 때 까지 이 과정을 반복한다.

삭제

1. 삭제 위치 탐색

• Root부터 시작해 키를 포함하고 있는 노드를 찾아 삭제한다.

2. 언더플로우 확인

• 키를 삭제한 후 해당 노드에서의 키의 개수가 m/2개 미만이라면 두 가지의 방법을 사용할 수 있다.

1. 형제 노드로부터 키 빌려오기
   형제 노드가 m/2개 보다 많은 키를 가지고 있다면 키 하나를 빌려온다.
2. 형제 노드와 병합하기
   1번 방법이 사용이 불가하다면 형제 노드와 현재 노드를 합친다.

B Tree 와 B+ Tree의 차이

• 구조적으로는 유사하나 B+ 트리는 Leaf노드에만 데이터가 저장된다.
• 모든 Leaf노드는 포인터를 통해 서로 연결되어 있다.
• 내부 노드는 자식 노드 포인터를 위한 키만을 저장한다.

---

GitHub - https://github.com/EmpChan/B-Plus-Tree