MySQL 인덱스는 어떻게 찾는가: InnoDB B+Tree와 풀 스캔

MySQL 인덱스가 빠른 이유를 한 문장으로 줄이면 조건에 맞는 행을 찾기 위해 읽어야 할 페이지를 줄이기 때문이다. 다만 “인덱스가 있으면 B+Tree를 몇 번 내려가 바로 한 행을 찾는다”는 설명만으로는 부족하다. 실제 비용은 저장 엔진, 인덱스 종류, 조건이 반환하는 행 수, 버퍼 풀 적중 여부와 테이블 행을 다시 읽는 횟수에 따라 달라진다.

이 글의 예제는 MySQL 8.4의 기본 저장 엔진인 InnoDB와 일반 B-tree 인덱스를 기준으로 한다. 전문 검색·공간 인덱스·MEMORY 엔진의 해시 인덱스는 동작 방식이 다르다.

풀 테이블 스캔은 언제 일어나는가

다음 테이블에서 email에 별도 인덱스가 없다고 가정해 보자.

CREATE TABLE users (
    id BIGINT PRIMARY KEY,
    name VARCHAR(50) NOT NULL,
    email VARCHAR(255) NOT NULL,
    created_at DATETIME NOT NULL
) ENGINE = InnoDB;

SELECT *
FROM users
WHERE email = 'chaaany@example.com';

옵티마이저가 사용할 만한 인덱스를 찾지 못하면 테이블을 훑으며 각 행에 조건을 적용할 수 있다. MySQL 실행 계획에서는 보통 Table scan 또는 전통 형식의 type=ALL로 확인한다.

풀 스캔 자체가 언제나 잘못은 아니다. 테이블이 작거나, 조건에 맞는 행이 전체의 대부분이거나, 읽어야 할 열이 많다면 인덱스를 오간 뒤 테이블 행을 다시 찾는 것보다 순차적으로 읽는 편이 저렴할 수 있다. 중요한 질문은 “스캔을 했는가”가 아니라 예상한 것보다 많은 행과 페이지를 읽었는가다.

InnoDB에서 테이블과 인덱스의 관계

InnoDB 테이블은 기본 키를 기준으로 조직된 클러스터드 인덱스다. 별도의 보조 인덱스는 보조 키 값과 해당 행의 기본 키를 저장한다.

보조 인덱스(email)
email 값 → 기본 키 id
              ↓
클러스터드 인덱스(PRIMARY KEY)
id → 전체 행

따라서 email 보조 인덱스로 SELECT *을 처리하면 대체로 두 단계가 필요하다.

1. email 인덱스에서 일치하는 엔트리를 찾는다.
2. 엔트리에 들어 있는 기본 키로 클러스터드 인덱스의 전체 행을 찾는다.

이 두 번째 접근을 흔히 테이블 조회 또는 row lookup이라고 부른다. 반환 행이 매우 많으면 이 반복 접근이 비싸져 옵티마이저가 풀 스캔을 선택할 수 있다.

B+Tree라는 설명에서 꼭 남길 것

MySQL 문서는 일반적으로 인덱스 구조를 B-tree라고 표현한다. InnoDB의 구현을 이해할 때는 키를 정렬된 페이지에 저장하고, 내부 페이지를 따라 리프 페이지로 내려가며, 리프 페이지가 순서대로 연결된 B+Tree 계열 구조로 생각하면 유용하다.

핵심은 세 가지다.

• 한 노드에 키 하나만 두는 이진 트리가 아니라, 한 페이지에 여러 키를 담는다.
• 루트와 내부 페이지는 어느 자식 페이지로 갈지 좁힌다.
• 정렬된 리프 페이지 덕분에 시작점을 찾은 뒤 범위를 이어서 읽을 수 있다.

email = ? 같은 동등 조건은 목표 키가 있을 법한 리프 페이지까지 탐색한다. created_at >= ? AND created_at < ? 같은 범위 조건은 시작 키를 찾은 뒤 범위가 끝날 때까지 리프 엔트리를 읽는다.

여기서 “1,000만 행도 루트·브랜치·리프 세 번이면 끝난다”처럼 횟수를 고정하면 안 된다. 트리 높이와 페이지 접근 비용은 키 길이, 페이지 크기, 데이터량, 캐시 상태에 따라 달라진다. 리프를 찾은 뒤 몇 개의 행을 반환하는지도 전체 비용에 큰 영향을 준다.

인덱스를 추가한 뒤 무엇이 달라지는가

email 조회가 충분히 자주 발생하고 결과가 적다면 다음 인덱스가 후보가 된다.

CREATE INDEX idx_users_email ON users (email);

실행 계획은 추측하지 말고 직접 비교한다.

EXPLAIN FORMAT=TREE
SELECT *
FROM users
WHERE email = 'chaaany@example.com';

EXPLAIN ANALYZE
SELECT *
FROM users
WHERE email = 'chaaany@example.com';

EXPLAIN은 옵티마이저가 고른 계획과 추정치를 보여 준다. EXPLAIN ANALYZE는 쿼리를 실제로 실행해 반복 횟수, 반환 행 수와 시간을 함께 보여 준다. 변경을 일으키는 문장에 사용할 때는 실제 실행된다는 점을 먼저 확인해야 한다.

비교할 항목은 다음과 같다.

• Table scan이 Index lookup 또는 Index range scan으로 바뀌었는가
• 추정 행 수와 실제 행 수의 차이가 큰가
• 인덱스에서 찾은 뒤 테이블 행을 몇 번 다시 읽는가
• 첫 행까지 걸린 시간과 전체 반복 시간이 어디에서 커지는가

실행 계획 하나의 시간이 곧 운영 성능은 아니다. 콜드 캐시와 웜 캐시, 동시 요청, 데이터 분포가 다르면 결과도 달라진다. 같은 데이터와 조건에서 여러 번 재고, 운영 쿼리의 빈도와 지연 분포를 함께 봐야 한다.

풀 스캔과 인덱스 스캔을 고르는 판단 기준

상황	먼저 의심할 계획	확인할 것
유일한 이메일 한 건 조회	인덱스 lookup	실제 반환 행 수, unique 제약 필요 여부
한 달치 가입자 범위 조회	인덱스 range scan	기간이 전체에서 차지하는 비율
전체 사용자의 80% 조회	table scan 가능	테이블 재조회 비용과 읽는 열 수
아주 작은 기준 테이블 조회	table scan 가능	인덱스 유지 비용보다 이득이 있는지
통계와 실제 분포가 크게 다름	비효율적인 계획 가능	ANALYZE TABLE, 추정 행 수

이 판단을 “인덱스가 있느냐”만으로 끝내지 않는 것이 중요하다. 인덱스는 가능한 접근 경로를 늘려 주지만, 최종 계획은 옵티마이저가 비용을 비교해 선택한다.

단일 컬럼 인덱스의 선택도와 정렬 활용은 MySQL 단일 인덱스가 유효한 조건, 여러 조건의 컬럼 순서는 MySQL 복합 인덱스 설계 기준에서 이어서 볼 수 있다.

참고 자료

• MySQL 8.4: How MySQL Uses Indexes
• MySQL 8.4: InnoDB 소개
• MySQL 8.4: Column Indexes
• MySQL 8.4: EXPLAIN Statement