B-트리 (B-Tree)

B-트리 (B-Tree)

각 노드가 여러 개의 키와 자식을 가질 수 있는 자가 균형 다원 탐색 트리로, 디스크 I/O를 최소화하도록 설계되어 데이터베이스와 파일 시스템의 인덱스로 널리 사용

목적: 디스크 I/O 최소화, 대용량 데이터 인덱싱, 균형 유지, 블록 단위 접근

특징: 다원 탐색 트리, 노드당 다수 키, 정렬 유지, 균형 보장, 디스크 최적화

구조(차수 m)

• •루트: 최소 1개 키
• •내부 노드: ⌈m/2⌉-1 ~ m-1개 키, ⌈m/2⌉ ~ m개 자식
• •리프: 모두 같은 레벨(균형)
• •정렬: key[i-1] < child[i] < key[i]

연산

• •검색(Search): 루트부터 키 비교, O(log n)
• •삽입(Insert): 리프에 삽입, 오버플로우 시 분할(split), O(log n)
• •삭제(Delete): 언더플로우 시 병합(merge) 또는 재분배, O(log n)

시간 복잡도: 검색·삽입·삭제 O(log n), 디스크 I/O = O(log_m n)

공간 복잡도: O(n), 노드당 최대 m-1개 키

장점: 디스크 I/O 최소화, 균형 보장, 범위 쿼리 효율, 대용량 데이터

단점: 복잡한 구현, 메모리 오버헤드(다수 키), 노드 분할·병합 비용

적용사례: 데이터베이스 인덱스(MySQL InnoDB), 파일 시스템(NTFS, ext4, Btrfs), SSD FTL(Flash Translation Layer): 논리-물리 주소 매핑

변형: B+트리(리프에만 데이터, 범위 쿼리 최적), B*트리(최소 2/3 채움)

비교: B-트리(다원/디스크/O(log_m n)) vs BST(이진/메모리/O(log n))

연관: B+트리, 데이터베이스 인덱스, 디스크 I/O, 다원 탐색 트리