Database Index (데이터베이스 인덱스)

데이터베이스에서 조회 성능을 좌우하는 가장 핵심적인 요소는 인덱스입니다. "인덱스를 걸면 빨라진다"는 사실은 누구나 알지만, 어떤 인덱스를 어떤 순서로 구성하느냐에 따라 성능이 수십 배 달라집니다. 이 글에서는 인덱스가 내부에서 실제로 어떻게 동작하는지를 리프 노드 레벨까지 파고들어 설명합니다.

인덱스란

데이터베이스 인덱스는 테이블의 특정 컬럼 값으로 행을 빠르게 찾기 위한 별도의 자료구조입니다. 책의 맨 뒤에 있는 색인(index)을 떠올리면 됩니다. 전체 본문을 처음부터 끝까지 읽지 않아도, 색인에서 키워드를 찾으면 해당 페이지로 바로 이동할 수 있습니다. 데이터베이스 인덱스도 같은 원리입니다.

인덱스를 이해하기 위해 알아야 할 핵심 용어 세 가지가 있습니다:

• 클러스터드 인덱스(Clustered Index): 테이블 데이터 자체가 PK 기준으로 정렬된 B+Tree 구조입니다. InnoDB에서는 테이블이 곧 클러스터드 인덱스입니다. 테이블당 하나만 존재합니다.
• 세컨더리 인덱스(Secondary Index): PK가 아닌 컬럼으로 만든 별도의 B+Tree입니다. 리프 노드에 인덱스 키 + PK 값을 저장하며, 실제 행 데이터가 필요하면 PK로 클러스터드 인덱스를 다시 탐색합니다.
• 복합 인덱스(Composite Index): 두 개 이상의 컬럼을 조합한 인덱스입니다. 컬럼 순서에 따라 리프 노드의 데이터 배치가 완전히 달라지며, 이것이 복합 인덱스 설계의 핵심입니다.

왜 필요한가

2,100만 건의 트랜잭션 테이블에서 주소 기반 조회를 했더니 평균 응답 시간이 2~3초였습니다. 인덱스가 없었기 때문입니다. 인덱스를 걸자 120ms로 떨어졌습니다.

인덱스가 없으면 데이터베이스는 Full Table ScanFull Table Scan을 수행합니다. 2,100만 건의 행을 첫 번째부터 마지막까지 순차적으로 읽으며 조건에 맞는 행을 찾습니다. 반면 인덱스가 있으면 B+Tree를 타고 3~4번의 페이지 접근만으로 원하는 데이터의 위치를 특정합니다.

하지만 어떤 인덱스를 거느냐에 따라 결과가 완전히 달라집니다. 단일 인덱스 (from_address)만 걸면 주소 필터링은 되지만 ORDER BY block_id DESC 정렬을 위해 filesort가 발생합니다. (from_address, block_id DESC) 복합 인덱스를 걸면 filesort가 완전히 제거됩니다. 이 차이를 이해하려면 리프 노드에서 데이터가 어떻게 배치되는지를 알아야 합니다.

흔한 오해 몇 가지를 짚겠습니다:

• "카디널리티카디널리티가 낮은 컬럼은 인덱스에 쓸모없다" — 단독 인덱스에서는 맞지만, 복합 인덱스의 중간 등호 컬럼으로는 매우 유효합니다
• "PK 조회는 $O(1)$이다" — 클러스터드 인덱스도 B+Tree이므로 $O(\log n)$입니다. 2,100만 건이면 3~4회 페이지 접근이 필요합니다
• "커버링 인덱스는 항상 좋다" — 컬럼이 20개인 테이블에 커버링 인덱스를 걸면 인덱스 크기가 테이블에 육박합니다

동작 원리

디스크 I/O 경제학이 강제한 B+Tree

데이터베이스는 데이터를 디스크에 저장합니다. 디스크에서 데이터를 읽을 때 두 가지 방식이 있습니다:

