[MySQL] 인덱스 동작 원리: B+Tree, 클러스터드 인덱스 vs 세컨더리 인덱스

[MySQL] 인덱스 동작 원리: B+Tree, 클러스터드 인덱스 vs 세컨더리 인덱스

"인덱스 걸면 빨라진다"는 다 아는데, 왜 빨라지는지, 왜 어떤 쿼리는 인덱스가 있어도 안 빨라지는지는 구조를 알아야 보여요. MySQL(InnoDB) 인덱스의 바탕은 두 가지예요 — B+Tree라는 자료구조와, "테이블 자체가 PK 인덱스"라는 클러스터드 구조요. 이 둘만 잡으면 인덱스 설계·실행계획·UUID 기본키 문제까지 전부 한 줄로 꿰어져요.

이 글은 MySQL 시리즈의 기둥이에요. B+Tree가 왜 빠른지, 클러스터드와 세컨더리 인덱스가 어떻게 다른지, 인덱스에 어떤 비용이 따르는지 하나씩 풀어 볼게요.

01. B+Tree, 정렬을 유지하는 얕은 트리

인덱스는 B+Tree로 저장돼요. 특징이 세 가지예요.

• 얕아요. 노드 하나(페이지, 16KB)에 키가 수백 개씩 들어가서, 수억 건짜리 테이블도 트리 높이가 3~4 정도예요. 단건 조회는 최악의 경우에도 디스크 접근 3~4번이면 끝나요. 루트·브랜치 노드는 보통 버퍼 풀에 상주해서 실제론 더 적고요. 풀 스캔의 O(N)이 트리 탐색으로 바뀌는 게 인덱스가 빠른 이유 전부예요.
• 리프가 정렬돼 있어요. 데이터(키)는 항상 정렬 상태로 유지돼요.
• 리프끼리 연결돼 있어요. 시작점을 찾으면 옆으로 쭉 읽을 수 있어요. BETWEEN·>= 같은 범위 검색과 ORDER BY가 인덱스로 빨라지는 이유예요.

"정렬된 채로 유지된다"는 게 핵심이에요. 검색뿐 아니라 정렬·범위·그룹핑까지, 인덱스의 모든 활용이 이 정렬에서 나와요. 그리고 뒤에서 볼 비용(페이지 분할)도 이 정렬을 유지하는 대가예요.

02. 클러스터드 인덱스, 테이블이 곧 PK 트리

InnoDB의 결정적인 특징이 있어요. 테이블 데이터 자체가 PK 순서로 정렬된 B+Tree로 저장돼요. 이게 클러스터드 인덱스예요. "테이블 따로, 인덱스 따로"가 아니라, PK 인덱스의 리프 노드에 행 데이터 전체가 들어 있어요.

그래서 PK 조회(WHERE id = ?)는 트리를 한 번 타면 행까지 바로 도달해요. 가장 빠른 조회 경로예요.

PK가 아닌 컬럼에 거는 인덱스는 전부 세컨더리 인덱스예요. 여기에 중요한 구조가 있어요. 세컨더리 인덱스의 리프에는 행의 위치가 아니라 PK 값이 저장돼요. 그래서 세컨더리 인덱스로 조회하면 두 번 찾아요.

• ① 세컨더리 인덱스 트리에서 조건에 맞는 키를 찾아 PK를 얻고
• ② 그 PK로 클러스터드 인덱스를 다시 타서 행을 가져와요

이 두 번째 단계가 "다시 테이블로 돌아간다"고 해서 흔히 북마크 룩업·테이블 접근이라 불러요. 조회 결과가 많을수록 이 왕복이 N번 일어나서, 세컨더리 인덱스를 탔는데도 느린 경우의 정체가 대개 이거예요.

이 구조에서 실무 원칙 두 개가 바로 나와요. 첫째, PK는 작게. 모든 세컨더리 인덱스가 리프마다 PK를 복사해 들고 있으니, PK가 크면(예: 긴 문자열) 모든 인덱스가 같이 비대해져요. 둘째, PK는 증가하는 값으로. 테이블이 PK순 정렬이라, 랜덤한 PK(UUID v4)는 삽입 위치가 매번 무작위라 페이지 분할이 끊임없이 일어나요. JPA ID 전략 편에서 "랜덤 UUID 기본키 금물"이라 한 이유가 바로 이 구조예요.

