taeknology/notes

[MySQL] InnoDB 인덱스: B+Tree 구조 · Clustered · Covering Index 와 실행 계획 읽기

한 줄 요약: InnoDB의 모든 인덱스는 B+Tree 구조임. Primary Key는 테이블의 물리적 데이터 순서를 결정하는 Clustered Index이고, 나머지는 Secondary Index로 leaf에 PK 값을 담아 double lookup 구조를 형성함. SELECT 컬럼이 인덱스 leaf만으로 해결되면 PK lookup 없이 Extra: Using index(Covering Index)로 처리됨.

개요

InnoDB 테이블을 생성하면 데이터는 B+Tree 형태로 디스크에 정렬 저장됨. 인덱스를 “별도 자료구조”가 아니라 “테이블 그 자체”로 이해해야 쿼리 성능을 제대로 예측할 수 있음.

이 글이 다루는 범위:

  • B+Tree internal 노드·leaf 노드 구조와 페이지 크기
  • Clustered Index(Primary Key) 동작 원리 및 PK 선택 기준
  • Secondary Index의 double lookup 구조
  • Covering Index — Extra: Using index 조건
  • Multi-column Index leftmost prefix 규칙
  • EXPLAIN 출력에서 key, key_len, rows, Extra 읽는 법

결론

설계 Q&A

질문답변
Clustered Index란?PK 순서로 데이터를 물리 배치하는 InnoDB 고유 구조. 테이블 자체가 B+Tree임.
PK가 없으면?UNIQUE NOT NULL 컬럼을 Clustered Index로 씀. 그것도 없으면 MySQL이 내부 숨김 컬럼 GEN_CLUST_INDEX를 자동 생성함.
Sequential vs Random PK?AUTO_INCREMENT 같은 순차 PK는 leaf에 순서대로 삽입됨. UUID 같은 랜덤 PK는 삽입마다 중간 페이지를 쪼개는 page split이 발생해 fragmentation이 심해짐.
Secondary Index는 어떻게 동작하는가?leaf에 인덱스 컬럼 + PK 값을 저장함. 조회 시 Secondary Index → PK → Clustered Index 2단 탐색(double lookup)이 일어남.
Covering Index란?SELECT 컬럼 전부가 Secondary Index leaf에 있어 Clustered Index를 다시 읽지 않아도 되는 상태. Extra: Using index로 표시됨.
Multi-column Index에서 leftmost prefix 규칙은?(a, b, c) 인덱스는 a, (a, b), (a, b, c) 조건에서만 사용됨. b 단독·c 단독·(b, c) 조건에서는 인덱스를 활용하지 못함.

운영 시 기억할 것

  • PK는 짧고 순차적으로: 랜덤 UUID PK는 page split·fragmentation을 유발함. AUTO_INCREMENT 또는 순차 BIGINT 권장.
  • Covering Index를 노려라: SELECT 컬럼을 인덱스 정의에 포함하면 double lookup을 없앨 수 있음. Extra: Using index가 보이면 성공.
  • Multi-column Index 컬럼 순서: 선택도(cardinality) 높은 컬럼을 앞에, WHERE 조건에 반드시 포함되는 컬럼을 앞에 배치함.
  • key_len으로 prefix 사용 여부 확인: EXPLAIN의 key_len이 전체 인덱스 길이보다 짧으면 일부 컬럼만 사용 중임을 의미함.

상세

1. B+Tree 구조

InnoDB는 모든 인덱스를 B+Tree(Balanced Plus Tree) 로 저장함. B-Tree와 달리 B+Tree는 실제 데이터(또는 PK 포인터)를 leaf 노드에만 저장하고, internal 노드에는 검색 경로를 안내하는 키만 담음.

페이지 크기와 트리 높이: InnoDB의 기본 페이지 크기는 16KB(innodb_page_size = 16384). internal 노드는 [키 + child page pointer(6바이트)] 쌍을 담는데, INT(4바이트) PK 기준 한 쌍이 약 10바이트 → 16384 / 10 ≈ 1600 개의 키 포인터가 한 페이지에 들어감. fanout 1000+ 트리라서 수백만수억 row 를 담은 테이블도 일반적으로 트리 높이 3~4 level 로 처리됨. 즉 어떤 행을 찾아도 디스크 I/O 는 34회 이내임. PK 가 길어질수록 fanout 이 줄어 트리가 깊어지므로, PK 는 짧을수록 좋다 는 실무 원칙이 여기서 나옴.

2. Clustered Index

InnoDB에서 테이블 데이터 자체가 B+Tree의 leaf임. 이 B+Tree를 Clustered Index라고 부름. 데이터가 Primary Key 순서로 물리 정렬되어 저장됨.

이 그림이 말하는 세 가지:

  • Root / Internal 노드: separator key 만 보관, 실제 행 데이터는 없음 — 어느 leaf 로 내려갈지 안내만 함
  • Leaf 노드 = 테이블의 행 그 자체: PK 컬럼(id) + 나머지 모든 컬럼(dept, name, salary) 전부 들어있음. 별도의 “데이터 파일” 이 따로 존재하지 않음
  • Leaf 끼리 prev/next 양방향 링크: WHERE id BETWEEN 1 AND 3 같은 range scan 시 트리를 다시 타지 않고 leaf 만 순서대로 따라가면 됨

PK 선택 우선순위 (MySQL 8.4 — Clustered and Secondary Indexes):

  1. PRIMARY KEY 명시 컬럼
  2. 첫 번째 UNIQUE NOT NULL 인덱스
  3. 둘 다 없으면 InnoDB가 숨김 컬럼 GEN_CLUST_INDEX를 내부 생성. MySQL 8.0.30+ 에서는 sql_generate_invisible_primary_key=ON 으로 PK 없는 테이블에 자동으로 가시 PK(my_row_id)를 부여하는 GIPK 기능이 별도로 추가됨.

Sequential PK vs Random PK

AUTO_INCREMENT 같은 순차 PK는 항상 leaf의 오른쪽 끝에 새 행을 추가함. 기존 페이지는 건드리지 않음.

UUID 같은 랜덤 PK는 삽입 위치가 무작위임. 중간 페이지가 꽉 찬 상태에서 삽입이 발생하면 page split — 페이지를 반으로 쪼개는 작업 — 이 일어남. 이 과정이 반복되면 페이지가 절반만 채워진 상태로 늘어나는 fragmentation이 심해지고, 불필요한 I/O와 공간 낭비가 생김.

3. Secondary Index

Primary Key 외의 모든 인덱스를 Secondary Index라고 함. Secondary Index의 leaf는 인덱스 컬럼 값 + PK 값을 저장함. 행 데이터 전체를 복사하지 않음.

점선 화살표 = PK lookup. Secondary Index 가 본 PK 값으로 Clustered Index 의 해당 leaf 를 다시 찾아가는 과정임. 맨 아래 Secondary leaf(id=1) 가 맨 위 Clustered leaf 로 점프하듯 화살표가 멀리 교차하는 게 핵심 — Secondary Index 의 행 순서와 Clustered Index 의 물리 배치가 일치하지 않아 무작위 I/O 가 발생함. Covering Index 가 강력한 이유는 바로 이 단계를 통째로 생략하기 때문임.

Secondary Index 조회 흐름:

  1. Secondary Index B+Tree를 탐색해 해당 조건의 leaf 노드를 찾음
  2. leaf에서 PK 값을 꺼냄
  3. PK 값으로 Clustered Index를 다시 탐색해 실제 행 데이터를 가져옴 (double lookup)

이 2단 탐색이 Secondary Index의 기본 비용임. SELECT 컬럼이 많을수록 3번 단계의 I/O가 커짐.

4. Covering Index

Secondary Index의 leaf에 SELECT에 필요한 컬럼이 이미 모두 포함되어 있으면, 3번 단계(Clustered Index lookup)를 생략할 수 있음. 이 상태를 Covering Index라고 함.

EXPLAIN의 Extra 컬럼에 Using index가 표시되면 Covering Index로 처리된 것임.

-- idx_dept_salary(dept_id, salary) 인덱스가 있을 때
-- SELECT 컬럼이 dept_id, salary만 → Covering Index
EXPLAIN SELECT dept_id, salary FROM employees WHERE dept_id = 3;
type: ref | key: idx_dept_salary | key_len: 4 | Extra: Using index

name 컬럼처럼 인덱스에 없는 컬럼을 SELECT에 추가하는 순간 double lookup으로 전환됨:

-- name은 idx_dept_salary에 없음 → double lookup
EXPLAIN SELECT dept_id, salary, name FROM employees WHERE dept_id = 3;
type: ref | key: idx_dept | key_len: 4 | Extra: NULL

Extra: NULL은 Clustered Index까지 접근했음을 뜻함.

5. Multi-column Index와 Leftmost Prefix

(a, b, c) 형태의 복합 인덱스는 컬럼 순서의 왼쪽부터 연속적으로 조건에 사용될 때만 활용됨. 이를 leftmost prefix 규칙이라고 함 (MySQL 8.4 — Multiple-Column Indexes).

WHERE 조건인덱스 사용 여부비고
a = ?사용 가능leftmost prefix
a = ? AND b = ?사용 가능leftmost prefix
a = ? AND b = ? AND c = ?사용 가능전체 키
b = ?사용 불가leftmost 아님
b = ? AND c = ?사용 불가leftmost 아님
a = ? AND c = ?a 부분만 사용b가 빠져 c는 활용 불가

Cardinality(선택도): 컬럼 값의 종류가 많을수록(high cardinality) 인덱스 효율이 높음. (dept_id, salary) 인덱스라면 dept_id는 10개 부서밖에 없는 low cardinality이므로, 실무에서는 선택도 높은 컬럼을 앞쪽에 두는 설계가 일반적임. 실제로 시나리오 1 의 dept_id = 3 결과가 rows: 950 으로 나온 것도 약 10개 부서 균등 분포(10000행 / 10 ≈ 1000행) 가 반영된 수치임.

테스트

MySQL 8.4.8 환경에서 직접 확인함.

환경

SELECT @@innodb_page_size AS innodb_page_size, VERSION() AS version;
innodb_page_size  version
16384             8.4.8

MySQL 8.4.8 에서 직접 확인 — innodb_page_size 기본값 16384(16KB).

테스트 테이블

CREATE TABLE employees (
  id        INT NOT NULL AUTO_INCREMENT,
  dept_id   INT NOT NULL,
  name      VARCHAR(50) NOT NULL,
  salary    INT NOT NULL,
  PRIMARY KEY (id),
  INDEX idx_dept (dept_id),
  INDEX idx_dept_salary (dept_id, salary),
  INDEX idx_name_dept_salary (name, dept_id, salary)
) ENGINE=InnoDB;

10000행 삽입 후 각 시나리오를 확인함.

시나리오 1 — Index Lookup (type: ref)

Secondary Index 등치 조건은 인덱스를 통해 해당 행들에만 곧장 접근함:

EXPLAIN SELECT * FROM employees WHERE dept_id = 3;
type: ref | key: idx_dept | key_len: 4 | rows: 950 | Extra: NULL

type: ref는 인덱스 등치 조건 탐색임. rows: 950은 전체 10000행 중 약 950행만 읽음을 뜻함 — 인덱스가 없었다면 type: ALL(full table scan)로 10000행 전체를 훑어야 했을 것임. idx_name_dept_salary 같은 복합 인덱스에서 leftmost prefix 가 깨지면 type: index(full index scan)로 떨어지는데, 이 케이스는 시나리오 3 에서 따로 다룸.

시나리오 2 — Covering Index (Extra: Using index)

SELECT 컬럼이 idx_dept_salary(dept_id, salary) leaf에 모두 포함될 때:

EXPLAIN SELECT dept_id, salary FROM employees WHERE dept_id = 3;
type: ref | key: idx_dept_salary | key_len: 4 | rows: 950 | Extra: Using index

Extra: Using index — Clustered Index lookup 없이 Secondary Index leaf만으로 결과를 완성함.

name 컬럼을 추가하면 인덱스 leaf에 없으므로 Covering Index가 깨짐:

EXPLAIN SELECT dept_id, salary, name FROM employees WHERE dept_id = 3;
type: ref | key: idx_dept | key_len: 4 | rows: 950 | Extra: NULL

Extra: NULL — Secondary Index → Clustered Index 2단 탐색(double lookup)이 발생함.

시나리오 3 — Multi-column Index Leftmost Prefix

idx_dept_salary(dept_id, salary) 인덱스를 대상으로 prefix 조건별 동작을 확인함:

leftmost 1컬럼 (dept_id만):

EXPLAIN SELECT dept_id, salary FROM employees WHERE dept_id = 5;
type: ref | key: idx_dept_salary | key_len: 4 | rows: 1017 | Extra: Using index

leftmost 2컬럼 (dept_id + salary):

EXPLAIN SELECT dept_id, salary FROM employees WHERE dept_id = 5 AND salary > 60000;
type: range | key: idx_dept_salary | key_len: 8 | rows: 581 | Extra: Using where; Using index

key_len: 8(INT 4바이트 × 2)로 두 컬럼 모두 사용됨. rows도 581로 줄어듦.

leftmost 미충족 (salary만):

EXPLAIN SELECT * FROM employees WHERE salary > 60000;
type: index | key: idx_name_dept_salary | key_len: 210 | rows: 9834 | Extra: Using where; Using index

salary 단독 조건은 leftmost prefix가 아니라 idx_dept_salary를 사용하지 못하고, 옵티마이저가 다른 인덱스를 full scan함.

key_len 으로 prefix 사용량 역산하기:

WHERE 조건keykey_len사용 컬럼 수
dept_id = 5idx_dept_salary41 (dept_id)
dept_id = 5 AND salary > 60000idx_dept_salary82 (dept_id + salary)
salary > 60000idx_name_dept_salary (full scan)210leftmost 미충족 — 전 인덱스 순회

INT 컬럼 1개당 key_len: 4 이므로 4 → 8 변화는 곧 “두 번째 컬럼까지 인덱스가 활용됨” 신호임. EXPLAIN 의 key_len 만 보고도 옵티마이저가 prefix 를 어디까지 썼는지 역산 가능함.

시나리오 4 — Using index condition (ICP)

SELECT * 이므로 Covering Index가 아니지만, range 조건을 스토리지 엔진 레벨에서 평가하는 Index Condition Pushdown(ICP) 가 동작함:

EXPLAIN SELECT * FROM employees WHERE dept_id BETWEEN 1 AND 3 AND salary > 60000;
type: range | key: idx_dept_salary | key_len: 8 | rows: 2534 | Extra: Using index condition

Using index condition — salary > 60000 필터를 스토리지 엔진이 인덱스에서 직접 평가한 뒤 조건을 만족하는 행만 MySQL 서버 레이어로 올림. Clustered Index 접근 횟수를 줄이는 효과가 있음.

시나리오 5 — Clustered Index 선택 우선순위 (PK / UNIQUE / GEN_CLUST_INDEX)

PK 가 없을 때 InnoDB 가 무엇을 Clustered Index 로 잡는지 직접 검증함. 세 가지 케이스를 만들어 비교함.

