(데이터베이스) B-Tree : 구조, 작동 원리, DB에서의 활용

불광동 물주먹 2025. 5. 31. 02:09

B-Tree : 구조, 작동 원리, DB에서의 활용

1. B-Tree란?

B-Tree는 **Binary Search Tree(이진 탐색 트리)**를 일반화한 트리 자료구조입니다. 데이터베이스와 파일 시스템 등, 디스크 기반의 저장 시스템에서 대량의 데이터를 효율적으로 검색, 삽입, 삭제할 수 있도록 설계된 구조입니다.

왜 B-Tree가 필요한가?

일반 이진 탐색 트리는 삽입 순서에 따라 한쪽으로 치우칠 수 있어 최악의 경우 O(n) 시간복잡도를 가집니다.
반면 B-Tree는 항상 균형을 유지하며, 트리의 높이를 제한해 모든 연산이 O(log n) 시간에 수행됩니다.
특히 디스크 I/O 비용이 큰 환경에서 적은 횟수의 블록 접근으로 원하는 데이터를 찾을 수 있도록 설계되었습니다.

2. B-Tree의 구조

기본 구성

M차 B-Tree: 하나의 노드가 최대 M개의 자식 노드를 가질 수 있는 트리
각 노드는 최대 M-1개의 key를 가짐 (key는 오름차순으로 정렬)
자식 노드 수는 항상 key 수 + 1
루트 노드를 제외한 모든 노드는 최소 ⌈M/2⌉개의 자식을 가져야 함

내부(internal) 노드 vs 리프(leaf) 노드

내부 노드: key와 자식 포인터 모두 가짐
리프 노드: key만 가지고 자식 포인터는 없음
모든 리프 노드는 같은 깊이에 위치하여 균형 트리를 유지함

Key와 자식의 관계

만약 어떤 노드가 key [K1, K2, K3]를 가진다면 자식 포인터는 [C0, C1, C2, C3]이며:

C0: key < K1
C1: K1 ≤ key < K2
C2: K2 ≤ key < K3
C3: K3 ≤ key

3. B-Tree 삽입 동작 (Insertion)

삽입 원칙

항상 리프 노드에 삽입
노드가 key 수 제한(M-1)을 넘으면 분할(split) 수행
가운데 key를 부모로 올려 보내고 승격(promote)
필요한 경우 재귀적으로 루트까지 분할

삽입 과정 예시 (3차 B-Tree)

삽입 순서: 10 → 20 → 5 → 6 → 12 → 30 → 7

1. 삽입 10      → [10]
2. 삽입 20      → [10, 20]
3. 삽입 5       → [5, 10, 20] → overflow
4. 분할         → 10 승격 → 루트 [10]
                   /      \
               [5]        [20]
5. 삽입 6       → [5,6], [20]
6. 삽입 12      → [5,6], [12, 20]
7. 삽입 30      → [5,6], [12, 20, 30] → overflow
   → 20 승격    → 루트 [10, 20]
                   /   |     \
              [5,6] [12]   [30]

아래 3차 Btree

아래 링크 Btree 삽입에 대한 예제를 아주 쉽고 자세히 다뤄주신 영상이 있어 링크를 걸어 뒀습니다.

영상 보시면 도움 많이 되실거라 확신합니다.

https://youtu.be/bqkcoSm_rCs?si=sW3-FFLHkS0btmpY

*출처 유튜브 쉬운코드

4. B-Tree 삭제 동작 (Deletion)

리프 노드 삭제

항상 리프에서 삭제
삭제 후 최소 key 수 미만이면 재조정 필요

재조정 방식

형제 노드에서 차용 (Redistribute)
→ 부모 키 하나 내려주고, 형제의 키 하나 올림
형제 노드와 병합 (Merge)
→ 형제 + 부모의 key와 병합 → 하나의 노드로 합쳐짐
→ 부모 노드도 key 수 감소 → 재귀적 조정

Internal 노드 삭제

Internal 노드의 key는 바로 삭제할 수 없음
반드시 leaf 노드로 위치를 바꾼 후 삭제

방법

삭제할 key의 전임자(predecessor) 또는 **후임자(successor)**를 찾아 위치를 교환
leaf에서 삭제한 후 필요 시 재조정

아래는 Btree 삭제 예제 영상입니다.

https://youtu.be/H_u28u0usjA?si=fout_w1jeiT3OavS

*출처 유튜브 - 쉬운코드

5. B-Tree의 성능

연산	시간복잡도
탐색	O(log N)
삽입	O(log N)
삭제	O(log N)

→ 왜? 트리의 높이가 log N 수준으로 유지되기 때문
→ 디스크 기반 환경에서는 한 노드 = 한 디스크 블록 → I/O 횟수 최소화

6. 데이터베이스에서 B-Tree가 중요한 이유

디스크 친화적 구조

B-Tree의 노드는 보통 하나의 디스크 페이지에 맞도록 구성됨
트리 높이를 낮게 유지하므로 **디스크 접근 횟수(I/O)**가 적음

정렬된 Key 유지

키가 항상 오름차순으로 유지되므로, **범위 검색(RANGE SCAN)**이 매우 효율적
예:

SELECT * FROM users WHERE age BETWEEN 20 AND 30;

CRUD 연산의 성능 보장

대용량 테이블에서도 검색, 삽입, 삭제 모두 안정적으로 빠름
트랜잭션이 많은 OLTP 환경에 최적

7. B-Tree vs B+Tree

항목	B-Tree	B+Tree
키 저장 위치	Internal 노드 + Leaf 노드	Leaf 노드에만 저장
범위 검색 성능	Internal → Leaf 순회 필요	Leaf 노드 간 연결 리스트로 빠르게 순차 탐색
데이터 저장 위치	노드마다 저장 가능	Leaf 노드에만 실제 데이터 저장
대부분의 DB에서 사용	❌ 일부 옛날 DB	✅ 대부분의 RDBMS 인덱스 구조

✅ B+트리를 많이 쓰는 이유 (요약)

이유	설명
1. 범위 조회에 최적화	리프 노드가 순차 연결되어 있어 BETWEEN, ORDER BY, LIKE 등에서 효율적
2. 구조가 단순함	모든 데이터가 리프 노드에만 있어 삽입/삭제 로직이 일관되고 단순
3. 디스크 I/O 최적화	내부 노드는 인덱스 역할만 하므로 한 블록에 더 많은 키를 저장 → 높이 작고 빠름

8. 결론 및 요약

B-Tree는 대용량 데이터 환경에서 빠른 검색과 수정을 지원하는 균형 트리 구조
모든 노드는 자식 수 제한을 지키면서 트리 전체 균형을 유지
삽입과 삭제 시 재조정 로직이 복잡하지만 그 덕분에 트리 높이가 낮게 유지
디스크 기반 시스템, 특히 RDBMS의 인덱스 구현에 기초가 되는 자료구조
실제 RDBMS는 대부분 B-Tree를 변형한 B+Tree를 사용함

추후엔 B+Tree에 대해 다뤄보겠습니다.