➕ B-Tree 완벽 정리 - 디스크 기반 탐색을 위한 균형 트리

---

✅ B+ Tree란?

B+ Tree는 B-Tree의 확장형으로, 모든 실제 데이터는 리프 노드에만 저장되고,
내부 노드는 탐색 경로를 위한 인덱스 역할만 수행하는 균형 트리 구조이다.

데이터베이스, 파일 시스템, 키-값 저장소 등에서 범위 검색과 순차 탐색이 매우 빠르기 때문에 가장 많이 쓰이는 인덱스 트리 구조다.

---

✅ B+ Tree와 B-Tree의 차이

항목	B-Tree	B+ Tree
데이터 저장	내부 노드와 리프 노드 모두	리프 노드에만 저장
리프 노드 연결	없음	리프 노드끼리 연결 (linked list)
검색 속도	키 찾을 때 노드마다 탐색 필요	리프까지 한 번만 내려가면 됨
범위 검색	느림 (리프 노드 간 연결 없음)	빠름 (연속된 리프 노드 순회)

---

✅ 특징 요약

• 리프 노드만 실제 데이터를 저장한다.
• 모든 리프 노드는 오른쪽으로 연결되어 있어, 범위 탐색과 정렬된 순회가 빠르다.
• 내부 노드는 인덱스 역할만 하며, 데이터는 포함하지 않는다.
• 노드는 B-Tree처럼 최소/최대 키 개수를 만족하며, 삽입/삭제 시 분할과 병합을 통해 균형을 유지한다.

---

✅ 삽입

1. 항상 리프 노드에 삽입된다.
2. 리프 노드가 가득 차면 → 노드를 분할
3. 중간 키는 부모로 올라가 인덱스 역할을 한다.
4. 부모 노드도 가득 차면 → 다시 분할 & 중간 키를 위로 전파
5. 필요시 루트까지 분할이 전파될 수 있음

---

✅ 삭제

1. 리프 노드에서 데이터 삭제
2. 삭제 후 키 개수가 부족하면 → 형제 노드에서 차용하거나 병합
3. 부모 노드의 인덱스도 같이 갱신
4. 균형이 유지되도록 트리 구조 조정

---

✅ 시간복잡도

연산	시간복잡도
탐색	O(log n)
삽입	O(log n)
삭제	O(log n)
범위검색	O(log n) + O(k) (k: 결과 개수)

---

✅ B+ Tree가 실무에서 인기 있는 이유

• 범위 검색, 순차 검색이 빠르다.
• 디스크 기반 시스템에서 I/O가 최소화되도록 설계되었다.
• 모든 데이터가 리프에 있어 정렬된 구조를 갖는다.
• 대용량 데이터 인덱싱에 최적화되어 있다.

---

🎯 마무리 요약

• B+ Tree는 B-Tree의 확장 버전으로, 데이터는 리프에만, 내부 노드는 인덱스로만 사용한다.
• 리프 노드끼리 연결되어 있어 범위 탐색이 매우 빠르다.
• 데이터베이스 인덱스, 파일 시스템 등에서 가장 널리 쓰이는 트리이다.
• 삽입/삭제 시에도 균형이 자동으로 유지되며, 성능은 O(log n) 수준이다.