B+Tree는 디스크 접근을 최소화하기 위해 설계된 균형 트리 자료구조다

요약

• 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개 자식 (분기 수 증가)

B-tree와의 차이

참고

• https://m.youtube.com/watch?v=K1a2Bk8NrYQ