(데이터베이스) B-Tree와 데이터베이스 인덱스

B-Tree와 데이터베이스 인덱스

1. B-Tree의 시간 복잡도

B-Tree는 self-balancing 트리로, 다음과 같은 시간 복잡도를 가진다:

• 탐색 (Search): O(logₙ N)
• 삽입 (Insert): O(logₙ N)
• 삭제 (Delete): O(logₙ N)

여기서 N은 전체 키의 수, n은 자식 노드의 수(= branching factor)이다.
즉, 자식 수가 많을수록 log의 밑이 커지므로 깊이가 얕아지고 탐색 횟수가 줄어든다.

예시:

• 자식 노드 수가 100일 경우, 1억 개의 키를 탐색할 때 최대 4단계만으로도 검색 가능.

---

2. Secondary Storage의 특징

하드디스크(HDD) 또는 SSD와 같은 보조 기억장치(Secondary Storage)는 다음과 같은 특징을 가진다:

• 접근 속도는 RAM보다 훨씬 느림 (ms 단위 vs ns 단위)
• 용량은 크지만, 접근 비용이 높음
• 데이터를 'block 단위'로 읽고 씀
  • 1 block = 4KB, 8KB, 16KB 등이 일반적
  • 실제로 필요한 데이터가 100바이트여도, 4KB 전체 블록을 읽음
  • 따라서 디스크 I/O의 최소 단위는 block

데이터베이스에서 성능을 높이기 위해서는, 가능한 적은 I/O 횟수로 많은 데이터를 처리하는 구조가 중요하다.

---

3. 왜 DB 인덱스로 B-Tree 계열이 사용되는가?

1) I/O 효율성

• B-Tree는 한 노드에 여러 key-value를 저장하므로, 하나의 디스크 블록에 여러 키가 포함됨
• AVL, Red-Black Tree 등은 메모리 기반이라 노드당 키 하나 -> I/O 낭비 심함
• B-Tree는 디스크의 block 단위 읽기에 최적화되어 있음

2) 트리의 낮은 깊이 (shallow depth)

• branching factor가 크기 때문에, 트리의 높이가 낮고 루트에서 리프까지 탐색 경로가 짧음
• 디스크 접근 횟수 줄어듦 (예: 수천만 건도 3~4단계면 조회 가능)

3) 정렬성과 범위 검색

• B-Tree는 키가 정렬된 상태로 저장됨
• 따라서 범위 조건 (WHERE age BETWEEN 20 AND 30)을 매우 빠르게 처리 가능
• 반면, 해시 인덱스는 = 조건만 가능하며 범위 검색 불가

---

4. B-Tree vs AVL / Red-Black Tree

기준	B-Tree	AVL / Red-Black Tree
목적	디스크 기반 탐색	메모리 기반 탐색
자식 수	다수 (m-way)	2개
노드당 키 수	다수	1개
트리 깊이	얕음	상대적으로 깊음
I/O 비용	매우 낮음	높음
범위 검색	O(logN) + O(K)	O(N) 전체 탐색 필요

 

결론: B-Tree는 디스크의 I/O 특성을 반영하여 설계되었고, 실제 저장되는 데이터 구조와 블록 읽기 방식이 맞물려 고성능을 낼 수 있다.

 

 

사진 출처 - 유튜브 쉬운코드

 

 

사진 출처 - 유튜브 쉬운코드

 

 

 

 

5. B+Tree: 실제 DB에서 사용되는 인덱스 구조

실제로 대부분의 RDBMS (Oracle, MySQL, PostgreSQL 등)는 B+Tree 구조를 인덱스로 사용한다.
B-Tree의 확장 버전으로, 다음과 같은 특징이 있다:

B+Tree의 특징

• 내부 노드는 키만 저장 (데이터 없음)
• 리프 노드만 실제 데이터의 포인터 보유
• 리프 노드끼리 연결 리스트로 연결되어 있음 → 범위 검색 및 정렬이 빠름
• 인덱스 스캔 시, 리프 노드부터 순차적으로 이동 가능

• b-tree 와의 가장 큰 차이점은 리프노드가 아닌 노드(Internal Node)에 데이터가 아닌 주소(인덱스)가 들어가있다는 것이다.
• 데이터들은 리프노드에만 들어있다.

[장점]

• internal node에서 데이터를 저장하지 않으므로 블럭 사이즈를 더 많이 이용할 수 있다.
  b tree의 internal node : 데이터 + 자식 노드 포인터,  b+ tree의 internal node : 자식 노드 포인터
• 리프노드끼리 연결 리스트로 연결되어 있어서 순차 탐색과 범위 탐색에 매우 유리하다.

 

[단점]

• b tree는 최상 케이스의 경우 루트 노드에서 끝나 O(1) 이 될 수 있지만 b+ tree는 무조건 리프노드까지 내려가봐야 한다.

즉, B+Tree는 검색뿐 아니라 정렬된 데이터를 빠르게 탐색하거나 범위 스캔하는 데 최적화되어 있다.

---

6. Hash Index와의 비교

 

기준	B+Tree Index	Hash Index
시간 복잡도	O(logN)	O(1)
지원 조건	=, <, >, BETWEEN 등 범위 검색	= (equality)만
정렬	가능	불가능
범위 탐색	효율적	불가능
대표 사용처	대부분의 인덱스	메모리 캐시 또는 단일 키 검색 최적화

 

MySQL에서 Memory 엔진은 hash 인덱스를 사용하고, InnoDB는 기본적으로 B+Tree를 사용함

---

7. 실무 관점에서의 주의점

• B-Tree는 insert/delete 시에도 균형을 유지해야 하므로 오버헤드가 존재
• 중복된 값이 많거나, 너무 많은 쓰기 연산이 발생하는 컬럼은 인덱스 관리 비용이 큼
• 잘못된 인덱스 설계는 오히려 성능을 저하시킬 수 있음
  → 예: 자주 사용되지 않는 컬럼에 인덱스를 걸면 오히려 I/O 부담만 증가

---

결론

• B-Tree는 disk I/O 특성에 맞춰 설계된 고성능 탐색 트리
• DB 인덱스로 가장 널리 사용되며, 대부분 B+Tree 형태로 구현
• hash index는 특수한 조건(= 조회, 캐시 용도)에서만 유리
• 효율적인 인덱스 설계를 위해서는 쿼리 패턴, 데이터 분포, I/O 구조까지 고려해야 한다.