Index, B-Tree와 B+Tree

데이터베이스 성능을 좌우하는 핵심 자료구조가 인덱스다.

수백만 건 중 한 행을 찾을 때, 인덱스가 없으면 테이블을 통째로 훑어야 한다. 인덱스가 있으면 디스크 I/O 몇 번이면 끝난다.

What’s Index?

인덱스(Index)는 데이터 조회 속도를 끌어올리기 위한 자료구조다. 책 뒷장의 색인처럼, 원하는 값의 위치를 빠르게 알려주는 보조 구조물이다.

당연히 공짜는 아니다. 트레이드오프가 따른다.

저장 공간: 인덱스 자체가 디스크를 차지한다.
쓰기 비용: INSERT, UPDATE, DELETE 마다 인덱스도 같이 갱신해야 한다.
메모리: 인덱스를 캐시에 올려두면 그만큼 메모리가 든다.

따라서 인덱스를 무작정 박지 않고, 조회가 잦은 컬럼에 골라서 거는 게 원칙이다.

왜 트리 인덱스인가

조회를 빠르게 하는 자료구조는 많다. Hash Table은 평균 $O(1)$ , 이진 탐색 트리는 $O(\log n)$ . 그런데 디스크 위에서는 둘 다 무너진다. B-Tree와 그 변형인 B+Tree만 살아남은 이유가 있다.

Hash Table

등호는 빠르지만 범위가 안 된다. Hash는 키 하나를 정확히 맞히는 등호 조회에 최적이다. 대신 두 가지 약점이 결정적이다.

범위 쿼리 불가: WHERE age BETWEEN 20 AND 30 같은 쿼리에서 해시는 쓸모가 없다. 키들이 무작위로 흩어져 있어 “20 다음 값이 무엇인지”를 모른다.
디스크 친화적이지 않다: 인접한 키가 디스크의 멀리 떨어진 페이지에 있을 수 있어, 범위 스캔은 매번 랜덤 I/O가 된다.

그래서 Hash Index는 메모리 캐시(예: Redis)나 PostgreSQL의 보조 인덱스 타입으로 제한적으로만 쓰인다.

이진 탐색 트리

메모리에서는 빠르지만 디스크에서는 깊이가 폭발한다. AVL, Red-Black 같은 균형 이진 트리는 $O(\log_2 n)$ 으로 빠르다. 메모리 안에서는 충분하다. 문제는 디스크다.

10억 건을 이진 트리에 넣으면 트리 높이는 약 $\log_2(10^9) \approx 30$ . 한 노드 = 한 디스크 페이지라고 보면, 한 번 조회에 디스크 I/O 30번이 발생한다. 디스크 한 번 읽기가 메모리보다 10만 배 느리니, 30번이면 사실상 망한 쿼리다.

두 자료구조의 실패 원인은 같다. 디스크 I/O 단위에 맞춰져 있지 않다는 점이다.

디스크는 한 번에 페이지(Page)라는 고정 단위로 읽고 쓴다. InnoDB는 16KB, PostgreSQL은 8KB가 기본이다. 이진 트리의 한 노드에 키를 1개만 담는 건, 16KB 페이지 안에 8바이트만 채우고 나머지를 버리는 셈이다.

\textbf{\text{페이지 한 장에 키를 가득 채워 트리를 납작하게 만든다.}}

이게 디스크 시대의 정답이고, B-Tree와 그 변형인 B+Tree가 그 답이다. Hash는 등호 조회에만, 이진 트리는 메모리 안에서만 통하지만, 트리 인덱스는 디스크 위에서 단건 조회와 범위 쿼리를 모두 처리한다.

먼저 기본형인 B-Tree를 보고, 그다음 실무 RDBMS가 쓰는 B+Tree로 넘어간다.

B-Tree

B-Tree는 1970년대에 디스크 기반 저장 시스템에 맞춰 설계된 균형 트리다. 한 노드에 여러 키와 자식을 담아 트리 높이를 끌어내린다.

차수(order)가 $m$ 인 B-Tree는 다음 규칙을 따른다.

각 노드는 최대 $m$ 개의 자식을 가진다.
루트를 제외한 내부 노드는 최소 $\lceil m/2 \rceil$ 개의 자식을 가진다.
루트는 리프가 아니라면 최소 2개의 자식을 가진다.
$k$ 개의 자식을 가진 노드는 $k-1$ 개의 키를 담는다.
모든 리프는 같은 깊이에 있다 (균형 트리).