• Random I/O: 디스크 헤드가 원하는 위치로 이동(seek) → 한 블록 읽기. HDD 기준 약 10ms
• Sequential I/O: 현재 위치에서 연속된 블록을 읽기. 같은 시간에 수십~수백 블록

이 비용 격차가 B+Tree의 모든 설계를 결정합니다:

높은 fanout: 이진 트리는 노드당 자식이 2개뿐이라 트리 높이가 ${\log }_{2}n$입니다. 2,100만 건이면 약 24레벨 — 한 건 찾는 데 24번의 Random I/O가 필요합니다. B+Tree는 노드 하나를 **디스크 페이지(보통 16KB)**에 맞춰 수백 개의 키를 담으므로 fanout이 수백입니다. ${\log }_{200}21000000\approx 3.2$ — 불과 3~4레벨이면 충분합니다.

리프 노드 연결 리스트: 범위 스캔(WHERE created_at BETWEEN ? AND ?)에서 트리를 매번 루트부터 타고 내려가면 Random I/O가 범위 크기만큼 발생합니다. 리프 노드를 양방향 연결 리스트로 연결하면 한 번만 트리를 타고 내려간 뒤 연속된 리프를 Sequential I/O로 쭉 읽을 수 있습니다.

SSD에서는 다른가? SSD는 seek 비용이 HDD 대비 100배 이상 빠르지만, Random I/O vs Sequential I/O 격차는 여전히 존재합니다 (약 4~10배). 그래서 SSD 환경에서도 B+Tree는 여전히 지배적인 인덱스 구조입니다. 다만 LSM Tree처럼 쓰기 최적화 구조가 SSD에서 더 경쟁력을 갖게 된 건 사실입니다.

클러스터드 인덱스 vs 세컨더리 인덱스

InnoDB에서 테이블은 그 자체가 클러스터드 인덱스입니다. PK를 기준으로 B+Tree를 구성하고, 리프 노드에 실제 행 데이터 전체를 저장합니다. 테이블이 곧 인덱스인 셈입니다.

세컨더리 인덱스는 별도의 B+Tree입니다. 리프 노드에는 인덱스 키 컬럼 + PK 값만 저장합니다. 실제 행 데이터가 필요하면 이 PK로 클러스터드 인덱스를 다시 탐색해야 합니다:

이 "이중 탐색"의 비용은 다음과 같습니다:

1. 세컨더리 인덱스 B+Tree 탐색: $O(\log n)$
2. 클러스터드 인덱스 B+Tree 탐색: $O(\log n)$

20건을 가져온다면 2번 과정이 20회 반복됩니다. 각 PK가 서로 다른 페이지에 있으면 20번의 Random I/O가 발생할 수 있습니다.

커버링 인덱스

이 재탐색을 제거하는 방법이 커버링 인덱스입니다. 쿼리에 필요한 모든 컬럼을 인덱스에 포함시키면 세컨더리 인덱스 리프만으로 결과를 반환할 수 있습니다. 대신 인덱스 크기가 커지고 쓰기 비용이 증가합니다. 컬럼이 20개인 테이블에서는 비실용적이지만, follows(follower_id, followee_id)처럼 컬럼이 적은 테이블에서는 매우 효과적입니다.

복합 인덱스의 리프 노드 배치

복합 인덱스의 핵심은 컬럼 순서에 따라 리프 노드의 데이터 배치가 완전히 달라진다는 점입니다. (user_id, status, created_at DESC) 인덱스에서 user_id = 123인 엔트리들이 리프에 어떻게 배치되는지 봅시다:

이 시각화에서 핵심을 두 가지 확인할 수 있습니다:

첫째, WHERE status = 'PAID' 조건이 있으면 PAID 그룹으로 바로 점프하고, 그 안에서 created_at이 이미 내림차순이므로 forward scan만으로 결과를 가져옵니다. filesort가 필요 없습니다.

둘째, status 조건 없이 ORDER BY created_at DESC만 하면 전체 엔트리를 읽어야 하는데, created_at이 status 그룹별로 분리되어 있어 전역 정렬이 깨져 있습니다. filesort가 필요합니다. 이것이 "중간 컬럼 건너뛰기 문제"입니다.

등호 먼저, 정렬 마지막 — 복합 인덱스의 황금 규칙

이 원칙을 이커머스 시나리오에 적용해봅시다:

SELECT * FROM orders
WHERE user_id = ?      -- 등호 조건
  AND status = ?       -- 등호 조건 (카디널리티 낮아도 OK)
ORDER BY created_at DESC  -- 정렬 조건
LIMIT 20;

최적 인덱스: (user_id, status, created_at DESC) // [!code highlight]

1. user_id = ? → 해당 유저의 파티션으로 점프 (평균 25건)
2. status = ? → 그 안에서 해당 상태로 점프 (약 5건)
3. ORDER BY created_at DESC → 이미 정렬됨, forward scan

status의 카디널리티가 5밖에 안 되더라도 복합 인덱스의 중간 등호 컬럼으로는 유효합니다. "카디널리티가 낮으면 인덱스에 불리하다"는 단독 인덱스에만 해당하는 이야기입니다.

중간 컬럼 건너뛰기 문제

요구사항이 바뀌어 status 필터가 빠지고 기간 검색이 들어오면 어떻게 될까요?

SELECT * FROM orders
WHERE user_id = ?
  AND created_at BETWEEN '2026-01-01' AND '2026-04-01'
ORDER BY created_at DESC
LIMIT 20;

(user_id, status, created_at DESC) 인덱스는 이 쿼리에 최적이 아닙니다. user_id = ?로 좁힌 뒤, 중간의 status를 건너뛰면 created_at의 전역 정렬이 깨져 filesort가 다시 발생합니다. 이 쿼리에는 (user_id, created_at DESC)가 필요합니다.

JOIN 환경에서의 인덱스 설계

소셜 피드 쿼리를 예로 들면:

SELECT p.*
FROM follows f
JOIN posts p ON p.author_id = f.followee_id
WHERE f.follower_id = ?
ORDER BY p.created_at DESC
LIMIT 20;

follows 테이블은 컬럼이 3개뿐이므로 커버링 인덱스의 비용이 낮습니다. posts 테이블은 author_id로 점프한 뒤 created_at 내림차순으로 스캔합니다.

하지만 500명을 팔로우하면 500개 author의 게시글을 모두 가져온 뒤 **전역 정렬(filesort)**이 필요합니다. 여러 author에 걸친 created_at 전역 정렬은 인덱스가 해결할 수 없는 영역입니다. 실제 SNS는 글 작성 시점에 팔로워들의 피드 테이블에 미리 써두는 fan-out on write 전략으로 해결합니다.

언제 사용하는가

인덱스가 효과적인 경우

읽기 중심 워크로드: 주문 조회처럼 쓰기는 하루 한두 번이지만 조회는 수십 번인 경우, 인덱스의 쓰기 비용을 조회 성능 이점이 충분히 상쇄합니다.

필터 + 정렬 복합 쿼리: WHERE user_id = ? AND status = ? ORDER BY created_at DESC 같은 쿼리는 복합 인덱스 하나로 필터링과 정렬을 동시에 해결할 수 있습니다.

JOIN 최적화: follows(follower_id, followee_id) 같은 커버링 인덱스로 JOIN 비용을 대폭 줄일 수 있습니다.

인덱스가 비효율적인 경우

카디널리티가 극히 낮은 단독 인덱스: status ENUM(5개 값)에 단독 인덱스를 걸면 5,000만 건의 20%인 1,000만 건을 걸러내는 게 고작입니다. Full Table Scan과 별 차이 없고 인덱스 유지 비용만 추가됩니다.

