포스트

RDB 인덱스 완전 정리 — B-tree 구조부터 인덱스가 안 타는 이유까지

B+tree 인덱스가 조회를 빠르게 하는 원리, 복합 인덱스 선두 컬럼 규칙, 커버링 인덱스, 그리고 인덱스가 안 타는 흔한 이유들을 실무 관점으로 정리한다.

게시
By clang.engineer
조회 20 분읽는 시간
RDB 인덱스 완전 정리 — B-tree 구조부터 인덱스가 안 타는 이유까지

인덱스를 만들었는데도 쿼리가 느리다면, 대개 인덱스의 동작 원리를 오해했기 때문이다. 인덱스는 마법이 아니라 정렬된 자료구조이고, 그 구조에 맞는 조건일 때만 탐색이 빨라진다. 이 글은 B+tree 인덱스가 조회를 어떻게 가속하는지, 복합 인덱스에서 컬럼 순서가 왜 중요한지, 그리고 인덱스를 만들고도 풀스캔이 도는 흔한 이유들을 정리한다.

1. 인덱스는 왜 조회를 빠르게 하나

인덱스가 없으면 조건에 맞는 행을 찾기 위해 테이블 전체를 읽어야 한다. 100만 행이면 100만 행을 다 훑는 풀 테이블 스캔이고, 비용은 데이터 양에 비례해 O(N)으로 늘어난다.

인덱스는 특정 컬럼 값을 정렬된 상태로 별도 저장한다. 정렬돼 있으니 이진 탐색처럼 값의 위치를 좁혀갈 수 있고, B+tree 기준 탐색 비용은 O(log N)이다. 100만 행에서 원하는 값을 찾는 데 몇 번의 노드 방문이면 충분하다.

공짜는 아니다. 인덱스는 대가를 요구한다.

  • 쓰기 비용: INSERT·UPDATE·DELETE 때마다 인덱스도 함께 갱신해야 한다. 인덱스가 많을수록 쓰기가 느려진다.
  • 공간 비용: 인덱스는 원본과 별개의 디스크 공간을 차지한다.

인덱스는 “읽기를 빠르게 하는 대신 쓰기와 공간을 내주는” 트레이드오프다. 읽기가 많고 쓰기가 적은 컬럼일수록 이득이 크다.

2. B+tree 구조

관계형 DB의 기본 인덱스는 거의 다 B+tree다. 흔히 “B-tree 인덱스”라 부르지만, 실제 구현은 값을 리프에만 저장하는 B+tree 변형이다.

왜 균형 트리인가

B+tree는 모든 리프 노드가 같은 깊이에 있는 균형 트리다. 어떤 값을 찾든 루트에서 리프까지 거치는 노드 수가 동일하다. 데이터가 아무리 편향돼 들어와도 트리가 한쪽으로 기울지 않으므로, 최악의 경우에도 탐색 비용이 O(log N)으로 보장된다.

각 노드는 디스크 페이지 하나에 대응하고, 한 노드가 자식을 수백 개씩 가지는 넓고 낮은(fan-out이 큰) 트리다. 그래서 수백만~수억 행이라도 트리 높이는 서너 단계에 그치고, 디스크 접근 횟수가 몇 번으로 억제된다.

1
2
3
4
5
6
7

             [ 30 | 60 ]              ← 루트(내부 노드): 라우팅 키만
            /    |     \
      [10|20] [40|50] [70|80]         ← 내부 노드
       ...
   [10→11→..] [40→..] [70→..]         ← 리프 노드: 실제 값 + 다음 리프 포인터
      └──────────┴─────────┘
        리프끼리 연결 리스트

리프 노드 연결 리스트와 범위 스캔

B+tree의 핵심은 리프 노드끼리 연결 리스트로 이어져 있다는 점이다. 실제 인덱스 값은 전부 리프에 정렬 순서대로 놓이고, 각 리프는 다음 리프를 가리킨다.

덕분에 BETWEEN, >, <, ORDER BY 같은 범위 조회가 효율적이다. 시작 값의 위치를 트리 탐색으로 한 번 찾은 뒤, 리프 연결 리스트를 순서대로 따라가기만 하면 된다. 매번 루트부터 다시 내려갈 필요가 없다.

