✅ B-tree 자료구조 완전 정복 🔍

"대용량 데이터를 빠르게 검색하고 정렬하는 비결!"

 

오늘의 포스팅은 면접에서 질문에 대답을 못해서 ㅎㅎ
작성해 봅니당

---

📌 B-tree란?

B-tree는 **균형 잡힌 다진 트리(Balanced Multiway Tree)**로,
디스크 기반 저장 시스템이나 데이터베이스에서 자주 사용되는 자료구조입니다.

기본적인 Binary Tree와 다르게, 하나의 노드가 여러 개의 키와 자식을 가질 수 있어
검색, 삽입, 삭제가 모두 로그 시간(log n) 안에 수행됩니다.

---

🎯 B-tree의 핵심 특징

항목 설명

구조	균형 잡힌 N진 트리
노드당 키	여러 개의 키 보유 가능
노드당 자식	최대 M개의 자식 노드 (M차 B-tree)
균형 유지	모든 리프 노드의 깊이가 동일
주요 용도	데이터베이스, 파일 시스템, 인덱스 구조

---

🧱 B-tree 기본 구조 예시

          [17 | 35]
         /    |    \
     [1 8]  [18 25] [40 50]

• 각 노드는 여러 개의 키를 가질 수 있으며,
• 각 자식 노드는 해당 키의 범위 내 값들을 포함합니다.
• 삽입/삭제 시 트리가 균형을 자동으로 유지합니다.

---

🧠 B-tree 작동 원리

🔹 검색 (Search)

• 루트 노드부터 시작하여 키와 비교하며 하위 노드로 이동
• 시간 복잡도: O(log n)

🔹 삽입 (Insert)

• 리프 노드까지 내려가 삽입
• 노드가 가득 찼을 경우 분할(split) 수행

🔹 삭제 (Delete)

• 삭제 후 노드의 최소 키 수를 만족하지 않으면 병합 또는 키 이동

---

🧩 B-tree vs Binary Search Tree 비교

항목 B-tree BST

자식 수	다수 (M진 트리)	최대 2개
깊이	얕음 (빠름)	깊어질 수 있음
디스크 최적화	가능	미흡
사용처	DB, 파일 시스템	일반 알고리즘 문제

---

📦 실전 활용 사례

• 📁 파일 시스템 (ex. NTFS, HFS, ext4)
• 💾 데이터베이스 인덱스 (MySQL, PostgreSQL 등)
• 📚 키-값 저장소 (B+ Tree로 응용)

---

📚 확장: B+ Tree는 뭐가 다를까?

항목 B-tree B+ Tree

내부 노드	키 & 데이터	키만 있음
리프 노드	없음	전체 데이터 저장
순차 탐색	복잡함	빠름 (리프 노드 연결)

---

✅ 정리 요약

• B-tree는 높이 균형을 유지하면서도 빠른 검색/삽입/삭제가 가능한 트리 구조
• 대용량 데이터 환경에서 성능 최적화에 필수
• 데이터베이스, 파일시스템 등 실전에서 매우 자주 사용됨!