B-Tree 개념과 특징

B-Tree란?

• 이진탐색트리(BST)를 일반화한 균형 트리로, 하나의 노드가 여러 키와 여러 자식을 가진다
• 모든 리프 노드가 같은 레벨에 있어 탐색 경로 길이가 균등하다
• DB 인덱스, 파일 시스템에서 널리 사용된다

구조와 규칙

• M차 B-Tree: 각 노드의 최대 자식 수가 M
• 최대 키 수: M-1
• 최소 자식 수: ceil(M/2) (root, leaf 제외)
• 최소 키 수: ceil(M/2) - 1 (root, leaf 제외)
• internal 노드의 키 수가 x개라면 자식 수는 x+1개
• 키는 항상 오름차순으로 정렬된다

삽입

• 삽입은 항상 leaf에서 발생
• 노드가 넘치면 median 키를 기준으로 좌/우 분할
• median 키는 부모로 승격

삭제

• 삭제는 leaf에서 수행
• internal 노드 삭제 시 predecessor/successor로 교체 후 삭제
• 삭제 후 최소 키 수 미만이면 재조정 필요

재조정 방식

1. 형제 노드에서 키를 빌린다 (rotation)
2. 불가능하면 부모 키를 내려받고 형제와 병합
3. 부모에 문제가 생기면 위로 재조정

B-Tree와 B+Tree 차이 (요약)

• B-Tree: 내부 노드와 리프 모두 키/데이터를 가질 수 있음
• B+Tree: 모든 데이터는 리프에만 있고 리프가 연결 리스트로 연결됨
• 범위 조회와 디스크 I/O 최적화 때문에 DB는 B+Tree를 더 많이 사용

B-Tree가 DB 인덱스에 적합한 이유

항목	B-Tree 계열	Self-balancing BST
탐색/삽입/삭제	O(logN)	O(logN)
디스크 I/O	적음	상대적으로 많음
노드 fan-out	큼	작음

• 디스크는 블록 단위로 읽기/쓰기를 수행
• 하나의 노드에 많은 키를 담아 fan-out을 키우면 트리 높이가 낮아짐
• 트리 높이가 낮으면 디스크 접근 횟수가 줄어 성능이 좋아진다

참고 & 출처

• 쉬운코드
• B-Tree - Wikipedia
• https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC