인덱스 완전 정복 — B+Tree 구조부터 실행 계획 읽기까지

인덱스, 왜 필요한가요?

테이블에 100만 행이 있다고 가정합니다. WHERE name = '김철수'를 인덱스 없이 실행하면 어떻게 될까요?

DB는 첫 번째 행부터 마지막 행까지 하나씩 비교합니다
이것을 풀 테이블 스캔(Full Table Scan) 이라고 합니다
데이터가 늘어날수록 조회 시간이 선형으로 증가합니다

인덱스는 책의 목차와 같습니다. 목차 없이 원하는 내용을 찾으려면 첫 페이지부터 넘겨야 하지만, 목차가 있으면 해당 페이지로 바로 이동할 수 있습니다. DB 인덱스도 마찬가지로, 원하는 데이터의 위치를 빠르게 찾아주는 자료구조입니다.

Phase 1. B+Tree 인덱스의 구조

왜 하필 B+Tree인가요?

MySQL InnoDB 같은 엔진은 기본 인덱스를 흔히 B+Tree 계열 구조로 설명합니다. PostgreSQL은 공식 문서에서 기본 인덱스를 B-Tree로 설명합니다. 실무적으로는 둘 다 균형 트리 기반 인덱스라는 점이 중요하며, 여기서는 MySQL InnoDB 관점에서 B+Tree를 중심으로 설명하겠습니다.

B-Tree — 브랜치 노드에도 데이터를 저장합니다. 운이 좋으면 리프까지 내려가지 않고 중간에서 데이터를 찾을 수 있습니다
B+Tree — 데이터는 리프 노드에만 저장하고, 리프 노드끼리 링크드 리스트로 연결합니다. 브랜치 노드에는 키만 저장하므로 하나의 노드에 더 많은 키를 담을 수 있어 트리 높이가 낮아집니다

DB가 B+Tree를 선택한 이유는 명확합니다.

항상 균형을 유지 — 어떤 데이터를 찾든 트리의 높이가 일정합니다
범위 검색에 유리 — 리프 노드가 정렬된 상태로 양방향 링크드 리스트로 연결되어 있어 BETWEEN, >, < 같은 범위 쿼리에 효율적입니다
디스크 I/O 최소화 — 하나의 노드에 여러 키를 저장해서 트리의 높이를 낮게 유지합니다

B+Tree의 구조

B+Tree는 세 가지 노드로 구성됩니다.

              [루트 노드]
            /      |      \
     [브랜치]   [브랜치]   [브랜치]
      / \        / \        / \
  [리프] [리프] [리프] [리프] [리프] [리프]

루트 노드(Root Node) — 트리의 시작점입니다. 검색은 항상 여기서 시작합니다
브랜치 노드(Branch Node) — 중간 경로입니다. 어느 방향으로 내려갈지 안내하는 이정표 역할을 합니다
리프 노드(Leaf Node) — 실제 인덱스 키 값과 데이터의 위치(또는 InnoDB에서는 PK 참조값)가 저장됩니다. InnoDB 기준으로 리프 노드가 연결되어 있어 정렬 순서대로 범위 탐색할 수 있습니다

검색 과정 예시

age 컬럼에 인덱스가 있고, WHERE age = 28을 실행한다고 가정합니다.

1. 루트 노드에서 28이 어느 범위에 속하는지 확인 → 왼쪽 브랜치로 이동
2. 브랜치 노드에서 다시 범위 확인 → 해당 리프 노드로 이동
3. 리프 노드에서 28을 찾고, 저장된 포인터로 실제 데이터 행에 접근

트리의 높이가 3이라면, 단 3번의 노드 접근으로 원하는 데이터를 찾을 수 있습니다. 100만 행이든 1,000만 행이든 B+Tree의 높이는 보통 3~4 수준이므로, 데이터 양이 늘어도 검색 속도가 크게 변하지 않습니다.

참고: B+Tree의 하나의 노드는 수백 개의 키를 저장할 수 있어 분기 계수(branching factor)가 매우 높습니다. 덕분에 1,000만 행이라도 트리 높이가 3~4에 불과하며, 디스크 I/O 횟수도 그만큼만 발생합니다. 풀 테이블 스캔의 O(N)과는 비교할 수 없는 차이입니다.