쓰기 비율이 압도적인 워크로드: 초당 수만 건의 INSERT가 발생하는 로그 테이블에 인덱스를 3~4개 걸면 쓰기 처리량이 급감합니다.

컬럼이 과다한 테이블의 커버링 인덱스: 메타데이터 컬럼이 20개 이상인 경우, 커버링 인덱스를 만들면 인덱스 크기가 테이블 크기에 육박합니다. 쓰기 비용과 버퍼 풀 압박이 조회 성능 이점을 상쇄합니다.

실전 시나리오별 인덱스 개수 결정

두 쿼리가 서로 다른 인덱스를 요구하면, 인덱스를 몇 개 만들 것인가를 결정해야 합니다. 판단 기준은 읽기/쓰기 비율입니다:

트레이드오프

쓰기 비용

인덱스 N개는 매 INSERT마다 N+1개의 B+Tree를 갱신합니다 (클러스터드 인덱스 1개 + 세컨더리 인덱스 N개). 인덱스가 많을수록 쓰기 성능이 선형으로 저하됩니다.

메모리와 디스크 공간

세컨더리 인덱스는 별도의 B+Tree로 디스크 공간을 차지합니다. 버퍼 풀(InnoDB Buffer Pool)에도 인덱스 페이지가 올라와야 하므로, 인덱스가 많으면 테이블 데이터 페이지가 버퍼 풀에서 밀려나는 경합이 발생합니다.

OFFSET 페이지네이션 함정

SELECT * FROM tx_block_transactions
WHERE from_address = ?
ORDER BY block_id DESC
LIMIT 20 OFFSET 10000;  -- 10,001건을 읽고 10,000건 버림

OFFSET 10000이면 MySQL은 인덱스를 타고 10,020건을 읽은 뒤 앞의 10,000건을 버립니다. 페이지가 깊어질수록 선형으로 느려집니다. 커서 기반 페이지네이션(WHERE block_id < :lastBlockId)으로 전환하면 페이지 깊이와 무관하게 항상 인덱스 범위 스캔만으로 결과를 반환합니다.

Leftmost Prefix 위반 함정

(user_id, status, created_at DESC) 인덱스에서 user_id 없이 WHERE status = 'PENDING'만 쓰면 인덱스를 탈 수 없습니다. B+Tree는 왼쪽부터 순서대로 사용하므로 선두 컬럼이 WHERE 조건에 없으면 해당 인덱스는 무용지물입니다. 마찬가지로 중간 컬럼을 건너뛰면 그 뒤 컬럼의 정렬 보장이 깨집니다.

카디널리티 오해

"카디널리티 낮은 컬럼은 인덱스에 의미 없다"는 단독 인덱스에만 해당합니다. (user_id, status, created_at DESC)에서 status는 카디널리티가 5지만, user_id 등호 조건 뒤에서 추가 파티셔닝을 제공하므로 유효합니다.

마무리

인덱스 설계의 본질은 "B+Tree 리프 노드에서 데이터가 어떤 순서로 배치되는가"를 이해하는 것입니다. 디스크 I/O 경제학이라는 물리적 제약이 B+Tree의 구조를 결정했고, 그 리프 노드의 배치 원리를 알면 등호 먼저·정렬 마지막 원칙, 중간 컬럼 건너뛰기 함정, 커버링 인덱스의 장단점이 모두 자연스럽게 따라옵니다.

인덱스 개수는 읽기/쓰기 비율로 결정합니다. 모든 쿼리에 최적 인덱스를 거는 것이 정답이 아니라, 워크로드의 특성에 맞게 인덱스 비용과 조회 이점을 저울질하는 것이 실전 설계의 핵심입니다.

참고 자료

• Use The Index, Luke — Anatomy of an Index
• MySQL 8.0 Reference Manual — InnoDB Index Types
• Markus Winand — SQL Performance Explained
• Percona — Covering Index and Covering Query