MySQL B+Tree 인덱스 구조 심화

InnoDB 인덱스 구조

MySQL InnoDB의 모든 인덱스는 B+Tree 자료구조로 구현됩니다. B+Tree를 이해하면 쿼리가 왜 빠른지, 왜 느린지, 인덱스를 어떻게 설계해야 하는지 근본적으로 파악할 수 있습니다. InnoDB는 클러스터드 인덱스(Clustered Index)와 세컨더리 인덱스(Secondary Index) 두 종류의 B+Tree를 사용합니다.

이 글에서는 B+Tree의 내부 구조, 클러스터드 vs 세컨더리 인덱스, 인덱스 스캔 방식, 복합 인덱스의 정렬 원리, 그리고 인덱스 설계 안티패턴까지 심층적으로 다룹니다. MySQL InnoDB MVCC 동작 원리와 함께 읽으면 InnoDB 내부 구조의 전체 그림을 이해할 수 있습니다.

B+Tree 기본 구조

-- B+Tree 특징 (B-Tree와의 차이)
-- 1. 데이터는 리프 노드에만 저장 (내부 노드는 키+포인터만)
-- 2. 리프 노드끼리 양방향 링크드 리스트로 연결
-- 3. 모든 리프 노드는 같은 깊이 (균형 트리)

-- InnoDB 페이지 크기: 기본 16KB
-- 한 페이지 = B+Tree의 한 노드

-- 예: INT(4바이트) PK + 포인터(6바이트) = 10바이트/엔트리
-- 내부 노드 한 페이지: 16384 / 10 ≈ 1,600개 키
-- 리프 노드 한 페이지: 행 크기에 따라 다름

-- 트리 깊이별 저장 가능 행 수:
-- 깊이 2 (루트 + 리프):          1,600 × 리프당 행 수
-- 깊이 3 (루트 + 내부 + 리프):   1,600 × 1,600 × 리프당 행 수
-- 깊이 4:                         1,600^3 × 리프당 행 수

-- 예: 행 크기 100바이트, 리프당 약 160행
-- 깊이 3: 1,600 × 1,600 × 160 ≈ 4억 행!
-- → 4억 행에서 PK 검색 = 디스크 I/O 3번 (루트는 보통 캐시됨 → 실제 2번)

       [루트 노드: 10, 20, 30]
      /         |         
 [1-9]      [10-19]     [20-30]      ← 내부 노드 (키+포인터)
  /         /           / 
[1,2,3] [4,5,6] [10,11] [15,16] ... ← 리프 노드 (실제 데이터)
  ↔       ↔       ↔       ↔          ← 양방향 링크

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

항목	클러스터드 인덱스	세컨더리 인덱스
리프 노드 내용	전체 행 데이터	인덱스 키 + PK 값
테이블당 개수	1개 (PK = 클러스터드)	여러 개 가능
데이터 정렬	PK 순서로 물리 정렬	인덱스 키 순서로 정렬
전체 행 접근	리프 노드에서 바로	PK로 클러스터드 재검색 필요

CREATE TABLE users (
  id BIGINT PRIMARY KEY,        -- 클러스터드 인덱스
  email VARCHAR(100),
  name VARCHAR(50),
  age INT,
  INDEX idx_email (email),      -- 세컨더리 인덱스
  INDEX idx_age (age)           -- 세컨더리 인덱스
);

-- 클러스터드 인덱스 B+Tree (PK 기준)
-- 리프 노드: [id=1 | email='a@mail.com' | name='Alice' | age=25]
--            [id=2 | email='b@mail.com' | name='Bob'   | age=30]
-- → 행 전체 데이터가 PK 순서대로 저장됨

-- 세컨더리 인덱스 (idx_email) B+Tree
-- 리프 노드: [email='a@mail.com' | PK=1]
--            [email='b@mail.com' | PK=2]
-- → email 정렬 + PK 값만 저장

-- 세컨더리 인덱스로 검색 시 과정:
SELECT * FROM users WHERE email = 'b@mail.com';
-- 1단계: idx_email B+Tree에서 email='b@mail.com' → PK=2 찾음
-- 2단계: 클러스터드 인덱스에서 PK=2 → 전체 행 데이터 가져옴
-- → 이 2단계를 "북마크 룩업(Bookmark Lookup)" 또는 "테이블 룩업"이라 함

PK 설계가 중요한 이유

-- 클러스터드 인덱스 = 테이블 자체의 물리적 정렬 순서
-- PK 선택이 전체 성능에 영향

-- ✅ 좋은 PK: AUTO_INCREMENT BIGINT
-- → 항상 끝에 INSERT → 페이지 분할(page split) 없음
-- → 순차적 I/O, 높은 캐시 히트율

-- ❌ 나쁜 PK: UUID (랜덤)
-- → 랜덤 위치에 INSERT → 빈번한 페이지 분할
-- → 랜덤 I/O, 낮은 캐시 히트율, 세컨더리 인덱스 비대화

-- PK 크기의 영향
-- 모든 세컨더리 인덱스 리프에 PK가 복사됨!
-- PK = BIGINT(8바이트) vs PK = UUID(36바이트)
-- 세컨더리 인덱스 100만 행 × 28바이트 차이 = 28MB 추가 공간
-- 인덱스 3개면 84MB, 1000만 행이면 840MB!

