B-Tree vs B+Tree, 그리고 InnoDB가 B+Tree를 쓰는 이유

1. 도입

인덱스를 설명할 때 흔히 "B-Tree 인덱스"라는 말을 쓴다. 그런데 실제로 MySQL InnoDB가 쓰는 자료구조는 정확히는 B-Tree가 아니라 B+Tree다. 처음엔 둘이 거의 같은 거라고 생각하고 넘어갔는데, 범위 검색이 왜 빠른지, 클러스터형 인덱스가 왜 그렇게 동작하는지를 따라가다 보니 결국 "B-Tree와 B+Tree의 차이"로 되돌아오게 됐다.

이 글에서는 B-Tree와 B+Tree가 무엇이 다른지, 그리고 디스크 기반 스토리지 엔진인 InnoDB가 왜 B+Tree를 선택했는지를 직접 따라가 본 흐름으로 정리했다. 주된 출처는 Alex Petrov의 Database Internals Part I(Storage Engines)이며, InnoDB 동작은 MySQL Reference Manual을 곁들여 확인했다.

결론을 한 줄로 먼저 적으면: B+Tree는 모든 데이터를 리프 노드에만 두고, 리프끼리 연결 리스트로 잇기 때문에 디스크 친화적이면서 범위 검색에 강하다.

2. 핵심 개념: B-Tree라는 출발점

B-Tree는 균형 잡힌(balanced) 다진 탐색 트리다. 이진 탐색 트리(BST)가 노드마다 자식을 2개 가지는 것과 달리, B-Tree의 한 노드는 여러 개의 키와 여러 개의 자식 포인터를 가진다. Database Internals에서는 이를 두고 "한 노드의 폭(fan-out)을 키워서 트리의 높이를 낮춘다"고 설명한다.

왜 폭을 키울까? 디스크(또는 SSD)는 한 번 읽을 때 블록/페이지 단위로 읽는다. 메모리 접근에 비해 디스크 접근은 수십~수만 배 느리기 때문에, 트리의 높이 = 디스크 I/O 횟수가 성능을 지배한다. 한 노드를 한 페이지(InnoDB 기본 16KB)에 꽉 채워서 fan-out을 수백 단위로 올리면, 수억 건의 데이터도 트리 높이 3~4 정도로 다룰 수 있다.

여기서 B-Tree의 한 가지 특징이 중요하다. B-Tree는 키와 함께 그 키에 해당하는 값(혹은 레코드)을 내부 노드에도 저장할 수 있다. 즉 루트나 중간 노드에서 찾는 키가 매칭되면 거기서 바로 값을 반환할 수 있다.

3. B+Tree는 무엇이 다른가

B+Tree는 B-Tree의 변형인데, 두 가지 규칙이 핵심이다.

1. 모든 실제 데이터(값)는 리프 노드에만 저장한다. 내부 노드는 오직 "어느 방향으로 내려갈지" 알려주는 라우팅용 키만 가진다.
2. 리프 노드들은 서로 연결 리스트로 이어져 있다. (보통 정렬 순서대로 다음 리프를 가리키는 포인터)

이 두 규칙의 차이를 표로 정리하면 이렇다.

항목	B-Tree	B+Tree
값 저장 위치	내부 + 리프 모두 가능	리프 노드에만
내부 노드 역할	키 + 값	라우팅(키)만
내부 노드 fan-out	값이 끼어 상대적으로 작음	키만 있어 더 큼
리프 간 연결	없음	연결 리스트로 연결
범위 검색	트리 재탐색 필요	리프 순회로 처리
같은 키 중복	없음	내부에 라우팅 키로 중복 등장 가능

구조를 ASCII로 그려 보면 차이가 분명해진다. 아래는 B+Tree의 모양이다.

                 [ 30 | 60 ]            ← 내부(라우팅) 노드: 키만
                /     |     \
        [10|20]   [30|40|50]   [60|70|80]   ← 리프 노드: 실제 값 보관
          |  ───────► |  ──────────► |       ← 리프끼리 연결 리스트

내부 노드의 30, 60은 "여기서 갈라진다"는 이정표일 뿐이고, 실제 30에 대응하는 데이터는 가운데 리프에 들어 있다. 그래서 B+Tree에서는 같은 키가 내부 노드(라우팅용)와 리프 노드(실제 값)에 중복으로 등장할 수 있다. 이걸 처음 봤을 때 "값이 두 번 저장되는 거 아냐?"라고 헷갈렸는데, 내부 노드에 있는 건 값이 아니라 분기용 키 복사본일 뿐이다.

자주 헷갈리는 지점

• "B+Tree가 항상 B-Tree보다 노드 수가 적다"는 오해: 모든 값을 리프에 모으기 때문에 오히려 리프 레벨은 더 빽빽해질 수 있다. 대신 내부 노드는 키만 담아 가벼워지고 fan-out이 커진다.
• 단일 키 조회(point query)에서는 B-Tree가 운 좋으면 더 빠를 수 있다: B-Tree는 찾는 키가 상위 노드에 있으면 리프까지 안 내려가도 된다. 반면 B+Tree는 값이 무조건 리프에 있으므로 항상 리프까지 내려간다. 즉 조회 경로 길이가 일정하다.

4. InnoDB는 왜 B+Tree인가

