인덱스 기본기 — 왜 빠른가, B-Tree, 카디널리티

만화로 보는 요약 — 먼저 읽어보세요

면접에서 자주 나오는 인덱스 3문항(① 왜 거는지 ② 어떻게 동작하는지 ③ 어떤 컬럼에 걸지)을 하나의 흐름으로 정리한다.

1. 인덱스를 왜 걸어야 하는가

인덱스가 없으면 DB는 조건에 맞는 행을 찾기 위해 테이블 전체를 처음부터 끝까지 읽는다 (full table scan). 행이 N개면 최악의 경우 N번 다 비교해야 하므로 O(N).

인덱스는 검색에 쓰는 컬럼 값들을 별도의 정렬된 자료구조(B-Tree)로 미리 만들어 둔 것이다. 정렬돼 있으므로 이진 탐색과 같은 방식으로 값을 찾을 수 있어 탐색 비용이 **O(log N)**으로 줄어든다. 테이블이 100만 건이면 풀스캔은 최악 100만 번 비교, B-Tree 인덱스는 약 20번 비교면 충분하다 — 이게 “인덱스를 걸어야 하는 이유”의 핵심이다.

-- 인덱스가 없으면 WHERE name = '홍길동' 은 전체 스캔
SELECT * FROM member WHERE name = '홍길동';

2. 인덱스 동작 방식 (B-Tree)

MySQL(InnoDB)은 기본적으로 B+Tree 구조를 인덱스로 사용한다.

• 정렬된 자료구조: 인덱스 컬럼 값을 오름차순으로 정렬해 트리 형태로 저장한다.
• 내부 노드(branch node): 실제 데이터는 없고, 어느 자식 노드로 내려가야 할지 판단하는 기준 값(라우팅 키)만 가진다.
• 리프 노드(leaf node): 실제 인덱스 값 + 그 값이 가리키는 실제 데이터 위치(PK 또는 row pointer)를 담는다. 리프 노드끼리는 linked list로 연결돼 있어서, 한 번 리프에 도달하면 옆으로 이동하며 범위 검색(BETWEEN, >, ORDER BY)도 순차적으로 처리할 수 있다.
• 탐색 과정: 루트 → 내부 노드 → 리프 노드로 내려가며 매 단계 범위를 좁힌다. 트리 높이가 h면 비교 횟수는 h에 비례하고, 트리는 균형(balanced) 상태를 유지하므로 h ≈ log(N) — 이것이 O(log N) 탐색의 실체다.

즉 “인덱스 = 정렬된 값 + 각 값이 가리키는 실제 행 위치를 트리로 관리하는 구조”라고 설명하면 된다.

3. 인덱스의 대가 (공짜가 아니다)

인덱스는 읽기(SELECT)를 빠르게 하는 대신 비용을 지불한다.

그래서 “조회 조건으로 자주 쓰이는 컬럼”에만 선별적으로 걸어야 하고, 아무 컬럼에나 인덱스를 걸면 쓰기 성능만 떨어뜨리는 역효과가 난다.

3-1. 쓰기 비용의 단위는 “인덱스 개수”가 아니다

같은 3개를 걸어도 키 값의 성질에 따라 비용이 크게 갈린다. B-Tree는 키 순서로 정렬된 자료구조라 삽입 위치가 곧 비용이기 때문이다.

**페이지 분할(page split)**은 꽉 찬 페이지 중간에 값을 끼워 넣어야 할 때 페이지를 반으로 쪼개 절반을 새 페이지로 옮기는 작업이다. I/O가 늘고 페이지 공간 점유율(fill factor)도 떨어져 인덱스가 더 커진다.

그래서 “인덱스를 3개 걸었으니 쓰기가 3배 비싸다”는 틀린 계산이다. 단조 증가 키 2개 + 난수 키 1개라면, 난수 키 하나가 나머지 둘을 합친 것보다 비쌀 수 있다. 쓰기 부하를 의심할 때 제일 먼저 볼 것은 개수가 아니라 난수 키 인덱스다.

