인덱스는 왜 빠른가 — B+Tree부터 커버링 인덱스까지 (2편)

들어가며

"인덱스 걸면 빨라진다"는 모두가 압니다. 하지만 왜 빠른지, 어떤 구조로 되어 있어서 O(log N)에 검색이 가능한지, 모든 인덱스가 같은 방식으로 동작하는지 설명하라고 하면 쉽지 않습니다.

1편에서 InnoDB가 데이터를 16KB 페이지 단위로 저장한다는 것을 살펴봤습니다. 인덱스도 결국 페이지의 조합입니다. 이 편에서는 인덱스가 페이지 위에서 어떤 구조로 동작하는지, 그리고 그 구조가 쿼리 성능에 어떤 영향을 미치는지 추적합니다.

왜 B+Tree인가

이진 탐색 트리의 한계

정렬된 데이터에서 빠르게 찾으려면 이진 탐색이 떠오릅니다. 이진 탐색 트리(BST)는 O(log₂ N)입니다. 100만 건이면 약 20번의 비교로 찾을 수 있습니다.

하지만 BST는 디스크 기반 데이터베이스에 적합하지 않습니다. 노드 하나에 키 하나만 저장하므로, 트리 높이가 높아집니다. 트리 높이 = 디스크 I/O 횟수이므로, 높이를 줄이는 것이 핵심입니다.

B-Tree: 노드 하나에 여러 키

B-Tree는 한 노드에 여러 개의 키를 저장합니다. InnoDB 페이지(16KB)에 수백 개의 키를 담을 수 있으므로, 트리 높이가 3-4 수준으로 낮아집니다.

• 100만 건 데이터, 분기 계수(fanout) 500이면: log₅₀₀(1,000,000) ≈ 2.2 → 3단계
• 이진 트리였다면: log₂(1,000,000) ≈ 20 → 20단계

디스크 I/O가 20번에서 3번으로 줄어듭니다. 이것이 B-Tree의 핵심 이점입니다.

B+Tree: B-Tree의 변형

InnoDB가 사용하는 것은 B-Tree가 아니라 B+Tree입니다. B-Tree와의 핵심 차이는 다음과 같습니다:

특성	B-Tree	B+Tree
데이터 위치	모든 노드에 저장	리프 노드에만 저장
내부 노드 역할	키 + 데이터 + 포인터	키 + 포인터만 (가이드 역할)
리프 노드 연결	없음	양방향 링크드 리스트
범위 검색	트리 재탐색 필요	리프에서 순차 스캔

B+Tree의 장점은 두 가지입니다:

1. 내부 노드에 더 많은 키를 저장: 데이터가 없으므로 같은 16KB 페이지에 더 많은 키가 들어갑니다 → 분기 계수 증가 → 높이 감소
2. 범위 검색이 효율적: WHERE age BETWEEN 20 AND 30 같은 범위 쿼리에서, 리프 노드의 링크를 따라 순차 스캔하면 됩니다

B+Tree의 실제 높이

실제로 계산해보겠습니다. PK가 BIGINT(8바이트), 포인터가 6바이트라면:

• 내부 노드 한 페이지: 16KB / (8 + 6) ≈ 1170개 키
• 높이 2: 1170² ≈ 137만 건 커버
• 높이 3: 1170³ ≈ 16억 건 커버

즉, 수억 건의 데이터도 3-4번의 페이지 읽기로 특정 행을 찾을 수 있습니다. 그리고 루트와 상위 내부 노드는 대부분 Buffer Pool에 상주하므로, 실제 디스크 I/O는 1-2번입니다.

클러스터드 인덱스: 데이터 자체가 인덱스

InnoDB에서 가장 중요한 개념입니다. 클러스터드 인덱스는 별도의 인덱스 구조가 아니라, 데이터 자체가 PK 순서로 B+Tree에 저장된 것입니다.

클러스터드 인덱스의 선택 기준

1. 명시적 PRIMARY KEY가 있으면 → 그것이 클러스터드 인덱스
2. PK가 없으면 → 첫 번째 NOT NULL UNIQUE 인덱스
3. 그것도 없으면 → InnoDB가 내부적으로 6바이트 DB_ROW_ID를 생성

그래서 항상 명시적 PK를 정의하는 것이 좋습니다. 내부 ROW_ID는 쿼리에서 사용할 수 없고, 의도치 않은 동작의 원인이 될 수 있습니다.

클러스터드 인덱스의 구조

       [내부 노드: PK 키 + 자식 포인터]
      /              |              \
[리프: PK=1,행데이터] [리프: PK=5,행데이터] [리프: PK=9,행데이터]
  ↔ 양방향 링크 ↔        ↔ 양방향 링크 ↔

