요약
- B-Tree는 디스크 I/O를 최소화하기 위해 설계된 균형 트리 자료구조다
- 하나의 노드에 여러 키를 저장하여 트리 높이를 낮추고 디스크 접근 횟수를 줄인다
본문
구조
- 노드에 n개 키가 저장되면 n+1개의 branch 존재
- 페이지 크기: 보통 8KB (InnoDB 기준 16KB)
- 디스크에 저장되어 durability 보장
균형 유지
- 노드가 가득 차면 분할 (split)
- 가운데 값이 부모로 올라감 (bottom-up)
- 삭제 시 최소 키 개수 미달하면 재조정
시간 복잡도
- 검색: O(log n)
- 삽입/삭제: O(log n)
이진 검색 트리보다 빠른 이유
Big-O 표기법은 같지만 로그의 **밑(base)**이 다르다:
- 이진 검색 트리: O(log₂ n) - 매번 2개 중 하나 선택
- B-Tree: O(log_m n) - 매번 m개(수백~수천) 중 하나 선택
예: 1억 개 데이터
- 이진 검색 트리: log₂(100,000,000) ≈ 27번 디스크 접근
- B-Tree (분기 수 1000): log₁₀₀₀(100,000,000) ≈ 3번 디스크 접근
분할(split) 상세 동작
노드가 가득 찬 상태에서 새 키 삽입 시:
[1, 3, 5, 7] + 4 삽입
↓
[1, 3, 4, 5, 7] ← 정렬 후 가운데는 4
↓
[4] ← 가운데 값이 부모로
/ \
[1,3] [5,7] ← 나머지가 두 자식으로
부모 노드가 이미 존재하면 가운데 값이 기존 부모에 추가됨. 부모도 가득 차 있으면 연쇄적으로 분할이 전파되고, 루트가 분할되면 트리 높이가 증가한다.
노드 크기가 디스크 블록 크기와 같은 이유
- 디스크는 블록(페이지) 단위로 읽음 (1바이트만 필요해도 전체 블록을 읽어옴)
- 노드 크기를 디스크 블록 크기에 맞추면 한 번 읽기로 노드 하나를 온전히 가져옴
- 노드가 너무 작으면 불필요한 데이터까지 읽게 되고, 너무 크면 여러 번 디스크 접근 필요
다른 트리 구조와의 차이
이진 검색 트리와의 차이
- 이진 검색 트리: 노드당 1개 키, 2개 자식
- B+Tree: 노드당 n개 키, n+1개 자식 (분기 수 증가)