B-Trees

Posted: 2026-04-13 Tags: cs datastructure

contents

현대 데이터베이스의 절대적인 중추에 오신 것을 환영합니다. MySQL, PostgreSQL, Oracle, SQLite를 사용해 본 적이 있다면, 여러분은 이미 B-트리(B-Tree) 를 사용하신 겁니다.

B-트리를 이해하려면 먼저 AVL이나 레드-블랙 트리가 데이터베이스에서 왜 실패 하는지 이해해야 합니다.

1. 문제점: "디스크 I/O" 병목 현상

AVL과 레드-블랙 트리는 엄격한 이진(Binary) 트리(노드당 최대 자식 2개)입니다. 모든 데이터가 RAM(메모리)에 있을 때는 믿을 수 없을 정도로 빠릅니다.

하지만 데이터베이스는 거대합니다. RAM에 다 들어가지 않기 때문에 하드 드라이브(또는 SSD) 에 저장됩니다.

RAM에서 데이터를 읽는 데는 나노초 단위가 걸립니다.
하드 드라이브에서 읽는 데는 밀리초 단위(10만 배나 더 느림!)가 걸립니다.

컴퓨터가 디스크에서 읽을 때는 한 번에 1바이트씩 읽지 않고, 메모리의 큰 "덩어리"나 "블록"(일반적으로 4KB 또는 8KB) 단위로 한꺼번에 읽습니다.

하드 드라이브에 이진 트리를 사용하면, 자식 노드로 향하는 포인터를 따라갈 때마다 숫자 하나를 읽기 위해 디스크에서 완전히 새로운 4KB 블록을 로드해야 합니다. 10억 개의 데이터가 있는 이진 트리의 높이는 약 30입니다. 즉, 행(row) 하나를 찾기 위해 끔찍하게 느린 디스크 읽기를 30번이나 수행해야 한다는 뜻입니다.

2. 해결책: B-트리 (넓고 얕게)

B-트리는 디스크 읽기를 최소화하기 위해 발명되었습니다. "이진(Binary)"(높고 좁은) 트리 대신, B-트리는 M-원(M-ary) 트리(짧고 믿을 수 없을 정도로 넓은) 형태를 띱니다.

하나의 노드에 단 하나 의 키만 넣는 대신, B-트리는 하나의 노드에 수백 개의 키를 쑤셔 넣어 4KB 디스크 블록 하나를 완벽하게 꽉 채웁니다.

디스크에서 B-트리 노드 하나를 로드하면 한 번의 읽기로 수백 개의 키를 가져옵니다. 10억 개의 데이터가 있는 B-트리의 높이는 고작 3 또는 4에 불과할 수 있습니다. 즉, 전체 데이터베이스에서 어떤 레코드를 찾든 디스크 읽기 3~4번이면 충분하다는 뜻입니다!

3. B-트리의 해부학 및 절대 규칙

B-트리는 차수(Order, $m$으로 표기) 에 의해 정의됩니다. 이 차수가 노드의 최대 용량을 결정합니다.

차수가 $m$인 B-트리의 엄격한 규칙은 다음과 같습니다:

최대 자식 수: 모든 노드는 최대 $m$개의 자식을 가질 수 있습니다.
최대 키 수: 모든 노드는 최대 $m-1$개의 키를 가질 수 있습니다. (예: 차수가 4라면 한 노드는 3개의 키를 가집니다).
정렬된 키: 단일 노드 내부의 키들은 엄격하게 오름차순으로 정렬되어 저장됩니다 (예: [10, 20, 30]).
최소 키 수 (절반 채우기 규칙): 공간 낭비를 막기 위해 (루트를 제외한) 모든 노드는 반드시 최소 절반 이상 채워져 있어야 합니다. 구체적으로는 최소 $\lceil m/2 \rceil - 1$개의 키를 가져야 합니다.
완벽하게 평평한 바닥: 모든 리프(Leaf) 노드는 정확히 같은 레벨에 존재해야 합니다. 트리의 맨 아래 바닥은 완벽하게 수평을 유지합니다.

4. 탐색 작동 원리

B-트리 탐색은 이진 트리 논리와 배열 논리를 결합한 것입니다.

[10, 20, 30]이 들어 있는 노드에서 25를 찾는다고 가정해 보겠습니다.

노드의 키들을 확인합니다. 25는 20과 30 사이에 있습니다.
두 번째와 세 번째 키 사이에 있으므로 세 번째 자식을 가리키는 포인터를 따라갑니다.
해당 자식 노드를 디스크에서 로드하고 25를 찾을 때까지 이 과정을 반복합니다.

5. 삽입 및 분할 작동 원리 (마법 같은 부분)

밑바닥에 리프를 추가하여 아래로 자라는 이진 탐색 트리와 달리, B-트리는 리프에서부터 위로(UPWARD) 자랍니다.

차수가 $m=4$인 B-트리(노드당 최대 3개의 키)에 숫자를 삽입해 보겠습니다.

10, 20, 30 삽입: 이들은 모두 루트 노드에 들어갑니다. 루트는 이제 [10, 20, 30]이 됩니다.
40 삽입 (오버플로우): 루트에 40을 넣으려 합니다: [10, 20, 30, 40]. 하지만 최대치는 3개입니다! 노드가 넘쳐흐릅니다(오버플로우).
분할 (The Split): 노드가 물리적으로 반으로 쪼개집니다.
- 중간 요소인 20이 위로(UP) 밀려 올라가 새로운 부모 노드가 됩니다.
- 왼쪽 요소들([10])은 왼쪽 자식이 됩니다.
- 오른쪽 요소들([30, 40])은 오른쪽 자식이 됩니다.
결과: 트리의 높이가 한 칸 커졌지만, 바닥에서부터 위로 밀어 올리면서 자라났습니다!

리프 노드가 넘쳐흐르면 중간 키를 부모로 밀어 올립니다. 그로 인해 부모까지 넘쳐흐르게 되면 부모도 쪼개지며 자신의 중간 키를 조부모에게 밀어 올립니다. 이 파도 효과(Ripple effect)는 루트까지 이어질 수 있으며, 이것이 B-트리의 높이가 커지는 유일한 방법입니다.

6. B-트리 vs B+ 트리 (데이터베이스 표준)

현대의 데이터베이스(MySQL의 InnoDB 등)는 사실 B+ 트리라는 약간 변형된 버전을 사용한다는 점을 알아두는 것이 중요합니다.

B-트리: 실제 데이터(데이터베이스의 행(row) 등)를 모든 노드(루트, 내부 노드, 리프 노드)에 저장합니다.
B+ 트리: 실제 데이터는 오직 리프 노드에만 저장합니다. 내부 노드는 오직 라우팅(길잡이)을 위한 "표지판" 키만 가지고 있습니다. 게다가 모든 리프 노드들이 연결 리스트처럼 서로 연결되어 있어서 범위 검색(Range Queries, 예: SELECT * WHERE age BETWEEN 20 AND 30)이 엄청나게 빠릅니다.

references