-- 페이지 분할(Page Split) 과정
-- [1, 2, 3, 4, 5] ← 페이지 꽉 참
-- INSERT id=2.5 (UUID 등으로 중간 삽입 발생)
-- → [1, 2, 2.5] [3, 4, 5] ← 페이지가 둘로 분할됨
-- → 추가 I/O + 공간 낭비 (각 페이지가 반만 차있음)
-- → fill factor 저하

-- AUTO_INCREMENT는 항상 끝에 추가하므로 분할 없음
-- [1, 2, 3, 4, 5] → [1, 2, 3, 4, 5] [6] ← 새 페이지 할당만

복합 인덱스와 정렬 순서

-- 복합 인덱스는 왼쪽부터 순서대로 정렬
INDEX idx_compound (status, created_at, user_id)

-- B+Tree 리프 노드 정렬 순서:
-- [active,  2024-01-01, 1]
-- [active,  2024-01-01, 5]
-- [active,  2024-01-02, 2]
-- [active,  2024-03-15, 8]
-- [pending, 2024-01-01, 3]
-- [pending, 2024-02-10, 4]
-- → status로 먼저 정렬, 같으면 created_at, 같으면 user_id

-- Leftmost Prefix 규칙
-- 복합 인덱스의 왼쪽부터 연속된 컬럼만 인덱스 사용 가능

-- ✅ 인덱스 사용 가능
WHERE status = 'active'                              -- (status)
WHERE status = 'active' AND created_at > '2024-01-01' -- (status, created_at)
WHERE status = 'active' AND created_at = '2024-01-01' AND user_id = 5
                                                      -- (status, created_at, user_id)

-- ❌ 인덱스 사용 불가 (중간 컬럼 건너뜀)
WHERE status = 'active' AND user_id = 5              -- created_at 건너뜀 → status만 사용
WHERE created_at > '2024-01-01'                       -- 첫 번째 컬럼 없음
WHERE user_id = 5                                     -- 첫 번째 컬럼 없음

-- 범위 조건 이후는 인덱스 무효화
WHERE status = 'active' AND created_at > '2024-01-01' AND user_id = 5
-- → status(=), created_at(>) 까지만 인덱스, user_id는 필터링만

인덱스 스캔 방식

스캔 방식	동작	EXPLAIN type
const	PK/유니크 인덱스로 1행 검색	const
ref	비유니크 인덱스 등가 검색	ref
range	인덱스 범위 스캔 (>, <, BETWEEN, IN)	range
index	인덱스 풀 스캔 (리프 전체 순회)	index
ALL	클러스터드 인덱스 풀 스캔 (테이블 풀 스캔)	ALL

-- Covering Index: 세컨더리 인덱스만으로 쿼리 완료
-- → 클러스터드 인덱스 룩업 불필요 = 성능 극대화
INDEX idx_email_name (email, name)

SELECT name FROM users WHERE email = 'a@mail.com';
-- EXPLAIN: Using index (Extra 컬럼)
-- → idx_email_name 리프에 email + name + PK 모두 있음
-- → 클러스터드 인덱스 접근 불필요!

-- Index Condition Pushdown (ICP, MySQL 5.6+)
INDEX idx_name_age (name, age)

SELECT * FROM users WHERE name LIKE 'A%' AND age > 25;
-- ICP 없이: name LIKE 'A%' 범위 스캔 → 모든 행을 서버 레이어에서 age > 25 필터
-- ICP 있으면: 스토리지 엔진에서 name + age 조건 모두 평가
-- EXPLAIN: Using index condition

인덱스 설계 안티패턴

-- ❌ 1. 함수 사용 → 인덱스 무효화
SELECT * FROM users WHERE YEAR(created_at) = 2024;
-- → created_at 인덱스 사용 불가!
-- ✅ 범위 조건으로 변환
SELECT * FROM users WHERE created_at >= '2024-01-01' AND created_at < '2025-01-01';

-- ❌ 2. 암묵적 형변환
SELECT * FROM users WHERE phone = 01012345678;  -- phone은 VARCHAR
-- → 문자열 컬럼에 숫자 비교 → 인덱스 무효화
-- ✅ 타입 일치
SELECT * FROM users WHERE phone = '01012345678';

-- ❌ 3. 선택도(cardinality) 낮은 컬럼 단독 인덱스
INDEX idx_gender (gender)  -- M/F 2가지 → 선택도 50%
-- → 테이블의 50%를 읽음 = 풀 스캔이 나을 수 있음

-- ❌ 4. 과도한 인덱스
-- INSERT/UPDATE/DELETE 시 모든 인덱스 갱신 필요
-- 인덱스 5개인 테이블에 INSERT = B+Tree 5개에 삽입
-- → 쓰기 성능 저하 + 디스크 공간 낭비

-- ✅ 인덱스 사용량 확인 후 미사용 인덱스 제거
SELECT * FROM sys.schema_unused_indexes
WHERE object_schema = 'mydb';

MySQL InnoDB Lock 구조 심화에서 인덱스와 Lock의 관계도 확인하세요.

정리

InnoDB의 B+Tree 인덱스는 모든 쿼리 성능의 기반입니다. 클러스터드 인덱스(PK)는 테이블 자체이고, 세컨더리 인덱스는 PK를 참조합니다. PK 크기가 모든 세컨더리 인덱스에 복제되므로 PK 설계가 전체 성능을 좌우합니다. 복합 인덱스의 Leftmost Prefix 규칙, Covering Index로 룩업 제거, 함수/형변환에 의한 인덱스 무효화 방지가 핵심 설계 원칙입니다.