B-트리 vs B+트리, 언제 무엇이 유리할까?

목차

1. B-트리 특징/장단점
2. B+트리 특징/장단점
3. 언제 B-트리가 유리할까?
4. 왜 데이터베이스는 B+트리를 쓸까?
5. 실제 사례 비교 (MySQL ↔ Redis)
6. 요약

---

1. B-트리 특징/장단점

B트리 (출처: https://rebro.kr/169)

 

• 특징
  - 모든 노드(내부 + 리프)에 데이터 저장
• 장점
  - 중간 노드에서 바로 데이터를 찾을 수 있어 단일 검색 속도 빠름
  - 메모리 사용 효율 높음 (리프만 따로 두지 않음)
  - 작은 데이터셋이나 메모리 기반 구조에 적합
• 단점
  - 리프 노드들이 연결되어 있지 않아 범위 검색 비효율적

---

2. B+트리 특징/장단점

B+트리 (출처: https://ajroot5685.github.io/posts/B+-Tree/)

• 특징
  - 내부 노드는 인덱스만, 데이터는 리프 노드에만 저장
  - 리프 노드들이 연결 리스트로 연결됨
• 장점
  - 범위 검색 / 순차 탐색 최적화
  - 내부 노드에 더 많은 키 저장 가능 → 트리 높이가 낮아짐
  - 대규모 데이터·디스크 기반(DB, 파일시스템 인덱스)에 최적
• 단점
  - 항상 리프까지 내려가야 하므로 단일 검색 속도는 B-트리보다 살짝 불리

---

3. 언제 B-트리가 유리할까?

1. 범위 검색보다는 단일 키 조회 위주일 때

• B-트리는 내부 노드에도 데이터를 저장합니다.
• 따라서 원하는 키가 내부 노드에 존재한다면, 리프까지 내려가지 않고 바로 조회할 수 있습니다.
• 반면 B+트리는 반드시 리프까지 내려가야 하므로, 단일 조회 성능은 상대적으로 불리합니다.
• 따라서 단건 조회 성능을 극대화하려면 B-트리가 더 낫습니다.

 

2. 데이터 크기가 작고 메모리에서 동작할 때 (= 데이터 접근 속도가 빠른 경우)

하드디스크 구성 (출처: https://colddesert078.tistory.com/119)

• B+트리는 Arm을 통해 Head를 움직이는 하드디스크에서 유리합니다. (리프 노드 연결 → 순차 접근 최적화)
• 하지만 메모리(RAM)에서는 랜덤 접근 자체가 빠르기 때문에 B+트리의 장점이 희석됩니다. (메모리는 디스크와달리 전자기적 신호로 데이터를 접근하기 때문에 디스크 I/O 최적화를 신경 쓸 필요 없음)
• 게다가 B+트리는 내부 노드와 리프 노드를 분리해 관리해야 하므로, 작은 데이터셋을 메모리에서 다룰 때는 오히려 불필요한 관리 오버헤드가 생길 수 있습니다.
• 따라서 메모리 기반의 소규모 데이터 처리에는 구조가 단순한 B-트리가 더 효율적입니다.
  

---

4. 왜 데이터베이스는 B+트리를 쓸까?

오늘날 데이터베이스(DB)는 거의 모두 B+트리 기반 인덱스를 사용합니다. 이유는 다음과 같습니다.

 

1. 범위 검색과 순차 접근에 최적화 / 디스크 페이지와 잘 맞는 구조

• B-트리는 리프 노드들이 연결돼 있지 않아서 범위 검색 시 키마다 별도 탐색이 필요합니다.
• 반면 B+트리는 리프 노드가 연결 리스트로 이어져 있어, WHERE id BETWEEN 10 AND 100 같은 쿼리를 처리할 때 시작점만 찾으면 순차적으로 데이터를 빠르게 읽을 수 있습니다.
• 또한 데이터가 리프 노드에 모여 있고 연속적으로 배치되므로, DB가 디스크 페이지 단위로 데이터를 읽을 때 인접 데이터까지 한 번에 가져올 수 있어 I/O 효율이 높습니다.

2. 트리 높이를 줄여 디스크 I/O 최소화

• B-트리는 내부 노드에도 데이터를 저장해야 하므로, 같은 페이지 크기에서는 담을 수 있는 키 개수가 적습니다.
• B+트리는 내부 노드에 키만 저장하기 때문에 더 많은 키를 넣을 수 있고, 결과적으로 트리의 높이가 낮아집니다.
• 트리 높이가 낮아진다는 건 곧 디스크 접근 횟수가 줄어든다는 뜻이므로 DB 성능에 큰 이점이 됩니다.

3. SQL 쿼리 패턴과 잘 맞음

• ORDER BY, GROUP BY는 인덱스 정렬 상태를 그대로 활용할 수 있습니다.
• JOIN에서는 정렬된 키를 활용해 머지 조인(Merge Join) 같은 최적화가 가능합니다.
• B-트리는 이런 활용도가 떨어지기 때문에, 실제 SQL 실행 계획에서 인덱스 효율성이 낮습니다.

4. 대규모 데이터셋에 강함

• 수백만~수억 건 이상의 데이터셋에서는 단건 조회보다 범위 검색, 정렬, 조인이 훨씬 더 자주 발생합니다.
• B+트리는 이러한 워크로드에 맞춰 설계돼 있기 때문에 대규모 디스크 기반 DB 환경에서 사실상 표준이 되었습니다.

---

5. 실제 사례 비교 (MySQL ↔ Redis)

MySQL (InnoDB)

• 인덱스 구조: 일반적으로 B+트리 사용
• 이유: 대규모 데이터, 범위 검색 쿼리 많음, 디스크 I/O 최적화 필요
• 예: WHERE, ORDER BY, BETWEEN 쿼리 등

 

Redis

• 인덱스 구조: Skip List + Hash Table (B-트리/ B+트리 계열 아님)
• 이유
  - Redis는 완전히 메모리 기반 DB이므로 디스크 I/O 최적화가 필요 없음
  - B+트리의 장점(범위 검색·페이지 단위 I/O 최적화)은 메모리 환경에서는 불필요
  - 대신 더 단순하고 캐시 친화적인 자료구조(Skip List, Hash Table, Red-Black Tree 등)가 훨씬 효율적 
• 구현 예시
  - ZSet(Sorted Set) 내부는 Skip List + Hash Table로 구성
  - ZRANGEBYSCORE, ZRANGEBYLEX 같은 범위 검색 명령어 지원
• 정리
  - Redis는 범위 검색도 지원하지만, B-트리/B+트리 대신 Skip List로 구현합니다.
  - Skip List는 구조가 단순하고, 메모리 효율, 구현 난이도가 B트리 계열보다 유리하기 때문입니다.

 

실제 데이터베이스 환경에서는 범위 검색과 정렬 쿼리가 필수적이고, 디스크 I/O를 최소화하는 것이 핵심 과제이기 때문에 B+트리가 선택됩니다.

반면에, 단일 조회나 메모리 기반의 소규모 데이터는 B-트리가 유리할 수 있습니다.
하지만, 메모리 기반 환경에서는 디스크 I/O 최소화 작업 자체가 아예 불필요하고, Hash Table, Skip List, Red Black Tree 같은 더 단순하고 빠른 대안이 있기 때문에, 현대 산업 현업에서는 사실상 B-트리를 찾아보기 어렵습니다.

---

6. 요약

B-트리 vs B+트리 비교

구분	B-트리	B+트리
데이터 저장	모든 노드(내부 + 리프)에 데이터 저장	내부 노드는 키만 저장, 데이터는 리프 노드에만 저장
단일 조회	중간 노드에서도 바로 조회 가능 → 단일 조회 빠름	항상 리프까지 내려가야 함 → 단일 조회는 B-트리보다 느림
범위 검색 / 순차 접근	리프 노드 간 연결이 없어 비효율적	리프 노드가 연결 리스트로 이어져 있어 범위 검색 최적화
트리 높이	같은 크기의 노드에 저장할 수 있는 키 수가 적음 → 트리 높이 상대적으로 큼	내부 노드에 더 많은 키 저장 가능 → 트리 높이 낮음
I/O 효율성	메모리 기반 소규모 데이터에 적합	디스크 페이지 단위 I/O 최적화 → 디스크 기반 환경에 유리
적합한 환경	작은 데이터셋, 메모리 기반, 단일 검색 위주	대규모 데이터셋, 디스크 기반 DB·파일시스템 (사실상 표준)

 

실제 사례 비교 (Redis ↔ MySQL)

구분	MySQL (InnoDB)	Redis
인덱스 구조	일반적으로 B+트리 사용	Skip List + Hash Table (B-트리/B+트리 계열 아님)
환경	디스크 기반 RDBMS	완전히 메모리 기반 DB
이유	- 대규모 데이터셋 처리 - 범위 검색 쿼리 많음 - 디스크 I/O 최적화 필요	- 디스크 I/O 최적화 불필요 - 메모리 친화적이고 단순한 자료구조가 더 효율적
구현 예시	인덱스 조회: WHERE, ORDER BY, BETWEEN 등 SQL 쿼리	ZSet 내부 구현: Skip List + Hash Table → ZRANGEBYSCORE, ZRANGEBYLEX 지원