CREATE TABLE t_pk   (id  BIGINT PRIMARY KEY,         v VARCHAR(20)) ENGINE=InnoDB;
CREATE TABLE t_uniq (uid BIGINT NOT NULL UNIQUE,     v VARCHAR(20)) ENGINE=InnoDB;
CREATE TABLE t_none (                                v VARCHAR(20)) ENGINE=InnoDB;

① information_schema.INNODB_INDEXES — 가장 결정적인 증거

SELECT t.NAME AS table_name, i.NAME AS index_name, i.TYPE
FROM information_schema.INNODB_INDEXES i
JOIN information_schema.INNODB_TABLES  t ON i.TABLE_ID = t.TABLE_ID
WHERE t.NAME IN ('test/t_pk','test/t_uniq','test/t_none')
ORDER BY t.NAME;
table_name    index_name        TYPE
test/t_none   GEN_CLUST_INDEX   1
test/t_pk     PRIMARY           3
test/t_uniq   uid               3

TYPE 비트값: 1 = clustered, 2 = unique, 3 = clustered + unique.

  • t_pk → Clustered Index 이름이 PRIMARY, TYPE=3
  • t_uniq → Clustered Index 이름이 uid (UNIQUE NOT NULL 컬럼이 그대로 PK 역할), TYPE=3
  • t_none → GEN_CLUST_INDEX 가 만들어지고 TYPE=1 (clustered 만, 유니크 비트 없음)

숨김 PK 가 만들어졌는지 단정 짓는 가장 명확한 신호임.

② SHOW EXTENDED COLUMNS — 숨김 컬럼 DB_ROW_ID 노출

SHOW EXTENDED COLUMNS FROM t_none;
Field         Type
v             varchar(20)
DB_ROW_ID
DB_TRX_ID
DB_ROLL_PTR

t_pk, t_uniq 에는 DB_TRX_ID · DB_ROLL_PTR 만 보이고, t_none 에만 DB_ROW_ID 가 추가됨. 이게 GEN_CLUST_INDEX 의 실체 — 6바이트 단조 증가 정수.

③ EXPLAIN 으로는 직접 확인 불가

EXPLAIN SELECT * FROM t_none;
type: ALL | key: NULL | rows: 3 | Extra: NULL

세 테이블 모두 full scan 시 key=NULL 로 동일하게 표시됨. 쿼리 플랜에는 GEN_CLUST_INDEX 라는 이름이 노출되지 않음. EXPLAIN 만으로는 숨김 PK 사용 여부를 단정하지 못함.

확인 방법 정리

방법무엇이 보이는가신뢰도
information_schema.INNODB_INDEXESClustered Index 이름과 TYPE 비트결정적
SHOW EXTENDED COLUMNSDB_ROW_ID 숨김 컬럼 등장 여부결정적
information_schema.STATISTICS유저가 만든 인덱스만 노출 — 출력 없으면 GEN_CLUST_INDEX 의심간접 신호
EXPLAIN / EXPLAIN FORMAT=JSONkey=NULL 만 표시도움 안 됨

MySQL 8.4.8 에서 직접 확인.

EXPLAIN 주요 컬럼 정리

컬럼의미체크 포인트
key실제 사용된 인덱스 이름NULL이면 인덱스 미사용
key_len사용된 인덱스 바이트 수Multi-column 인덱스에서 몇 컬럼이 쓰였는지 역산 가능
rows옵티마이저 예상 접근 행 수실제 행 수와 다를 수 있음(통계 기반 추정치)
Extra: Using indexCovering Index — Clustered Index 미접근목표 상태
Extra: Using index conditionICP — 스토리지 엔진이 인덱스에서 조건 평가double lookup 횟수 감소
Extra: Using whereMySQL 서버 레이어에서 WHERE 필터링인덱스로 걸러내지 못한 조건이 있음
Extra: Using filesort인덱스 순서와 다른 정렬 필요ORDER BY 컬럼이 인덱스에 없는 경우 발생

MySQL 8.4.8 에서 직접 확인.

참고

관련 글