리프 노드에 행의 모든 컬럼 데이터가 저장됩니다. SELECT * FROM users WHERE id = 5는 B+Tree를 타고 리프에 도착하면 바로 전체 행을 얻습니다. 추가 I/O가 필요 없습니다.

PK 설계가 중요한 이유

클러스터드 인덱스 = 데이터의 물리적 정렬 순서이므로, 다음을 고려해야 합니다:

• AUTO_INCREMENT PK: 새 행이 항상 끝에 추가됨 → 페이지 분할이 거의 없음 → 쓰기 성능 좋음
• UUID PK: 랜덤한 값이 중간에 삽입됨 → 빈번한 페이지 분할 → 쓰기 성능 저하, 공간 낭비
• 복합 PK: 첫 번째 컬럼으로 정렬 → 범위 검색 패턴에 따라 설계

세컨더리 인덱스: PK를 가리키는 인덱스

PK 외의 인덱스를 세컨더리(보조) 인덱스라고 합니다. CREATE INDEX idx_name ON users(name)을 하면 별도의 B+Tree가 생성됩니다.

세컨더리 인덱스의 구조

       [내부 노드: name 키 + 자식 포인터]
      /              |              \
[리프: name='김',PK=3] [리프: name='박',PK=1] [리프: name='이',PK=5]

핵심: 세컨더리 인덱스의 리프 노드에는 행 데이터가 아니라 PK 값이 저장됩니다.

왜 행의 물리적 주소가 아닌 PK를 저장하는가

MyISAM은 행의 물리적 위치(파일 오프셋)를 저장했습니다. InnoDB가 PK를 저장하는 이유는 다음과 같습니다:

• 클러스터드 인덱스에서 행의 물리적 위치는 페이지 분할 때마다 바뀔 수 있습니다
• 물리적 주소를 저장하면, 페이지 분할 시 모든 세컨더리 인덱스를 갱신해야 합니다
• PK를 저장하면, 페이지 분할이 일어나도 세컨더리 인덱스는 수정할 필요가 없습니다

트레이드오프: PK 크기가 커지면 모든 세컨더리 인덱스도 커집니다. PK는 가능한 작게 유지해야 하는 이유가 여기에 있습니다.

세컨더리 인덱스 조회 과정: 두 번의 B+Tree 탐색

SELECT * FROM users WHERE name = '홍길동'을 실행하면 다음과 같이 동작합니다:

1. 세컨더리 인덱스 B+Tree 탐색: name = '홍길동' → PK = 42를 얻음
2. 클러스터드 인덱스 B+Tree 탐색: PK = 42 → 행 데이터 전체를 얻음

이 두 번째 단계를 북마크 룩업(Bookmark Lookup) 또는 랜덤 I/O라고 합니다. 세컨더리 인덱스를 통한 조회가 PK 조회보다 느린 이유입니다.

대량의 행을 세컨더리 인덱스로 조회하면, 행마다 클러스터드 인덱스를 다시 타야 해서 성능이 급감합니다. 옵티마이저가 "차라리 풀 스캔이 낫다"고 판단하는 경우도 이 때문입니다.

커버링 인덱스: 두 번째 탐색을 생략

쿼리에 필요한 모든 컬럼이 인덱스에 포함되어 있으면, 클러스터드 인덱스를 탐색할 필요가 없습니다. 이것을 커버링 인덱스라고 합니다.

-- 인덱스: CREATE INDEX idx_name ON users(name)

SELECT name FROM users WHERE name = '홍길동';
-- 세컨더리 인덱스의 리프에 name이 있으므로, 클러스터드 인덱스 탐색 불필요
-- EXPLAIN에서 Extra: "Using index"로 확인

SELECT name, email FROM users WHERE name = '홍길동';
-- email이 인덱스에 없으므로, 클러스터드 인덱스를 다시 타야 함

커버링 인덱스는 세컨더리 인덱스에 PK도 자동 포함되므로, PK 컬럼은 별도로 추가할 필요 없습니다:

-- 인덱스: CREATE INDEX idx_name ON users(name)

SELECT id, name FROM users WHERE name = '홍길동';
-- id(PK)는 세컨더리 인덱스에 이미 포함 → 커버링 인덱스 성립

복합 인덱스와 최좌선 규칙

여러 컬럼을 묶은 인덱스를 복합 인덱스(Composite Index)라고 합니다.

CREATE INDEX idx_age_name ON users(age, name);

B+Tree는 왼쪽 컬럼부터 순서대로 정렬됩니다. 이것이 최좌선(Leftmost Prefix) 규칙의 근거입니다:

-- 인덱스: (age, name)

