[데이터베이스] 인덱스(Index) 개념과 B-Tree / B+Tree 구조 및 장단점 완전 정리

컴퓨터공학과 데이터베이스 시험이나 백엔드 개발자 면접에서 "데이터베이스 탐색 성능을 향상시키는 핵심 원리"를 물어볼 때 빠짐없이 나오는 주제가 있습니다. 바로 인덱스(Index)와 이를 구현하는 B-Tree / B+Tree 자료구조입니다.

"인덱스는 무조건 많이 생성할수록 좋을까?"

"왜 RDBMS에서는 일반적인 Binary Search Tree 대신 B-Tree나 B+Tree를 사용할까?"

인덱스의 기본 개념부터 장단점, 그리고 시험 단골 서술/비교 문제로 나오는 B-Tree와 B+Tree의 결정적 차이점까지 완벽하게 정리해 드립니다!

1. 데이터베이스 인덱스(Index)란?

인덱스(Index)란 데이터베이스 테이블의 검색 속도를 향상시키기 위해 특정 컬럼의 값과 해당 레코드가 저장된 물리적 주소를 (Key, Value) 형태로 짝지어 구성한 색인 자료구조입니다.

책 맨 뒤에 있는 '찾아보기(색인)'를 생각하면 이해하기 쉽습니다. 책 전체를 처음부터 끝까지 읽지 않아도 원하는 키워드가 몇 페이지에 있는지 바로 찾아갈 수 있는 원리입니다.

💡 인덱스의 장점과 단점

구분	주요 특징 및 내용
장점	• 조회(SELECT) 속도 극대화: 테이블 전체를 탐색하는 Full Table Scan 대신 인덱스를 활용해 빠르게 검색 • 시스템의 전체적인 I/O 자원 소모 감소 및 JOIN, ORDER BY 속도 향상
단점	• 저장 공간 차지: 인덱스를 위한 추가적인 데이터베이스 용량이 필요 (보통 테이블 크기의 약 10%) • CUD 성능 저하: 데이터의 삽입(INSERT), 수정(UPDATE), 삭제(DELETE) 시 인덱스도 재정렬/갱신해야 하므로 오버헤드 발생

💡 시험 단골 포인트: 인덱스는 조회 성능을 대폭 높여주지만, INSERT, UPDATE, DELETE가 빈번하게 발생하는 테이블에 인덱스를 과도하게 생성하면 오히려 성능 저하를 일으킵니다.

2. B-Tree vs B+Tree 구조 비교

대부분의 RDBMS(MySQL의 InnoDB, PostgreSQL 등)는 인덱스 자료구조로 B-Tree 계열을 사용합니다. 자식이 최대 2개인 이진 탐색 트리(BST)와 달리, B-Tree는 하나의 노드가 여러 개의 자식을 가질 수 있는 다원 탐색 트리(Balanced Multi-way Tree)로, 디스크 I/O 횟수를 최소화하는 데 최적화되어 있습니다.

데이터 저장 위치와 리프 노드 연결성에 따른 B-Tree와 B+Tree 차이점. 출처: Unstop

1️⃣ B-Tree (Balanced Tree)

• 특징:
  • 모든 노드(루트, 브랜치, 리프)가 Key와 실제 데이터(또는 데이터 포인터)를 함께 저장합니다.
  • 원하는 Key를 루트 노드나 중간(브랜치) 노드에서 찾으면, 리프 노드까지 내려가지 않고 즉시 탐색을 종료할 수 있습니다.
• 단점:
  • 모든 노드에 데이터 포인터가 들어가므로, 한 노드 안에 담을 수 있는 Key의 개수가 적어져 트리의 높이가 높아질 수 있습니다.
  • 순차 탐색(Range Scan) 시 트리의 각 노드를 중위 순회(In-order Traversal)해야 하므로 비효율적입니다.

2️⃣ B+Tree

• 특징:
  • 오직 리프 노드(Leaf Node)에만 실제 데이터(또는 데이터 포인터)가 저장됩니다.
  • 루트 및 브랜치 노드는 리프 노드까지 찾아가기 위한 인덱스(Key) 역할만 수행합니다. (동일한 Key가 중복 존재할 수 있음)
  • 모든 리프 노드들이 연결 리스트(Linked List) 형태로 서로 이어져 있습니다.
• 장점:
  • 브랜치 노드에 데이터 포인터가 없으므로 더 많은 Key를 보관할 수 있어 트리의 높이가 낮아집니다. (디스크 I/O 감소)
  • 범위 검색(Range Scan)에 극도로 유리: 리프 노드의 연결 리스트를 따라 선형 탐색만 하면 되므로 부모 노드로 다시 올라갈 필요가 없습니다.
• 단점:
  • 어떤 Key를 찾더라도 무조건 리프 노드까지 내려가야 탐색이 완료됩니다.

3. 한눈에 끝내는 핵심 요약표 (★시험 필수)

구분	B-Tree	B+Tree
데이터 저장 위치	모든 노드 (루트/브랜치/리프)	오직 리프 노드(Leaf Node)
Key 중복 여부	중복 없음 (트리 내 단 1개)	브랜치와 리프 노드에 중복 존재 가능
리프 노드 연결성	연결되지 않음	연결 리스트(Linked List)로 연결됨
범위 탐색 (Range Scan)	비효율적 (트리 순회 필요)	매우 효율적 (리프 노드만 순차 탐색)
탐색 시간	Best Case는 빠르게 종료 가능	모든 검색이 리프까지 도달 (일정한 시간 복잡도)

4. 시험 단골 출제 유형 체크

1. Q. B-Tree와 비교했을 때 B+Tree가 범위 검색(Range Scan)에 훨씬 유리한 구조적 이유는?
2. 👉 모든 데이터가 리프 노드에만 저장되어 있고, 리프 노드끼리 연결 리스트(Linked List)로 이어져 있어 연속적인 순차 탐색이 가능하기 때문입니다.
3. Q. 인덱스를 무분별하게 많이 생성하면 안 되는 이유를 DML 연산 관점에서 설명하시오.
4. 👉 데이터 수정 연산(INSERT, UPDATE, DELETE)이 발생할 때마다 인덱스 트리를 재정렬하고 갱신해야 하는 추가 오버헤드가 발생하여 전체적인 시스템 성능이 저하되기 때문입니다.
5. Q. RDBMS에서 일반적인 이진 탐색 트리(BST) 대신 B-Tree 계열을 사용하는 결정적인 이유는?
6. 👉 하나의 노드에 여러 개 데이터를 담아 트리의 높이를 낮춤으로써, 속도가 느린 디스크 I/O(입출력) 횟수를 최소화하기 위함입니다.