1
2
3
4

-- 인덱스가 (created_at)에 있으면:
-- 2026-01-01 위치를 log N 으로 찾고, 리프를 순차 스캔
SELECT * FROM orders
WHERE created_at BETWEEN '2026-01-01' AND '2026-01-31';

정렬된 순서로 저장되므로 ORDER BY created_at도 별도 정렬 없이 인덱스 순서를 그대로 활용할 수 있다.

3. 복합 인덱스와 선두 컬럼(leftmost prefix) 규칙

여러 컬럼을 묶은 복합 인덱스(composite index) 는 지정한 컬럼 순서대로 값을 이어붙여 정렬한다. (a, b, c) 인덱스는 먼저 a로 정렬하고, a가 같은 것끼리 b로, 그다음 c로 정렬한다. 전화번호부가 성 → 이름 순으로 정렬된 것과 같다.

여기서 선두 컬럼(leftmost prefix) 규칙이 나온다. 인덱스는 왼쪽 컬럼부터 연속으로 조건이 주어질 때만 탐색에 쓸 수 있다.

(a, b, c) 인덱스 기준으로:

WHERE 조건인덱스 사용
a = ?사용 (선두 컬럼)
a = ? AND b = ?사용
a = ? AND b = ? AND c = ?완전 사용
b = ?불가 — 선두 a 없음
b = ? AND c = ?불가 — 선두 a 없음
a = ? AND c = ?a까지만 사용, c는 필터로

성 없이 이름만으로 전화번호부를 찾을 수 없는 것과 같다. 이름은 성 안에서만 정렬돼 있기 때문이다.

복합 인덱스는 컬럼 순서가 성능을 좌우한다. 자주 등장하고 등호(=)로 걸리는 컬럼을 앞에, 범위 조건(>, BETWEEN)으로 걸리는 컬럼을 뒤에 두는 것이 일반적인 원칙이다. 범위 조건이 걸린 컬럼 이후의 컬럼은 인덱스 정렬 이점을 잃는다.

4. 커버링 인덱스 (index-only scan)

쿼리가 요구하는 컬럼이 전부 인덱스 안에 있으면, DB는 테이블 본체를 읽지 않고 인덱스만으로 결과를 완성한다. 이를 커버링 인덱스, 그 실행을 index-only scan이라 한다.

보통 인덱스로 위치를 찾은 뒤 실제 행 데이터를 가져오려 테이블에 한 번 더 접근한다(테이블 랜덤 액세스). 커버링이면 이 2차 접근이 사라져 크게 빨라진다.

1
2
3

-- 인덱스: (user_id, status)
-- SELECT 대상이 모두 인덱스에 존재 → 테이블 접근 없이 완료
SELECT status FROM orders WHERE user_id = 42;

MySQL(InnoDB)에서는 EXPLAIN의 Extra에 Using index로, PostgreSQL에서는 EXPLAIN에 Index Only Scan으로 나타난다. PostgreSQL은 가시성 판단을 위해 visibility map을 참조하므로, VACUUM이 최근에 돈 테이블일수록 index-only scan 효율이 좋다.

SELECT와 WHERE에 자주 함께 쓰이는 소수 컬럼이라면, 필요한 컬럼을 인덱스에 포함시켜 커버링을 노리는 것이 효과적이다. PostgreSQL·MySQL 8은 INCLUDE 절로 탐색 키가 아닌 컬럼을 리프에만 얹을 수 있다.

1
2

-- 탐색은 user_id로, status는 커버링 용도로만 리프에 저장
CREATE INDEX idx_orders_user ON orders (user_id) INCLUDE (status);

5. 부분 인덱스와 함수/표현식 인덱스

부분 인덱스 (partial index)

특정 조건을 만족하는 행만 인덱싱한다. 인덱스가 작아져 공간·유지 비용이 줄고, 조회하려는 대상이 소수일 때 효율적이다. PostgreSQL·SQLite가 지원하며, MySQL은 이 형태의 부분 인덱스를 지원하지 않는다.

1
2
3