flowchart TD
    R["30"] --> A["8, 15"]
    R --> B["40, 60"]
    A --> A1["3, 5"]
    A --> A2["10, 12"]
    A --> A3["18, 22"]
    B --> B1["35, 38"]
    B --> B2["45, 50"]
    B --> B3["70, 80"]

위 트리에서 3 을 찾는 과정.

루트 30 에서 $3 < 30$ , 왼쪽으로.
8, 15 에서 $3 < 8$ , 왼쪽으로.
리프 3, 5 에서 발견.

디스크 I/O 3번. 이진 트리라면 같은 데이터에 훨씬 더 많이 들었다.

Fanout

B-Tree의 위력은 fanout(노드당 자식 수)에서 나온다. 페이지 한 장에 키가 많이 들어갈수록 트리가 얕아진다. 페이지 한 장에 키를 몇 개 담느냐에 따라 트리 높이가 결정된다.

페이지 크기 $P$ , 키 크기 $K$ , 자식 포인터 크기 $R$ 일 때 fanout은 다음과 같다.

\text{fanout} = \left\lfloor \frac{P}{K + R} \right\rfloor

InnoDB 기준 실제 숫자를 넣어보면.

$P = 16{,}384$ bytes (16KB 페이지)
$K = 8$ bytes (BIGINT 키)
$R = 6$ bytes (InnoDB record pointer)

\text{fanout} = \left\lfloor \frac{16384}{8 + 6} \right\rfloor = 1170

트리 높이 $h$ 는 다음 식을 만족한다.

h \approx \lceil \log_{\text{fanout}}(N) \rceil

$N = 10^9$ (10억 행) 을 대입하면.

h \approx \log_{1170}(10^9) = \frac{9 \cdot \ln 10}{\ln 1170} \approx 2.93

\textbf{\text{10억 행을 단 3번의 디스크 I/O로 찾는다.}}

이게 B-Tree가 50년간 자리를 지킨 이유다.

행 수 $N$	이진 트리 높이	B-Tree 높이 ( $m=1170$ )
$10^6$ (백만)	$\approx 20$	$\approx 2$
$10^9$ (10억)	$\approx 30$	$\approx 3$
$10^{12}$ (1조)	$\approx 40$	$\approx 4$

게다가 루트와 상위 내부 노드는 자주 접근되어 거의 항상 메모리 캐시에 머문다. 실제 디스크 I/O는 리프 한 번으로 끝나는 경우가 많다.

같은 16KB 페이지를 어떻게 채우느냐 — 이진 트리 vs B-Tree

B+Tree

여기까지가 B-Tree의 기본형이다. 실무에서 쓰는 RDBMS는 거의 모두 그 변형인 B+Tree 를 쓴다. MySQL InnoDB, PostgreSQL, Oracle, SQL Server 모두 마찬가지다. 위에서 본 fanout·분할 메커니즘은 그대로 통용되고, B+Tree는 거기에 두 가지 변경을 더한다.

B-Tree와의 차이

flowchart TD
    subgraph BT["B-Tree (모든 노드에 데이터)"]
      direction TB
      BTR["20 data | 50 data"]
      BTL1["5 data | 10 data"]
      BTL2["25 data | 30 data"]
      BTL3["60 data | 80 data"]
      BTR --> BTL1
      BTR --> BTL2
      BTR --> BTL3
    end

flowchart TD
    subgraph BPT["B+Tree (리프에만 데이터, 리프 연결)"]
      direction TB
      BPTR["20 | 50"]
      BPTL1["5 data | 10 data | 20 data"]
      BPTL2["25 data | 30 data | 50 data"]
      BPTL3["60 data | 80 data"]
      BPTR --> BPTL1
      BPTR --> BPTL2
      BPTR --> BPTL3
      BPTL1 -.->|next| BPTL2
      BPTL2 -.->|next| BPTL3
    end

핵심 차이는 세 가지.

데이터 저장 위치: B-Tree는 모든 노드가 데이터를 갖는다. B+Tree는 데이터를 리프에만 둔다.
내부 노드의 역할: B+Tree의 내부 노드는 라우팅용 키만 담는다. 같은 페이지에 더 많은 키가 들어가니 fanout이 더 커지고, 트리는 더 얕아진다.
리프 연결: B+Tree의 리프 노드는 Linked List로 연결되어 있다.

B+Tree를 쓰는 이유

1. 범위 쿼리 효율

SELECT * FROM orders
WHERE created_at BETWEEN '2026-01-01' AND '2026-01-31';