✅ WHERE age = 25                     -- age로 검색 가능
✅ WHERE age = 25 AND name = '홍길동'  -- age → name 순서로 매칭
✅ WHERE age > 20 AND age < 30         -- age 범위 검색 가능
❌ WHERE name = '홍길동'               -- age 없이 name만으로는 인덱스 사용 불가
⚠️ WHERE age > 20 AND name = '홍길동'  -- age는 범위 스캔, name은 인덱스 필터링만

왜 순서가 중요한가

전화번호부를 생각하면 쉽습니다. 전화번호부는 "성 → 이름" 순으로 정렬되어 있습니다.

• "김" 씨를 찾는 건 쉽습니다 (첫 번째 컬럼)
• "김영희"를 찾는 것도 쉽습니다 (순서대로)
• 하지만 "영희"만으로 찾는 건 불가능합니다 (두 번째 컬럼만으로는 정렬이 안 되어 있음)

복합 인덱스 설계 원칙

1. 동등 조건(=) 컬럼을 앞에, 범위 조건(>, <, BETWEEN) 컬럼을 뒤에
2. 카디널리티가 높은 컬럼(값의 종류가 많은)을 앞에 배치하면 필터링 효율이 높다
3. SELECT 절의 컬럼도 고려: 커버링 인덱스를 만들 수 있다면 성능 이점이 크다
4. 정렬(ORDER BY) 방향도 고려: ORDER BY created_at DESC가 자주 쓰이면 인덱스에 포함

인덱스가 안 타는 경우들

인덱스를 만들었는데도 사용되지 않는 대표적인 경우입니다:

1. 함수 적용

-- ❌ 인덱스 안 탐
SELECT * FROM users WHERE YEAR(created_at) = 2024;

-- ✅ 범위 조건으로 변환
SELECT * FROM users WHERE created_at >= '2024-01-01' AND created_at < '2025-01-01';

인덱스는 컬럼 값으로 정렬되어 있지, 함수 적용 결과로 정렬되어 있지 않습니다. MySQL 8.0의 함수 기반 인덱스(Expression Index)로 해결할 수 있지만, 쿼리를 바꾸는 게 일반적입니다.

2. 암묵적 형변환

-- phone이 VARCHAR인데 숫자로 비교
-- ❌ 모든 행을 숫자로 변환해서 비교 → 풀 스캔
SELECT * FROM users WHERE phone = 01012345678;

-- ✅ 문자열로 비교
SELECT * FROM users WHERE phone = '01012345678';

3. LIKE 앞쪽 와일드카드

-- ❌ 앞에 %가 있으면 정렬 순서를 활용할 수 없음
SELECT * FROM users WHERE name LIKE '%길동';

-- ✅ 뒤에만 %
SELECT * FROM users WHERE name LIKE '홍%';

4. OR 조건

-- ❌ 각 조건에 인덱스가 있어도, OR로 묶이면 비효율적
SELECT * FROM users WHERE age = 25 OR name = '홍길동';

-- ✅ UNION으로 분리
SELECT * FROM users WHERE age = 25
UNION
SELECT * FROM users WHERE name = '홍길동';

인덱스의 비용: 쓰기 성능

인덱스는 읽기를 빠르게 하지만, 쓰기를 느리게 합니다:

• INSERT: 데이터 + 모든 인덱스의 B+Tree에 키를 삽입해야 합니다
• UPDATE: 변경된 컬럼이 포함된 인덱스를 갱신해야 합니다
• DELETE: 인덱스에서도 삭제 마킹

인덱스가 5개인 테이블에 INSERT 하면, 사실상 6번의 B+Tree 삽입(데이터 1 + 인덱스 5)이 일어납니다. Change Buffer가 일부 완화하지만, 근본적으로 인덱스는 필요한 만큼만 만들어야 합니다.

정리

개념	핵심
B+Tree	내부 노드는 가이드, 데이터는 리프에만, 리프는 링크드 리스트
클러스터드 인덱스	PK 순서로 데이터 자체가 저장됨. 테이블당 1개.
세컨더리 인덱스	리프에 PK를 저장. 조회 시 클러스터드 인덱스를 다시 탐색.
커버링 인덱스	인덱스만으로 쿼리 완료. "Using index"
복합 인덱스	최좌선 규칙. 동등 조건 앞, 범위 조건 뒤.
인덱스 안 타는 경우	함수 적용, 형변환, 앞쪽 %, OR 조건

다음 편 예고

3편에서는 트랜잭션과 MVCC를 다룹니다. 여러 트랜잭션이 동시에 같은 데이터를 읽고 쓸 때 어떤 일이 일어나는지, InnoDB가 Undo Log와 Read View로 어떻게 일관된 읽기를 보장하는지 추적합니다.