InnoDB의 인덱스(클러스터형 PK 인덱스, 보조 인덱스 모두)는 B+Tree로 구현돼 있다고 MySQL Reference Manual(§15.x InnoDB On-Disk Structures)에 서술돼 있다. 디스크 기반 스토리지 엔진 관점에서 B+Tree가 선택되는 이유를 정리하면 다음과 같다.

(1) 범위 검색·정렬에 압도적으로 유리하다.
WHERE id BETWEEN 100 AND 200, ORDER BY id, 페이지네이션 같은 쿼리는 실무에서 매우 흔하다. B+Tree는 시작 키가 있는 리프를 한 번 찾은 뒤, 리프 연결 리스트를 따라 옆으로 쭉 읽으면 끝이다. 트리를 다시 타고 오르내릴 필요가 없다. B-Tree라면 다음 키를 찾을 때마다 중위 순회를 위해 위로 올라갔다 내려와야 한다.

-- B+Tree에서 이 쿼리는:
--   1) 리프에서 id=100 위치를 한 번 탐색
--   2) 거기서부터 리프 연결 리스트를 따라 200까지 순차 스캔
SELECT * FROM orders WHERE id BETWEEN 100 AND 200 ORDER BY id;

(2) 내부 노드가 가벼워 fan-out이 커지고, 트리 높이가 낮아진다.
내부 노드에 값이 끼지 않으니 한 페이지에 더 많은 키 + 자식 포인터를 담을 수 있다. fan-out이 커지면 같은 데이터 양을 더 낮은 높이로 표현할 수 있고, 이는 곧 조회당 디스크 I/O 횟수 감소로 이어진다.

(3) 풀 스캔(전체 순회)이 단순하다.
모든 데이터가 리프에 정렬돼 연결돼 있으므로, 인덱스 전체를 읽어야 할 때 리프 레벨만 순차적으로 따라가면 된다. 디스크의 순차 읽기는 임의 읽기보다 훨씬 빠르므로 이 점이 유리하다.

(4) 클러스터형 인덱스 구조와 잘 맞는다.
InnoDB는 PK 기준 클러스터형 인덱스를 쓴다. 즉 리프 노드 자체가 행 데이터 전체를 담는다(B+Tree의 "값은 리프에" 규칙과 그대로 맞물린다). 보조 인덱스의 리프는 값 대신 PK 값을 담고, 그 PK로 클러스터형 인덱스를 다시 타는 식이다. 이 설계가 B+Tree의 "리프 = 데이터" 모델과 자연스럽게 들어맞는다.

정리하면, 디스크 I/O가 비싸고 범위/정렬 쿼리가 흔한 환경이라는 제약 아래에서 B+Tree가 합리적인 선택이라는 것이다. 메모리 안에서 단일 키만 빠르게 찾는 게 목적이라면 해시 인덱스나 일반 B-Tree가 더 나을 수도 있지만, 범용 디스크 DB의 기본 인덱스로는 B+Tree가 표준이 됐다.

5. 작은 확인: 높이와 fan-out 감각

숫자로 감을 잡아 보자. InnoDB 기본 페이지가 16KB이고, 내부 노드의 한 엔트리(키 + 자식 포인터)가 대략 십수 바이트라고 가정하면 fan-out은 수백 단위가 된다. 아주 보수적으로 fan-out을 100이라 잡아도:

• 높이 2: 100 × 100 = 약 1만 개 리프 진입점
• 높이 3: 100³ = 약 100만
• 높이 4: 100⁴ = 약 1억

즉 수억 건이라도 루트→리프까지 3~4번의 페이지 접근이면 도달한다. fan-out을 더 현실적인 수백으로 잡으면 높이는 더 낮아진다. "인덱스 타면 빠르다"는 말의 정체가 결국 이 낮은 트리 높이라는 걸 직접 계산해 보고서야 체감이 됐다. (정확한 fan-out은 키 크기·페이지 채움률에 따라 달라지므로 위 숫자는 어디까지나 감각용 근사다.)

6. 정리

B-Tree는 값을 내부 노드에도 둘 수 있고, B+Tree는 값을 리프에만 두고 리프끼리 이어 붙인다. InnoDB는 디스크 I/O 절감과 범위 검색 효율 때문에 B+Tree를 쓴다.

• B+Tree의 두 규칙(값은 리프에만, 리프는 연결 리스트)이 범위 검색·정렬·풀 스캔의 강점을 만든다.
• 내부 노드가 가벼워 fan-out이 커지고, 트리 높이가 낮아져 조회당 I/O가 줄어든다.
• InnoDB의 클러스터형 인덱스는 "리프 = 행 데이터"라는 B+Tree 모델과 그대로 맞물린다.

다음에 더 파고들 만한 주제:

• InnoDB 보조 인덱스가 PK를 다시 타는 구조와 커버링 인덱스(covering index)의 동작
• LSM-Tree와 B+Tree의 write 경로 비교 (쓰기 많은 워크로드에서의 트레이드오프)

참고 자료

• Alex Petrov, Database Internals, Part I — Storage Engines (B-Tree / B+Tree 구조, fan-out, 디스크 기반 트리 설계)
• MySQL Reference Manual, §15 InnoDB Storage Engine — On-Disk Structures, Index 구조 (InnoDB가 B+Tree와 클러스터형 인덱스를 사용한다는 서술)