-- 미처리 주문만 조회한다면 그 행만 인덱싱
CREATE INDEX idx_pending ON orders (created_at)
WHERE status = 'PENDING';

함수/표현식 인덱스 (functional / expression index)

컬럼 원본이 아니라 함수·표현식의 결과를 인덱싱한다. 뒤에서 볼 “컬럼에 함수를 씌우면 인덱스가 안 탄다” 문제를 정면으로 해결하는 수단이다.

1
2
3
4

-- 대소문자 무시 검색을 인덱스로: PostgreSQL
CREATE INDEX idx_lower_email ON users (LOWER(email));
-- 이제 이 쿼리가 인덱스를 탄다
SELECT * FROM users WHERE LOWER(email) = 'a@b.com';

MySQL 8도 함수 인덱스(functional key parts)를 지원한다. 표현식을 인덱스 정의와 똑같이 써야 옵티마이저가 매칭한다.

6. 인덱스가 안 타는 흔한 이유

인덱스를 만들고도 풀스캔이 도는 대부분의 원인은 아래 몇 가지다. 공통 원리는 하나 — 인덱스는 컬럼 값이 “정렬된 원본 그대로” 조건에 걸릴 때만 쓸 수 있다.

6-1. 선두 컬럼 누락

(a, b) 인덱스에서 WHERE b = ?만 걸면 못 쓴다(§3). 복합 인덱스를 만들 때 가장 흔한 실수다.

6-2. 컬럼에 함수·연산 적용

컬럼을 가공하면 인덱스에 저장된 “원본 값”과 매칭되지 않는다.

1
2
3
4
5
6
7
8

-- 인덱스 못 탐: 컬럼에 함수/연산이 씌워짐
WHERE LOWER(email) = 'a@b.com'          -- email 인덱스 무력화
WHERE salary * 12 > 60000000            -- salary 인덱스 무력화
WHERE DATE(created_at) = '2026-07-03'   -- created_at 인덱스 무력화

-- 인덱스 탐: 컬럼은 그대로 두고 상수 쪽을 가공
WHERE salary > 5000000
WHERE created_at >= '2026-07-03' AND created_at < '2026-07-04'

정 함수를 써야 하면 표현식 인덱스(§5)로 맞춰준다.

6-3. 암묵적 형변환 (implicit type conversion)

컬럼 타입과 비교 값의 타입이 다르면 DB가 한쪽을 자동 변환하는데, 이때 컬럼 쪽이 변환되면 6-2와 같은 이유로 인덱스가 죽는다.

1
2
3

-- phone 컬럼이 VARCHAR인데 숫자로 비교 → 컬럼이 형변환됨
WHERE phone = 1012345678     -- 인덱스 못 탐
WHERE phone = '1012345678'   -- 타입 일치, 인덱스 탐

JDBC 바인딩 타입과 컬럼 타입 불일치로 조용히 발생하곤 한다. EXPLAIN으로 반드시 확인할 대목이다.

6-4. 낮은 선택도 (low cardinality)

인덱스는 조건에 맞는 행이 전체의 소수일 때 이득이다. gender, is_active처럼 값 종류가 적어 한 값이 테이블의 절반을 차지하면, 인덱스로 위치를 찾고 테이블을 랜덤 액세스하는 비용이 오히려 풀스캔보다 크다. 옵티마이저는 이 경우 일부러 인덱스를 버리고 풀스캔을 고른다. 인덱스가 안 타는 게 아니라 안 타는 게 이득이라 판단한 것이다.

선택도(selectivity)가 높은 컬럼(값이 다양해 조건이 소수 행만 남기는 컬럼)이 인덱스에 적합하다. 카디널리티가 낮은 컬럼 단독 인덱스는 대개 무의미하다.

6-5. LIKE 앞 와일드카드

B+tree는 값의 앞부분(prefix) 부터 정렬돼 있다. 앞이 고정된 LIKE 'abc%'는 범위 스캔이 되지만, 앞이 열린 LIKE '%abc'는 시작 위치를 특정할 수 없어 못 쓴다.

1
2
3