3-2. 그럼에도 견디는 이유 — 체인지 버퍼

InnoDB는 non-unique 세컨더리 인덱스에 한해, 변경 대상 페이지가 버퍼풀에 없으면 즉시 적용하지 않고 체인지 버퍼에 적어 뒀다가 나중에 병합한다. 랜덤 쓰기를 매번 디스크 랜덤 I/O로 바꾸는 대신 모아서 처리하는 구조다.

전제가 둘이다. 유니크 인덱스에는 안 통한다(중복 검사를 하려면 어차피 페이지를 읽어야 한다). 그리고 대상 페이지가 이미 버퍼풀에 있으면 체인지 버퍼를 거치지 않는다. 자세히는 InnoDB Buffer Pool 4장.

📄 문서 기반 (미검증) — 3-1·3-2는 MySQL 문서 기준이며, 키 성질별 쓰기 비용 차이를 필자가 계측한 수치는 아직 없다.

4. 회원 테이블(name, age) — 어디에 인덱스를 걸까

핵심 개념은 카디널리티(cardinality) — 컬럼이 가질 수 있는 **값의 다양성(고유값 개수)**이다.

답: name에 인덱스를 거는 게 유리하다.

이유는 카디널리티가 낮은 컬럼(age)에 인덱스를 걸면, WHERE age = 30처럼 조회해도 “30살”인 행이 워낙 많아 B-Tree로 걸러봤자 매칭되는 행이 테이블의 상당 부분을 차지한다. 이 경우 옵티마이저는 인덱스를 타봤자 이득이 적다고 판단해 인덱스를 무시하고 풀스캔을 선택하기도 한다. 반면 name처럼 카디널리티가 높은 컬럼은 조건에 맞는 행이 소수로 좁혀지므로 인덱스의 이득(O(log N) 탐색 → 소수 행만 접근)이 극대화된다.

CREATE INDEX idx_member_name ON member (name);

예외: age를 범위 조건(age BETWEEN 20 AND 30)이나 정렬(ORDER BY age)에 자주 쓴다면 상황에 따라 age에도 인덱스가 유효할 수 있다. 하지만 “단일 컬럼 하나만 고른다”는 전제라면 카디널리티가 높은 name이 정답이다.

5. 복합 인덱스와 최좌측 접두사(leftmost prefix) — 짧게

(name, age)처럼 여러 컬럼을 묶은 복합 인덱스를 만들면, 정렬은 name 우선 → 그 안에서 age 순으로 이뤄진다. 이 인덱스는 왼쪽부터 순서대로 조건이 걸려야 탄다.

• WHERE name = '홍길동' → 인덱스 사용 가능 (leftmost)
• WHERE name = '홍길동' AND age = 30 → 인덱스 사용 가능
• WHERE age = 30 (name 없이 age만) → 이 인덱스 사용 불가 (중간 컬럼부터 시작 못 함)

그래서 복합 인덱스를 설계할 때는 “어떤 컬럼이 항상 먼저 조건으로 들어오는지”를 기준으로 컬럼 순서를 정한다.

6. 커버링 인덱스 — 왕복을 없앤다

세컨더리 인덱스 리프에 들어 있는 건 실제 행이 아니라 PK 값이다. 그래서 인덱스에서 값을 찾았다고 끝이 아니라, 그 PK로 클러스터드 인덱스를 다시 타고 내려가야 행에 닿는다. 이 두 번째 탐색을 테이블 접근(bookmark lookup)이라 한다.

① 세컨더리 인덱스 탐색 (높이 h)  →  PK 획득
② 클러스터드 인덱스 재탐색 (높이 h)  →  실제 행
③ (행이 페이지 절반을 넘을 만큼 크면) 오버플로 페이지 추가 읽기

