핵심 인사이트 (3줄 요약)

• **다분 탐색 트리(Multi-way Search Tree)**의 일종으로, 모든 리프 노드가 같은 깊이를 가지는 균형 트리(Balanced Tree)임.
• 노드 내 데이터가 정렬된 상태를 유지하며, 하나의 노드에 여러 자식 노드를 가질 수 있어 대량의 데이터를 처리하는 디스크 기반 데이터베이스 및 파일 시스템에 최적화됨.
• 이진 탐색 트리와 달리 노드당 키 개수를 늘려 트리의 높이를 낮춤으로써 디스크 I/O 횟수를 최소화함.

Ⅰ. 개요 (Context & Background)

• 배경: 대용량 데이터를 처리할 때 주메모리보다 느린 보조기억장치(HDD, SSD) 접근 비용이 성능 병목이 됨. 이진 탐색 트리는 트리가 깊어질수록 디스크 접근 횟수가 늘어나는 단점이 있음.
• 정의: 노드 하나에 여러 개의 키를 저장하고 여러 개의 자식을 가질 수 있도록 설계된 균형 다분 탐색 트리임.
• 특징: 모든 리프 노드는 동일한 레벨에 위치하며, 각 노드는 최소 $\lceil M/2 \rceil - 1$개에서 최대 $M-1$개의 키를 가짐 ($M$은 트리의 차수).

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

[ B-Tree Structure (Degree M=3) ]
          +-----------+
          |   [20]    |  <-- Root Node (Key: 20)
          +--/-----\--+
            /       \
   +-------/---+     +---\-------+
   | [10] [15] |     | [30] [40] |  <-- Internal Nodes
   +--/---|--\-+     +--/---|--\-+
     /    |   \        /    |    \
 [5,7] [12] [18]    [25] [35]  [45,50]  <-- Leaf Nodes (Same Level)

• 탐색(Search): 루트에서 시작하여 노드 내 키와 비교하며 적절한 포인터를 따라 리프까지 내려감 ($O(\log n)$).
• 삽입(Insertion): 리프 노드에 삽입 후, 노드가 가득 차면(Overflow) 중앙값을 부모로 올리고 노드를 분할(Split)함.
• 삭제(Deletion): 리프 노드에서 삭제 후, 최소 키 개수 미달 시(Underflow) 형제 노드에서 빌려오거나(Redistribution) 병합(Merge)을 수행함.

Ⅲ. 융합 비교 및 다각도 분석 (Comparison & Synergy)

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

• 적용 사례: Oracle, MySQL(InnoDB)의 인덱스 구조, NTFS/Ext4 파일 시스템의 디렉터리 구조.
• 기술사적 판단: 현대 시스템에서는 CPU 연산 속도보다 저장장치의 Latency가 훨씬 크므로, 페이지 단위 읽기에 최적화된 B-트리 계열을 사용하는 것이 데이터 일관성과 성능 확보의 핵심 전략임.

Ⅴ. 기대효과 및 결론 (Future & Standard)

• 기대효과: 트리의 높이를 낮게 유지(Low Fan-out)하여 수백만 건의 데이터도 3~4번의 디스크 접근만으로 탐색 가능하게 함.
• 결론: B-트리는 대규모 데이터 저장소의 성능 보장을 위한 표준 알고리즘이며, 최근에는 SSD의 특성에 맞춘 LSM-Tree 등으로 발전하고 있으나 여전히 인덱싱의 근간을 이룸.

📌 관련 개념 맵 (Knowledge Graph)

• 상위 개념: Balanced Search Tree, Multi-way Tree
• 하위/확장 개념: B+Tree (리프 연결), B*Tree (분할 억제), 2-3 Tree, AVL Tree

👶 어린이를 위한 3줄 비유 설명

• 한 층에 책이 수천 권 있는 거대한 도서관에서 책을 찾는 것과 같아요.
• 일반적인 계단(BST) 대신, 한 번에 수십 층씩 올라가는 초고속 엘리베이터(B-Tree)를 타고 올라가요.
• 엘리베이터 문이 열릴 때마다 내가 찾는 층이 어디인지 정확히 알려줘서 아주 빨리 도착할 수 있답니다.