Phase 2. 클러스터드 vs 논클러스터드 인덱스

클러스터드 인덱스 (Clustered Index)

데이터 자체가 인덱스 순서대로 물리적으로 정렬되어 저장되는 인덱스입니다.

테이블당 하나만 존재할 수 있습니다 (물리적 정렬은 하나의 기준만 가능)
MySQL(InnoDB)에서는 기본키(PK)가 곧 클러스터드 인덱스입니다
리프 노드에 실제 데이터 행 전체가 저장됩니다

-- 클러스터드 인덱스 (PK = id)
리프 노드: [id=1, name='김철수', age=28] → [id=2, name='이영희', age=25] → ...

논클러스터드 인덱스 (Non-Clustered Index, 보조 인덱스)

별도의 공간에 인덱스 키와 PK 값을 저장하는 인덱스입니다.

테이블에 여러 개 만들 수 있습니다
리프 노드에는 인덱스 키 값과 PK 값(포인터) 이 저장됩니다
데이터를 가져오려면 PK로 다시 한번 클러스터드 인덱스를 탐색해야 합니다

-- 논클러스터드 인덱스 (name)
리프 노드: ['김철수', PK=1] → ['이영희', PK=2] → ...
         ↓                    ↓
   클러스터드 인덱스에서      클러스터드 인덱스에서
   PK=1인 행 조회            PK=2인 행 조회

이 두 번째 조회를 랜덤 I/O라고 하며, 조회할 행이 많아지면 오히려 풀 테이블 스캔보다 느려질 수 있습니다. 이것이 옵티마이저가 대량 데이터 조회 시 인덱스를 사용하지 않는 이유입니다.

참고: MySQL(InnoDB)에서 보조 인덱스의 리프 노드에 저장되는 것은 행의 물리적 주소가 아니라 PK 값입니다. 따라서 PK가 크면(예: UUID) 모든 보조 인덱스의 크기도 함께 커집니다. PK를 BIGINT AUTO_INCREMENT로 설정하는 것이 유리한 이유 중 하나입니다.

Phase 3. 복합 인덱스와 컬럼 순서

복합 인덱스란?

두 개 이상의 컬럼을 조합해서 만드는 인덱스입니다.

CREATE INDEX idx_name_age ON users (name, age);

컬럼 순서가 중요한 이유

복합 인덱스는 왼쪽 컬럼부터 순서대로 정렬됩니다. (name, age) 인덱스는 이렇게 정렬됩니다.

김철수, 25
김철수, 28
박민수, 27
이영희, 22
이영희, 30

먼저 name으로 정렬하고, 같은 name 안에서 age로 정렬합니다. 이 순서 때문에 다음과 같은 차이가 생깁니다.

-- ✅ 인덱스 사용 가능 (왼쪽부터 순서대로 사용)
WHERE name = '김철수'
WHERE name = '김철수' AND age = 28

-- ❌ 일반적인 복합 인덱스 탐색에는 부적합 (첫 번째 컬럼을 건너뜀)
WHERE age = 28

age만으로 검색하면 일반적인 leftmost prefix 탐색에는 맞지 않습니다. name이 정해지지 않은 상태에서 age 기준 정렬을 바로 활용하기 어렵기 때문입니다. 이것을 최좌선 접두사 규칙(Leftmost Prefix Rule) 이라고 합니다. 다만 MySQL 8.x의 skip scan 같은 예외 최적화가 적용되는 경우는 있을 수 있습니다.

어떤 컬럼을 앞에 놓아야 할까?

일반적인 원칙은 다음과 같습니다.

동등 조건(=)으로 자주 사용하는 컬럼을 앞에 배치합니다
범위 조건(>, <, BETWEEN)으로 사용하는 컬럼은 뒤에 배치합니다
카디널리티(고유 값의 수)가 높은 컬럼을 앞에 두면 검색 범위가 빠르게 좁혀집니다

-- status는 값이 3~4종류, created_at은 범위 검색
-- → status를 앞에, created_at을 뒤에
CREATE INDEX idx_status_created ON orders (status, created_at);

-- 이렇게 하면 아래 쿼리가 효율적으로 동작합니다
WHERE status = 'PAID' AND created_at > '2026-01-01'