B+Tree는 시작 지점만 트리로 찾고, 그 뒤는 리프의 linked list를 따라가며 순차 스캔한다. 디스크 입장에서는 인접 페이지를 연속으로 읽는 순차 I/O 가 된다.

2. 더 얕은 트리

내부 노드가 데이터를 들고 있지 않으니 한 페이지에 키를 더 많이 담는다. fanout이 커지고, 결과적으로 트리 높이가 한 단계 더 낮아진다.

3. 일관된 조회 비용

모든 조회가 리프까지 끝까지 내려간다. 운 좋으면 루트에서 끝나고 운 나쁘면 리프까지 가는 B-Tree와 달리, B+Tree는 어떤 키든 비슷한 비용으로 찾는다. 응답 시간 분포가 좁다.

삽입과 분할

B-Tree가 항상 균형을 유지하는 비결은 노드 분할(split)이다. 노드가 가득 차면 절반으로 쪼개고, 중간 키 하나를 부모로 끌어올린다.

차수 $m=4$ 인 트리에 15 를 삽입하는 예를 보자.

flowchart TD
    subgraph Before["삽입 전: 리프가 가득 참"]
      P1["부모: 50"]
      L1["10, 20, 30, 40"]
      L2["60, 70, 80"]
      P1 --> L1
      P1 --> L2
    end

15 가 들어갈 자리는 리프 10, 20, 30, 40 이다. 이 리프는 이미 가득 찼다. 분할이 일어난다.

flowchart TD
    subgraph After["삽입 후: 리프 분할, 20을 부모로 promote"]
      P2["부모: 20, 50"]
      L3["10, 15"]
      L4["30, 40"]
      L5["60, 70, 80"]
      P2 --> L3
      P2 --> L4
      P2 --> L5
    end

분할 절차는 다음과 같다.

가득 찬 리프에 새 키를 임시로 끼워넣는다 → 10, 15, 20, 30, 40
가운데 키 20 을 골라 부모로 promote한다.
남은 키를 좌우로 나눈다 → 10, 15 와 30, 40.
부모도 가득 차면 부모도 분할한다. 이 과정이 루트까지 전파될 수 있다.

루트가 분할되면 트리 높이가 1 늘어난다. 이게 B-Tree의 높이가 자라는 유일한 경로다. 모든 리프가 항상 같은 깊이에 머무는 비결이기도 하다.

한 키가 위로, 나머지는 좌우로 — 분할과 promote

삭제도 대칭적으로 동작한다. 노드가 최소치 미만으로 줄면 형제와 병합(merge)하거나 키를 재분배한다. 트리는 항상 균형을 유지한다.

순차 I/O와 범위 쿼리

B+Tree의 진짜 강점은 단건 조회보다 범위 스캔에서 드러난다. 리프가 linked list로 묶여 있다는 사실이 디스크 수준에서 어떤 의미인지 보자.

WHERE id BETWEEN 1000 AND 2000 같은 쿼리에서 B+Tree는 다음 순서로 동작한다.

트리 탐색으로 id = 1000 이 위치한 리프 페이지를 찾는다 (디스크 I/O ≈ 트리 높이).
리프의 next 포인터를 따라 id = 2000 이 나올 때까지 인접 페이지를 순차로 읽는다.

이 두 번째 단계가 결정적이다. 디스크는 인접 페이지를 한꺼번에 읽는 순차 I/O 가 랜덤 I/O보다 압도적으로 빠르다. HDD는 헤드 이동이 사라져 100배 차이가 나고, SSD에서도 NAND 채널 병렬화와 OS의 페이지 prefetch 덕에 5~10배 차이가 난다.

I/O 패턴	HDD	SSD
랜덤 4KB read	~10ms	~0.1ms
순차 1MB read	~10ms	~0.5ms
단위당 비용 차이	~250배	~50배

같은 6개 페이지를 디스크 위에 어떻게 두느냐 — 흩어진 배치 vs 인접 배치

테이블이 PK 순서로 정렬된 InnoDB의 Clustered Index에서, WHERE id > X ORDER BY id LIMIT N 같은 키셋 페이지네이션이 빠른 이유가 여기에 있다. 같은 쿼리를 정렬되지 않은 컬럼으로 돌리면 Bookmark Lookup이 끼어들면서 랜덤 I/O가 폭발한다.

SSD가 보편화된 지금도 B+Tree가 흔들리지 않는 이유는, 페이지 단위 정렬과 순차 I/O 친화성이 매체와 무관한 자료구조 차원의 이점이기 때문이다. NVMe SSD에서도 순차 read는 랜덤 read보다 여전히 한 자릿수 배 빠르다.