Balanced Tree - Self-balancing Tree Data Structure
B-Tree는 균형 다방향 탐색 트리로, 데이터베이스 인덱스의 핵심 자료구조입니다. 모든 리프 노드가 동일한 깊이를 유지하여 O(log n) 성능을 보장하며, 디스크 I/O를 최적화하기 위해 한 노드에 여러 키를 저장합니다. MySQL, PostgreSQL 등 모든 RDBMS의 기반이 됩니다.
B-Tree의 탄생과 설계 철학 - 1970년 Rudolf Bayer와 Edward McCreight가 발명한 B-Tree는 "Balanced"의 B를 따서 명명되었습니다(또는 Bayer의 B). 메인 메모리보다 훨씬 느린 디스크 접근을 최소화하기 위해 설계되었으며, 한 번의 디스크 읽기로 여러 키를 비교할 수 있어 탐색 효율이 높습니다.
B-Tree vs B+Tree - 실제 데이터베이스는 대부분 B+Tree를 사용합니다. B+Tree는 모든 데이터가 리프 노드에만 저장되고, 리프 노드끼리 연결 리스트로 연결됩니다. 이 구조는 범위 쿼리(BETWEEN, ORDER BY)에서 압도적으로 유리합니다. 내부 노드는 라우팅용 키만 포함하여 더 많은 자식을 가질 수 있습니다.
차수(Order)와 구조 - B-Tree의 차수 m은 각 노드가 가질 수 있는 최대 자식 수입니다. 각 노드는 최소 ⌈m/2⌉개의 자식을 가져야 하며, 최대 m-1개의 키를 저장합니다. 예를 들어 차수 4인 B-Tree는 2-4개의 자식과 1-3개의 키를 가집니다. 데이터베이스에서는 보통 수백~수천의 차수를 사용합니다.
삽입과 분할(Split) - 새 키를 삽입할 때 노드가 가득 차면 중간값을 기준으로 둘로 분할합니다. 중간 키는 부모로 올라가고, 이 과정이 루트까지 전파될 수 있어 트리 높이가 증가합니다. 삭제 시에는 반대로 병합(Merge)이 일어납니다.
데이터베이스에서의 활용 - InnoDB의 클러스터드 인덱스(Primary Key)는 B+Tree로 데이터를 직접 저장하고, 세컨더리 인덱스는 Primary Key를 참조합니다. PostgreSQL의 기본 인덱스도 B-Tree이며, CREATE INDEX 시 기본 적용됩니다. 인덱스 크기, 페이지 분할, 버퍼 풀 등이 성능의 핵심입니다.
# B-Tree 핵심 개념 구현 (교육용)
from dataclasses import dataclass, field
from typing import List, Optional
@dataclass
class BTreeNode:
"""B-Tree 노드"""
keys: List[int] = field(default_factory=list)
children: List['BTreeNode'] = field(default_factory=list)
is_leaf: bool = True
class BTree:
"""
B-Tree 구현
- 차수 t: 각 노드는 t-1 ~ 2t-1개의 키를 가짐
"""
def __init__(self, t: int = 2):
self.t = t # 최소 차수
self.root = BTreeNode()
def search(self, key: int, node: BTreeNode = None) -> Optional[tuple]:
"""키 검색: O(log n)"""
if node is None:
node = self.root
i = 0
while i < len(node.keys) and key > node.keys[i]:
i += 1
if i < len(node.keys) and key == node.keys[i]:
return (node, i)
if node.is_leaf:
return None
return self.search(key, node.children[i])
def insert(self, key: int):
"""키 삽입: O(log n)"""
root = self.root
if len(root.keys) == 2 * self.t - 1:
new_root = BTreeNode(is_leaf=False)
new_root.children.append(self.root)
self._split_child(new_root, 0)
self.root = new_root
self._insert_non_full(self.root, key)
def _split_child(self, parent: BTreeNode, idx: int):
"""자식 노드 분할 (핵심 연산)"""
t = self.t
full_child = parent.children[idx]
new_child = BTreeNode(is_leaf=full_child.is_leaf)
mid_key = full_child.keys[t - 1]
new_child.keys = full_child.keys[t:]
full_child.keys = full_child.keys[:t - 1]
if not full_child.is_leaf:
new_child.children = full_child.children[t:]
full_child.children = full_child.children[:t]
parent.keys.insert(idx, mid_key)
parent.children.insert(idx + 1, new_child)
def _insert_non_full(self, node: BTreeNode, key: int):
"""가득 차지 않은 노드에 삽입"""
i = len(node.keys) - 1
if node.is_leaf:
node.keys.append(None)
while i >= 0 and key < node.keys[i]:
node.keys[i + 1] = node.keys[i]
i -= 1
node.keys[i + 1] = key
else:
while i >= 0 and key < node.keys[i]:
i -= 1
i += 1
if len(node.children[i].keys) == 2 * self.t - 1:
self._split_child(node, i)
if key > node.keys[i]:
i += 1
self._insert_non_full(node.children[i], key)
# 사용 예제
if __name__ == "__main__":
btree = BTree(t=3)
for key in [10, 20, 5, 6, 12, 30, 7, 17]:
btree.insert(key)
# 검색
result = btree.search(12)
print(f"12 검색: {'발견' if result else '없음'}")
# 시간 복잡도
print("\nB-Tree 시간 복잡도:")
print("- 검색: O(log n)")
print("- 삽입: O(log n)")
print("- 삭제: O(log n)")
-- B-Tree 인덱스 활용 SQL
-- ============================================
-- 1. 인덱스 생성 (B-Tree가 기본)
-- ============================================
-- 단일 컬럼 인덱스
CREATE INDEX idx_users_email ON users(email);
-- 복합 인덱스 (왼쪽부터 순서대로 사용됨)
CREATE INDEX idx_orders_composite
ON orders(customer_id, order_date DESC, status);
-- 커버링 인덱스 (테이블 접근 없이 해결)
CREATE INDEX idx_products_covering
ON products(category_id, price, name);
-- ============================================
-- 2. 인덱스 사용 최적화
-- ============================================
-- ✅ 좋은 예: 인덱스 사용
SELECT * FROM users WHERE email = 'user@example.com';
SELECT * FROM orders WHERE customer_id = 100;
SELECT * FROM orders
WHERE customer_id = 100 AND order_date > '2024-01-01';
-- ❌ 나쁜 예: 인덱스 미사용
SELECT * FROM users WHERE LOWER(email) = 'user@example.com';
SELECT * FROM orders WHERE status = 'shipped';
SELECT * FROM products WHERE name LIKE '%phone%';
-- ============================================
-- 3. 클러스터드 vs 세컨더리
-- ============================================
CREATE TABLE orders (
id BIGINT PRIMARY KEY AUTO_INCREMENT, -- 클러스터드
customer_id INT,
order_date DATETIME,
INDEX idx_customer (customer_id) -- 세컨더리
);
-- ============================================
-- 4. 인덱스 통계 확인
-- ============================================
-- MySQL
SHOW INDEX FROM orders;
-- PostgreSQL
SELECT indexrelname, idx_scan, idx_tup_read
FROM pg_stat_user_indexes
WHERE schemaname = 'public';
-- EXPLAIN으로 B-Tree 인덱스 사용 분석
-- ============================================
-- 1. MySQL EXPLAIN
-- ============================================
EXPLAIN SELECT * FROM orders
WHERE customer_id = 100 AND order_date > '2024-01-01';
/*
확인 항목:
- type: const, ref, range (좋음) / ALL (나쁨)
- key: 사용된 인덱스 이름
- rows: 예상 스캔 행 수
- Extra: Using index (커버링 인덱스)
*/
-- ============================================
-- 2. PostgreSQL EXPLAIN ANALYZE
-- ============================================
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE customer_id = 100;
/*
Index Scan using idx_orders_customer
(cost=0.43..8.45 rows=1)
(actual time=0.015..0.017 rows=1)
Buffers: shared hit=3
*/
-- ============================================
-- 3. 인덱스 힌트
-- ============================================
-- MySQL: 특정 인덱스 강제 사용
SELECT * FROM orders
USE INDEX (idx_orders_customer)
WHERE customer_id = 100;
-- 인덱스 제외
SELECT * FROM orders
IGNORE INDEX (idx_orders_date)
WHERE order_date > '2024-01-01';
"이 쿼리가 느린 이유는 B-Tree 인덱스 선택도가 너무 낮아서예요. status 컬럼은 값이 3개뿐이라 전체의 33%를 스캔해요. 복합 인덱스로 customer_id를 앞에 두면 B-Tree가 훨씬 효율적으로 탐색할 겁니다."
"ORDER BY id DESC LIMIT 10인데 왜 filesort가 생기죠? Primary Key가 B+Tree니까 역순 스캔도 빠를 텐데... 아, WHERE 조건 때문에 세컨더리 인덱스 타고 Primary Key 찾는 거네요. 커버링 인덱스로 해결합시다."
"UUID를 Primary Key로 쓰면 B-Tree에서 문제가 생겨요. 랜덤한 값이라 삽입할 때마다 페이지 분할이 빈번해요. ULID나 Snowflake ID를 쓰면 B-Tree 오른쪽에만 삽입되어 분할이 최소화됩니다."
WHERE YEAR(created_at) = 2024는 인덱스를 사용하지 못합니다. WHERE created_at >= '2024-01-01'로 작성하세요.
INDEX(a, b, c)에서 b만으로는 검색 불가합니다. 가장 자주 쓰는 컬럼을 앞에 배치하세요.
INSERT/UPDATE마다 모든 인덱스의 B-Tree를 수정해야 합니다. 사용되지 않는 인덱스를 정리하세요.
B-Tree는 접두사 기반 정렬입니다. 전문검색이 필요하면 Full-Text Index를 사용하세요.