참고: 범위 조건이 사용된 컬럼 이후의 컬럼은 인덱스를 활용하지 못합니다. (a, b, c) 인덱스에서 WHERE a = 1 AND b > 10 AND c = 100이라면, a와 b까지만 인덱스를 타고 c는 필터링으로 처리됩니다.

Phase 4. 커버링 인덱스

커버링 인덱스란?

쿼리가 요청하는 모든 컬럼이 인덱스에 포함되어 있어서, 실제 데이터 행을 읽지 않고 인덱스만으로 결과를 반환할 수 있는 상태를 말합니다.

-- (name, age) 인덱스가 있을 때
SELECT name, age FROM users WHERE name = '김철수';

이 쿼리는 name과 age만 필요한데, 둘 다 인덱스에 있습니다. 따라서 클러스터드 인덱스(데이터 페이지)를 추가로 조회할 필요가 없습니다.

왜 빠른가요?

랜덤 I/O 제거 — 보조 인덱스 → 클러스터드 인덱스로 이동하는 과정이 사라집니다
읽는 데이터 양 감소 — 인덱스 페이지는 데이터 페이지보다 훨씬 작습니다 (필요한 컬럼만 저장)

EXPLAIN으로 확인하기

커버링 인덱스가 적용되면 EXPLAIN 결과의 Extra 컬럼에 Using index 가 표시됩니다.

EXPLAIN SELECT name, age FROM users WHERE name = '김철수';

+----+-------+------+-----------+
| id | type  | key  | Extra     |
+----+-------+------+-----------+
|  1 | ref   | idx  | Using index |
+----+-------+------+-----------+

참고: 커버링 인덱스를 위해 SELECT * 대신 필요한 컬럼만 명시하는 습관이 중요합니다. SELECT *은 인덱스에 포함되지 않은 컬럼까지 요청하므로 커버링 인덱스를 활용할 수 없습니다.

Phase 5. EXPLAIN 실행 계획 읽기

EXPLAIN이란?

쿼리를 실행하기 전에 옵티마이저가 어떤 계획으로 실행할지 미리 보여주는 명령입니다.

EXPLAIN SELECT * FROM orders WHERE user_id = 1 AND status = 'PAID';

핵심 컬럼 해석

+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+

가장 중요한 컬럼들을 하나씩 살펴보겠습니다.

type — 접근 방식

성능에 가장 큰 영향을 주는 컬럼입니다. 위에서 아래로 갈수록 성능이 좋습니다.

type	의미	성능
ALL	풀 테이블 스캔	최악
index	풀 인덱스 스캔 (인덱스 전체를 순회)	나쁨
range	인덱스 범위 스캔 (BETWEEN, >, <)	보통
ref	인덱스를 사용한 동등 비교 (비유니크)	좋음
eq_ref	인덱스를 사용한 동등 비교 (유니크/PK)	매우 좋음
const / system	PK 또는 유니크 인덱스로 1행 조회	최고

key — 실제 사용된 인덱스

possible_keys는 사용 가능한 인덱스 후보이고, key는 옵티마이저가 실제로 선택한 인덱스입니다. key가 NULL이면 인덱스를 사용하지 않았다는 뜻입니다.

rows — 예상 조회 행 수

옵티마이저가 얼마나 많은 행을 읽어야 하는지 추정한 값입니다. 실제 값과 다를 수 있지만, 이 숫자가 크면 쿼리가 비효율적일 가능성이 높습니다.

Extra — 추가 정보

자주 보이는 값들입니다.

Extra	의미
Using index	커버링 인덱스 사용 (데이터 페이지 접근 없음)
Using where	WHERE 조건으로 추가 필터링
Using filesort	인덱스 순서와 다른 정렬이 필요해 별도 정렬 수행
Using temporary	임시 테이블 생성 (GROUP BY, DISTINCT 등)

Using filesort와 Using temporary가 함께 나타나면 성능 개선이 필요한 신호입니다.

참고: EXPLAIN ANALYZE(MySQL 8.0.18+)를 사용하면 예상 값이 아닌 실제 실행 결과를 확인할 수 있습니다. 실행 계획과 실제 성능 차이가 의심될 때 유용합니다.

Phase 6. 인덱스가 안 타는 케이스

인덱스를 만들어 놓고도 사용되지 않는 대표적인 경우들입니다.