③의 조건은 생각보다 훨씬 큽니다. “BLOB/JSON이면 항상”이 아니라 행 하나가 페이지의 절반을 넘을 때고, 실측하면 그 경계가 8KB 근처입니다 (✅ 실측: 한 스키마에서 8,105바이트까지 인라인, 8,106바이트부터 오버플로 — 5장. 모든 것은 16KB다). 2KB짜리 JSON은 오버플로가 아니라 페이지 안에 그대로 들어갑니다.

조회에 필요한 컬럼이 인덱스 안에 전부 있으면 ②가 통째로 사라진다. 이걸 커버링 인덱스라 하고, EXPLAIN의 Extra에 Using index로 나타난다.

-- (name, age) 인덱스가 있을 때
SELECT name, age FROM member WHERE name = '홍길동';   -- Using index (커버링)
SELECT * FROM member WHERE name = '홍길동';            -- 테이블 접근 발생

대가: 포함 컬럼만큼 인덱스가 커진다 → 쓰기 비용(3장)과 버퍼풀 점유가 함께 는다. 그래서 조회 패턴이 굳기 전에 넓게 잡으면 안 쓰이는 큰 인덱스가 남는다. 단건 조회처럼 결과가 몇 건뿐이면 왕복을 아끼는 이득 자체도 작다.

7. 옵티마이저가 인덱스를 안 쓰는 경우

4장에서 “옵티마이저가 인덱스를 무시하고 풀스캔을 고르기도 한다”고 했다. 그 판단의 근거가 통계인데, 이 통계는 전수 조사가 아니라 페이지 샘플링이다 (innodb_stats_persistent_sample_pages, 기본 20).

문제는 인덱스가 아예 없을 때다. 샘플링할 대상이 없으므로 옵티마이저는 카디널리티를 추정할 근거가 0이고, filtered에 **고정 상수 10%**를 꽂는다.

✅ 실측 (QR 결제 중계 운영 DB, 2026-08) — 인덱스가 PK뿐인 370만 행 로그 테이블에서 EXPLAIN이 rows=3,726,611 / filtered=10을 냈다. filtered가 컬럼 분포를 반영한 값이 아니라 10이라는 기본 상수였고, 실행계획의 추정 통과 행수도 그 10% 언저리(372,663)로 잡혔다. 실제 결과는 1행. 같은 쿼리의 EXPLAIN ANALYZE 실측은 45.36초(382만 행 스캔 후 1행 반환).

추정치가 실제와 37만 배 어긋난 것은 옵티마이저가 틀려서가 아니라 줄 수 있는 정보가 없어서다. 인덱스가 없으면 샘플링할 대상 자체가 없다.

인덱스를 만들어도 통계는 자동으로 정확해지지 않는다. 인덱스를 걸고도 type: ALL이 그대로 나오면 여기를 의심한다.

ANALYZE TABLE member;

통계 말고 인덱스를 아예 못 타게 만드는 흔한 패턴도 함께 알아둔다.

면접 30초 요약

“인덱스가 없으면 조건에 맞는 행을 찾으려고 테이블 전체를 순차 탐색해서 O(N)이 걸립니다. 인덱스는 컬럼 값을 정렬된 B-Tree로 미리 구성해 두는 구조라, 루트에서 리프까지 내려가며 범위를 좁혀 O(log N)에 찾을 수 있고, 리프 노드끼리 연결돼 있어 범위 검색도 빠릅니다. 다만 쓰기마다 인덱스도 같이 갱신해야 하고 저장 공간도 추가로 쓰니 아무 데나 걸면 안 됩니다. name/age 중 고른다면, 카디널리티(값의 다양성)가 높은 name에 인덱스를 겁니다. age는 값의 종류가 적어 인덱스를 걸어도 걸러지는 행이 적기 때문입니다.”

Related

• InnoDB Buffer Pool — 체인지 버퍼, 페이지 단위 캐싱, Young/Old LRU
• Database
• MySQL DATETIME vs TIMESTAMP