WHERE name LIKE 'kim%'    -- 인덱스 탐 (prefix 고정)
WHERE name LIKE '%kim'    -- 인덱스 못 탐 (앞 와일드카드)
WHERE name LIKE '%kim%'   -- 못 탐

중간·뒷부분 검색이 필요하면 전문 검색 인덱스(PostgreSQL GIN + pg_trgm, MySQL FULLTEXT)를 쓴다.

6-6. OR 조건

서로 다른 컬럼을 OR로 묶으면 하나의 인덱스 범위로 좁혀지지 않는다. 옵티마이저가 각 조건의 인덱스를 각각 타 결과를 합치기도(index merge / Bitmap OR) 하지만, 안 되면 풀스캔으로 떨어진다. UNION으로 쪼개거나 IN으로 바꿀 수 있으면 유리하다.

1
2
3
4
5

-- 각 컬럼 인덱스가 따로 있어도 못 탈 수 있음
WHERE a = 1 OR b = 2

-- 같은 컬럼이면 IN이 인덱스에 우호적
WHERE status = 'A' OR status = 'B'   →   WHERE status IN ('A', 'B')

7. B-tree 외 인덱스 종류

B+tree가 만능은 아니다. 접근 패턴에 따라 다른 구조가 낫다.

종류언제 쓰나
Hash등호(=) 조회 전용. 범위·정렬 불가. PostgreSQL이 지원하나 이점이 제한적이라 실무에선 B-tree가 기본
GiST (PostgreSQL)기하·공간 데이터(PostGIS), 범위 타입, 근접 검색 등 “겹침/포함” 질의
GIN (PostgreSQL)한 행이 여러 값을 갖는 데이터 — 전문 검색(tsvector), jsonb, 배열 컬럼
BRIN (PostgreSQL)값이 물리적 저장 순서와 상관관계 큰 초대형 테이블(시계열 등). 블록 요약만 저장해 매우 작음
Bitmap (Oracle)카디널리티 낮은 컬럼, 읽기 위주 DW. AND/OR 결합 조회에 강함. OLTP엔 부적합

MySQL(InnoDB)은 사용자에게 B-tree 인덱스만 노출하고(내부적으로 메모리 해시 등을 자동 활용), 공간 인덱스와 FULLTEXT를 별도로 제공한다.

8. 실무 팁

인덱스 남발의 비용

인덱스는 쓰기마다 함께 갱신되므로, 안 쓰이는 인덱스는 순수한 손해다. 쓰기 성능을 갉아먹고 공간을 차지하며, 옵티마이저의 후보만 늘려 실행 계획 수립을 흐린다.

  • 실제 쿼리 패턴에 근거해 만든다. “혹시 몰라서”는 지운다.
  • 복합 인덱스로 여러 쿼리를 커버할 수 있으면 단일 인덱스 여러 개보다 낫다.
  • 안 쓰이는 인덱스는 통계로 찾아 제거한다(PostgreSQL pg_stat_user_indexes의 idx_scan, MySQL sys.schema_unused_indexes).

EXPLAIN으로 실제 사용 확인

인덱스가 “탈 것 같다”는 추측은 자주 틀린다. EXPLAIN(PostgreSQL은 EXPLAIN (ANALYZE, BUFFERS))으로 실제 실행 계획을 봐야 한다.

  • 풀스캔 여부: PostgreSQL Seq Scan / MySQL type: ALL 이면 인덱스 미사용.
  • 인덱스 스캔: PostgreSQL Index Scan·Index Only Scan / MySQL type: ref·range, Extra: Using index.
  • 예상 행 수(rows)와 실제 행 수가 크게 다르면 통계가 낡은 것 — ANALYZE로 갱신한다.

인덱스는 만드는 게 아니라 쓰이는지 확인하는 것까지가 작업이다. EXPLAIN 없이 인덱스를 논하지 않는다.

관련 글

글관계
RDB에서 조인(Join) 방식 총정리옵티마이저가 인덱스 유무로 조인 전략을 고르는 방식
쿼리 옵티마이저 작동 원리와 실행계획 읽기EXPLAIN으로 인덱스가 실제 쓰였는지 확인
db, RDB·트랜잭션
index b-tree performance
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.