인덱스 컬럼에 가공을 하는 경우

-- ❌ 함수 적용 → 인덱스 무시
WHERE YEAR(created_at) = 2026

-- ✅ 범위 조건으로 변환
WHERE created_at >= '2026-01-01' AND created_at < '2027-01-01'

인덱스는 원본 값 기준으로 정렬되어 있습니다. 함수를 적용하면 정렬 순서가 달라질 수 있어 B+Tree를 활용할 수 없습니다.

묵시적 타입 변환

-- phone 컬럼이 VARCHAR인데 숫자로 비교
-- ❌ 묵시적 변환 발생 → 인덱스 무시
WHERE phone = 01012345678

-- ✅ 문자열로 비교
WHERE phone = '01012345678'

타입이 맞지 않으면 DB가 내부적으로 변환을 수행하는데, 이때 인덱스 컬럼 쪽이 변환되면 인덱스를 사용할 수 없습니다.

OR 조건

-- ❌ OR로 다른 컬럼을 연결하면 인덱스 활용이 어려움
WHERE name = '김철수' OR age = 28

-- ✅ 각각 인덱스가 있다면 UNION으로 분리
SELECT * FROM users WHERE name = '김철수'
UNION ALL
SELECT * FROM users WHERE age = 28 AND name != '김철수'

NOT, != 부정 조건

-- ❌ 부정 조건은 옵티마이저가 비효율적이라 판단하여 인덱스를 사용하지 않는 경우가 많음
WHERE status != 'DELETED'

-- ✅ 긍정 조건으로 변환 가능하면 변환
WHERE status IN ('ACTIVE', 'PENDING', 'PAID')

LIKE의 와일드카드 위치

-- ❌ 앞에 % → 인덱스 무시
WHERE name LIKE '%철수'

-- ✅ 뒤에 % → 인덱스 사용 가능
WHERE name LIKE '김%'

%가 앞에 오면 시작 지점을 특정할 수 없으므로 B+Tree를 탐색할 수 없습니다.

조회 대상이 너무 많은 경우

인덱스로 조회할 행이 전체 데이터의 상당 부분을 차지하면, 옵티마이저는 인덱스를 거치는 것보다 풀 테이블 스캔이 더 효율적이라고 판단합니다. 정확한 임계값은 데이터 분포, 페이지 크기 등에 따라 다르지만, 경험적으로 약 10~25% 이상이면 풀 스캔이 선택되는 경우가 많습니다. 보조 인덱스의 랜덤 I/O 비용이 순차 스캔보다 커지기 때문입니다.

참고: 인덱스를 만들었는데 EXPLAIN에서 사용되지 않는다면 위 케이스 중 하나에 해당하는 경우가 대부분입니다. EXPLAIN으로 확인하는 습관이 가장 확실한 예방법입니다.

한눈에 보는 인덱스 핵심 정리

개념	핵심 포인트
B+Tree	균형 트리, O(log N) 탐색, 범위 검색에 유리
클러스터드 인덱스	데이터 자체가 PK 순서로 정렬, 테이블당 1개
논클러스터드 인덱스	별도 저장, PK로 다시 조회 (랜덤 I/O)
복합 인덱스	최좌선 접두사 규칙, 동등 조건 → 범위 조건 순서로 배치
커버링 인덱스	인덱스만으로 결과 반환, SELECT * 지양
EXPLAIN	type, key, rows, Extra를 확인

정리

B+Tree — 대부분의 RDBMS가 사용하는 기본 인덱스 구조이며, O(log N)으로 빠른 검색을 보장합니다
클러스터드 vs 논클러스터드 — PK는 곧 클러스터드 인덱스이며, 보조 인덱스는 PK를 통해 데이터에 접근합니다
복합 인덱스 — 컬럼 순서가 성능을 결정합니다. 동등 조건을 앞에, 범위 조건을 뒤에 배치합니다
커버링 인덱스 — 인덱스만으로 쿼리를 처리하면 랜덤 I/O를 제거할 수 있습니다
EXPLAIN — 쿼리 튜닝의 기본 출발점입니다. 인덱스를 만들었으면 실행 계획으로 확인하는 습관이 중요합니다
인덱스 함정 — 컬럼 가공, 타입 불일치, 앞쪽 와일드카드 등은 인덱스를 무력화합니다