03. 커버링 인덱스 맛보기

두 번 찾기가 비싸다면, 한 번에 끝낼 수도 있을까요? 있어요. 쿼리가 필요로 하는 컬럼이 전부 인덱스 안에 있으면, 클러스터드로 돌아갈 필요 없이 인덱스만 읽고 끝나요. 이게 커버링 인덱스예요.

-- (user_id, status) 인덱스가 있을 때
SELECT user_id, status FROM orders WHERE user_id = 7;
-- 필요한 컬럼이 인덱스에 다 있음 → 테이블 접근 0번 (Using index)

세컨더리 리프에 PK가 들어 있다는 구조 덕분에, SELECT id, user_id ...처럼 PK를 포함해도 커버링이 돼요. 설계 편에서 이걸 무기로 깊게 다뤄요.

04. 인덱스의 비용, 공짜가 아니에요

인덱스는 읽기를 사고 쓰기로 지불하는 거래예요.

• 쓰기 비용 — INSERT·UPDATE·DELETE마다 관련된 모든 인덱스를 같이 갱신해요. 인덱스가 5개면 한 건 쓰기에 트리 5개를 손봐요. 정렬 유지를 위해 페이지가 꽉 차면 쪼개는(페이지 분할) 비용도 있고요.
• 공간 비용 — 인덱스도 디스크를 차지하고, 더 중요하게는 메모리(버퍼 풀)를 데이터와 나눠 써요. 인덱스가 많으면 정작 자주 쓰는 데이터가 메모리에서 밀려요.

그래서 "일단 다 걸어두자"는 안 돼요. 안 쓰는 인덱스는 읽기에는 무용하고 쓰기에는 순수 비용이에요. 어떤 컬럼에 어떤 순서로 걸지는 다음 편(인덱스 설계)의 주제예요.

05. 자주 만나는 질문

인덱스를 탔는데도 느려요

조회 결과가 많아 두 번 찾기(테이블 접근)가 N번 반복되는 경우가 흔해요. 커버링 인덱스로 테이블 접근을 없애거나, 애초에 조건을 더 좁히는 방향을 봐요. 실행계획으로 확인하는 법은 EXPLAIN 편에서 다뤄요.

PK를 UUID로 했더니 insert가 갈수록 느려져요

랜덤 PK의 페이지 분할이에요. 클러스터드 구조상 PK는 증가하는 값(auto_increment·UUID v7·TSID)이 유리해요.

LIKE '%검색어%'는 왜 인덱스를 못 타나요

B+Tree는 정렬 기반이라 "앞부분"이 고정돼야 탐색 시작점을 잡아요. 앞에 %가 붙으면 시작점이 없어 풀 스캔이에요. LIKE '검색어%'(전방 일치)는 타요. 이런 "인덱스를 못 타는 조건" 모음은 설계 편에서 정리해요.

두 구조에서 다 따라 나온다

MySQL 인덱스의 바탕은 둘이에요. B+Tree는 정렬을 유지하는 얕은 트리라 단건·범위·정렬이 다 빠르고, 클러스터드 구조는 테이블 자체가 PK 트리라 세컨더리 인덱스가 PK를 들고 두 번 찾기를 해요. 여기서 실무 원칙이 줄줄이 나와요.

• PK는 작게 — 모든 세컨더리 인덱스가 PK를 복사해 들고 있어요.
• PK는 증가하는 값으로 — 랜덤 PK는 페이지 분할을 부르니까요.
• 커버링이면 테이블 접근 생략 — 필요한 컬럼이 인덱스에 다 있으면 두 번 찾기가 사라져요.
• 인덱스는 쓰기 비용 — 안 쓰는 인덱스는 순수 손해예요.

이게 시리즈의 기둥이에요. 이 구조 위에 복합 인덱스 설계(컬럼 순서·커버링·카디널리티)를 다음 편에서 얹고, ORM 쪽 성능은 JPA 트러블슈팅 시리즈와 이어져요.

출처: MySQL — Clustered and Secondary Indexes · MySQL — How MySQL Uses Indexes