한양과기고 에듀테크 수업도구 대시보드

디스크 접근 횟수를 줄이려고 "넓고 얕게" 자라는 트리

이진 탐색 트리는 노드마다 자식이 2개뿐이라 데이터가 많아지면 깊이가 깊어진다. 디스크는 한 번 읽을 때 블록 단위(4KB, 16KB…)로 읽으므로, 노드 하나에 여러 개의 키를 욱여넣어 자식을 수십~수백 갈래로 늘리면 훨씬 얕은 트리로 같은 데이터를 담을 수 있다. 그게 B-Tree다. 실제 DB 인덱스, 파일시스템은 대부분 이 구조(정확히는 변형인 B+Tree)를 쓴다.

1 핵심 규칙 4가지 (최소 차수 t)

키 개수

루트가 아닌 노드는 키를 t-1 ~ 2t-1개 갖는다. 너무 비지도, 너무 차지도 않게 유지.

자식 개수

내부 노드의 자식 수는 키 개수 + 1개. 키가 많을수록 자식(분기)도 많아진다.

같은 깊이

모든 리프는 항상 같은 깊이에 있다 — 회전 없이도 트리가 저절로 완벽 균형을 이룬다.

분할(Split)

노드가 꽉 차서(2t-1개) 하나 더 들어오면, 가운데 키를 부모로 올리고 둘로 쪼갠다.

2 직접 만들어 보는 B-Tree

최소 차수 t

트리가 비어 있다. 숫자를 넣어 루트부터 만들어 보자.

노드 수: 0 키 개수: 0 트리 높이: 0 누적 분할 횟수: 0

💡 파란 굵은 테두리는 방금 분할이 일어난 노드, 초록 테두리는 탐색 경로다. 차수 t를 올리면(예: 4) 노드 하나가 키를 최대 7개까지 담아 분할이 훨씬 뜸하게 일어나고 트리가 더 얕아지는 것을 확인할 수 있다. 차수를 바꾸면 트리는 초기화된다.

# 노드가 꽉 찼으면(2t-1개) 미리 쪼개면서 내려가는 방식 (CLRS 표준 삽입) def insert(tree, key): if len(tree.root.keys) == 2*t - 1: new_root = Node(leaf=False, children=[tree.root]) split_child(new_root, 0) # 루트가 꽉 찼으면 루트부터 쪼갠다 → 높이 +1 tree.root = new_root insert_nonfull(tree.root, key) def split_child(parent, i): child = parent.children[i] mid_key = child.keys[t - 1] # 가운데 키 right = Node(leaf=child.leaf, keys=child.keys[t:]) # 오른쪽 절반 child.keys = child.keys[:t - 1] # 왼쪽(= 원래 노드)은 절반만 남김 if not child.leaf: right.children = child.children[t:] child.children = child.children[:t] parent.keys.insert(i, mid_key) # 가운데 키는 부모로 승격 parent.children.insert(i + 1, right)

3 분할(Split)이 일어나는 순간

분할 전 — 꽉 찬 노드(t=2, 최대 3키)

[ 10 | 20 | 30 ]  ← 4번째 키 25 도착

분할 후 — 가운데 키가 부모로 승격, 나머지는 반씩

        [ 20 ]              ← 부모로 승격
       /      \
 [ 10 ]      [ 25 | 30 ]     ← 왼쪽 / 오른쪽 절반

분할은 자식 개수만 하나 늘릴 뿐 모든 리프의 깊이를 똑같이 유지한다. AVL 트리처럼 "기울어짐"을 측정해 회전하는 게 아니라, 노드가 넘치면 그 자리에서 즉시 쪼개는 것만으로 균형이 저절로 맞춰진다.

4 성능 — 왜 디스크에 유리한가

O(log_t n)

검색·삽입·삭제
t가 클수록 더 얕아짐

1 노드 = 1 블록

디스크 I/O 1번에
키 수십~수백 개 확인

3~4단계

실제 DB에서
수백만 행도 이 정도 깊이

5 자주 나오는 질문

💡 이진 탐색 트리(BST)나 AVL 트리로는 안 되나?

메모리에서는 된다. 하지만 데이터가 디스크에 있으면 얘기가 다르다. 노드 하나 읽는 데 디스크 접근 1번(수 ms)이 걸리는데, 이진 트리는 자식이 2개뿐이라 100만 개를 담으려면 깊이가 log₂ 1,000,000 ≈ 20단계나 된다. B-Tree는 노드 하나에 수백 개의 키를 담아 자식을 수백 갈래로 늘려서, 같은 데이터를 3~4단계만에 도달하게 만든다. "느린 디스크 접근 횟수"를 최소화하는 게 핵심이다.

💡 실제 DB(MySQL, PostgreSQL)는 진짜 이 구조를 그대로 쓰나?

정확히는 B+Tree 변형을 쓴다. 차이는: (1) 실제 데이터는 리프에만 저장하고 내부 노드는 리프로 가는 이정표(키)만 들고 있다. (2) 모든 리프 노드끼리 연결 리스트로 연결돼 있어서, 범위 검색(WHERE age BETWEEN 20 AND 30)을 할 때 트리를 다시 안 타고 리프를 옆으로 쭉 훑을 수 있다. 이 데모의 B-Tree는 개념 이해용 원형이고, B+Tree는 여기서 한 걸음 더 나아간 실전형이다.

💡 삭제할 때는 어떻게 되나?

삽입의 반대 원리다. 노드의 키가 최소 개수(t-1개) 아래로 내려가려 하면, 이웃 형제한테서 키를 하나 빌려오거나(rotate), 그것도 안 되면 형제와 합쳐버린다(merge). 분할이 "위로 올라가며 쪼개는" 연산이라면, 병합은 "위에서 내려오며 합치는" 연산이라고 볼 수 있다. 이 데모는 개념을 보여주는 데 집중해 삽입·탐색만 지원한다.