B+Tree

B-Tree의 변형으로, 실제 데이터를 리프 노드에만 저장합니다. 대부분의 DB(MySQL InnoDB 등)가 사용합니다.

B-Tree vs B+Tree

B-Tree: 모든 노드에 데이터 저장

        [30:데이터]
       /          \
[10:데이터]    [50:데이터]

B+Tree: 리프 노드에만 데이터 저장

        [30]              ← 키만 저장 (길잡이)
       /    \
   [10,20] → [30,50]      ← 실제 데이터 + 연결

구조

            [30, 60]                    ← 내부 노드 (키만)
           /    |    \
        /       |       \
   [10,20] → [30,40,50] → [60,70,80]   ← 리프 노드 (데이터)

탐색 과정

35 찾기:

1. [30, 60] → 35 > 30, 35 < 60 → 가운데로

2. [30, 40, 50] 리프에서 35 찾기 → 없음

범위 검색이 빠른 이유

WHERE age BETWEEN 25 AND 55

B-Tree: 트리를 여러 번 탐색해야 함

B+Tree:
1. 25 찾아서 리프로 이동
2. 리프에서 오른쪽으로 쭉 이동하며 수집
   [20,25] → [30,40,50] → [55,60]
   여기서   →  전부 수집  → 여기까지

리프가 연결되어 있어서 순차 접근이 빠릅니다.

핵심 차이

B-TreeB+Tree
데이터 위치모든 노드리프만
리프 연결없음링크드 리스트
내부 노드데이터 포함키만 저장
범위 검색느림빠름
동등 검색빠를 수 있음항상 리프까지

B+Tree 장점

장점이유
범위 검색 빠름리프가 연결됨
내부 노드에 키 더 많이 저장데이터 없으니 공간 여유
트리 높이 낮음한 노드에 키가 많음
순차 접근 효율적리프만 순회하면 됨

실제 사용

-- MySQL InnoDB
CREATE INDEX idx_age ON users(age);

-- 내부적으로 B+Tree 생성

대부분의 RDBMS가 B+Tree를 기본 인덱스로 사용합니다.

B+Tree를 사용하는 이유

1. 트리 높이가 낮다

내부 노드에 데이터 없음
    ↓
같은 블록에 키 더 많이 저장 (19개 → 500개)
    ↓
트리 높이 낮아짐 (6 → 3)
    ↓
디스크 I/O 감소

2. 범위 검색이 빠르다

B-Tree:  트리를 왔다 갔다
B+Tree:  리프에서 옆으로 쭉 이동 (Linked List)

WHERE id BETWEEN 20 AND 50
ORDER BY id

3. 전체 스캔이 빠르다

B-Tree:  트리 전체 순회
B+Tree:  리프만 순차적으로 읽으면 끝

4. 성능이 일정하다

B-Tree:  1~6번 (들쭉날쭉)
B+Tree:  항상 3번 (예측 가능)

정리

항목B-TreeB+Tree
내부 노드키 + 데이터키만
노드당 키 수적음많음
트리 높이높음낮음
디스크 I/O많음적음
범위 검색느림빠름
전체 스캔느림빠름
성능 예측어려움일정함

결론

DB는 범위 검색, 정렬, 전체 스캔이 많고, 디스크 I/O가 병목입니다.

B+Tree는 이 모든 상황에서 유리해서 대부분의 RDBMS가 사용합니다.

CSLOG에서 보기