1
2
3
4
5
6
7
8
9
10
[Full Table Scan]

데이터 페이지 1: [이영희, 박민수, 정수진, ...]  → 전부 읽음
데이터 페이지 2: [최동현, 김철수, 한지민, ...]  → 전부 읽음 (김철수 발견!)
데이터 페이지 3: [강동원, 송혜교, 김철수, ...]  → 전부 읽음 (또 김철수!)
...
데이터 페이지 N: [...]                          → 마지막까지 전부 읽음

→ N개의 데이터 페이지를 모두 읽어야 한다
→ 1000만 행이면 1000만 행을 모두 스캔

1
2
3
4
5
6
7
8
9
10
11
12
[인덱스 검색]

B+Tree 인덱스:
  루트 노드: [김, 박, 이]
                │
  중간 노드: [... 김대현, 김수진, 김철수 ...]
                              │
  리프 노드: [김철수 → PK=5], [김철수 → PK=127]

→ 루트 → 중간 → 리프: 3번의 노드 접근으로 '김철수'의 위치를 찾음
→ PK 5, 127로 실제 데이터 행을 조회
→ 전체 1000만 행 중 필요한 행만 정확히 접근

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[Hash Index의 한계]

Hash: key → hash(key) → bucket → 값

장점:
  - 등호(=) 검색: O(1) — 매우 빠름

단점:
  - 범위 검색 불가: WHERE age > 20 → 해시로는 "20보다 큰 값"을 찾을 수 없다
  - 정렬 불가: ORDER BY age → 해시는 정렬 순서를 보장하지 않는다
  - 부등호 불가: WHERE age >= 20 AND age <= 30
  - LIKE 앞부분 일치 불가: WHERE name LIKE '김%'
  - 부분 키 검색 불가: (a, b) 복합 인덱스에서 a만으로 검색 불가

→ 실무 쿼리의 대부분은 범위 검색, 정렬, LIKE가 포함되어 있다
→ Hash Index로는 이런 쿼리를 처리할 수 없다

1
2
3
4
5
6
7
8
9
10
11
[B+Tree Index의 강점]

B+Tree: key → 정렬된 트리 탐색 → 값

- 등호(=) 검색: O(log N) — 충분히 빠름
- 범위 검색: WHERE age > 20 → 20을 찾은 후 리프 노드를 순차 탐색
- 정렬: ORDER BY age → 이미 정렬되어 있으므로 추가 정렬 불필요
- LIKE 앞부분 일치: WHERE name LIKE '김%' → '김'을 찾은 후 순차 탐색
- 복합 인덱스: (a, b)에서 a만으로 검색 가능 (최좌선 접두사 규칙)

→ SQL에서 필요한 거의 모든 검색 패턴을 지원한다

1
2
3
4
5
6
7
8
9
10
11
12
[B-Tree (차수 3: 각 노드에 최대 2개의 키, 3개의 자식)]

          [30, 60]                     ← 루트 노드
         /    |    \
   [10, 20] [40, 50] [70, 80]         ← 리프 노드
    ↓ ↓ ↓    ↓ ↓ ↓    ↓ ↓ ↓
   데이터   데이터   데이터             ← B-Tree는 모든 노드에 데이터

키 35 검색:
1. 루트 [30, 60] → 30 < 35 < 60 → 가운데 자식으로
2. [40, 50] → 35 < 40 → 왼쪽 자식으로
3. 리프에서 35를 찾음

1
2
3
4
5
6
7
8
9
10
[B-Tree]
          [30|DATA, 60|DATA]           ← 내부 노드에도 데이터가 있다
         /         |         \
   [10|DATA, 20|DATA]  [40|DATA]  [70|DATA, 80|DATA]

[B+Tree]
          [30,      60]                ← 내부 노드에는 키만 있다
         /      |      \              ← 데이터가 없으므로 더 많은 키를 넣을 수 있다!
   [10|D, 20|D, 30|D] → [40|D, 50|D, 60|D] → [70|D, 80|D]
   ↑ 리프 노드에만 데이터    ↑ 링크드 리스트로 연결

1
2
3
4
5
6
7
8
9
10
11
[B+Tree의 리프 노드 연결]

리프1 [10, 20, 30] → 리프2 [40, 50, 60] → 리프3 [70, 80, 90]

범위 검색: WHERE age BETWEEN 25 AND 65
1. 트리 탐색으로 25 이상인 첫 번째 리프를 찾는다 → 리프1의 30
2. 리프1에서 30을 가져온다
3. 링크를 따라 리프2로 이동 → 40, 50, 60을 가져온다
4. 링크를 따라 리프3으로 이동 → 65 이하이므로 탐색 종료

→ 트리를 다시 올라갈 필요 없이 리프 노드만 순차적으로 읽으면 된다!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
[B+Tree 높이별 저장 가능 행 수 계산]

전제:
  - 페이지 크기: 16KB = 16,384 bytes
  - 내부 노드의 키 크기: BIGINT(8 bytes) + 자식 포인터(6 bytes) = 14 bytes
  - 내부 노드 하나에 들어가는 키 수: 16,384 / 14 ≈ 1,170개
  - 리프 노드의 행 크기: 평균 100 bytes (컬럼에 따라 다름)
  - 리프 노드 하나에 들어가는 행 수: 16,384 / 100 ≈ 160행

높이 1 (루트만):
  행 수: 160
  디스크 I/O: 1회

높이 2 (루트 + 리프):
  행 수: 1,170 × 160 = 187,200 (약 18만)
  디스크 I/O: 2회

높이 3 (루트 + 중간 + 리프):
  행 수: 1,170 × 1,170 × 160 = 219,024,000 (약 2.2억!)
  디스크 I/O: 3회

높이 4:
  행 수: 1,170^3 × 160 ≈ 2,562억
  디스크 I/O: 4회

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
[InnoDB 클러스터드 인덱스 구조]

        [내부 노드: PK 값들]
       /        |        \
  [PK 1~100] [PK 101~200] [PK 201~300]
      ↓            ↓            ↓
  리프 노드     리프 노드     리프 노드
  ┌──────────┐ ┌──────────┐ ┌──────────┐
  │PK=1      │ │PK=101    │ │PK=201    │
  │name=김철수│ │name=박민수│ │name=최동현│
  │age=25    │ │age=30    │ │age=22    │
  │team_id=1 │ │team_id=2 │ │team_id=3 │
  ├──────────┤ ├──────────┤ ├──────────┤
  │PK=2      │ │PK=102    │ │PK=202    │
  │name=이영희│ │...       │ │...       │
  │age=28    │ │          │ │          │
  │team_id=1 │ │          │ │          │
  └──────────┘ └──────────┘ └──────────┘
  ↑ 리프 노드 = 실제 데이터 행!

1
2
3
1. PRIMARY KEY가 있으면 → PK가 클러스터드 인덱스
2. PK가 없고 UNIQUE NOT NULL 컬럼이 있으면 → 그 컬럼이 클러스터드 인덱스
3. 둘 다 없으면 → InnoDB가 내부적으로 GEN_CLUST_INDEX(6바이트 Row ID)를 생성

1
2
리프: [1, 2, 3] → [4, 5, 6] → [7, 8, 9] → [10, 11, NEW]
                                               ↑ 항상 끝에 추가

1
2
3
리프: [10ab..., 22fc..., 35da...] → [44bc..., NEW(3f2e...), 55ef...]
                                        ↑ 중간에 삽입!
                                        → 페이지 분할 발생!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[페이지 분할 과정]

원래 페이지: [A, B, C, D, E] (가득 참)
새 데이터 C' (C와 D 사이에 삽입해야 함)

1. 새 페이지를 할당한다
2. 원래 페이지의 절반을 새 페이지로 이동
   원래 페이지: [A, B, C']
   새 페이지:   [D, E]
3. 상위 노드의 포인터를 갱신한다

비용:
  - 새 페이지 할당: 디스크 I/O
  - 데이터 이동: 디스크 I/O
  - 상위 노드 갱신: 디스크 I/O
  - 페이지 사용률 50%로 하락 → 공간 낭비

1
2
3
4
5
6
7
8
9
10
11
12
13
[세컨더리 인덱스: idx_member_name]

        [내부 노드: name 값들]
       /         |          \
  [가~나]     [다~마]      [바~하]
      ↓           ↓           ↓
  리프 노드    리프 노드    리프 노드
  ┌────────┐  ┌────────┐  ┌────────┐
  │김철수→PK5│  │박민수→PK3│  │이영희→PK2│
  │김현수→PK9│  │박지성→PK7│  │정수진→PK4│
  └────────┘  └────────┘  └────────┘
  ↑ 리프 노드 = (인덱스 키, PK 값)
    실제 데이터는 없다!

1
2
3
4
5
6
7
8
9
10
11
12
13
[더블 룩업 과정]

1단계 — 세컨더리 인덱스(idx_member_name) 탐색:
  B+Tree에서 '김철수'를 찾는다
  → 리프 노드에서 PK = 5를 얻는다

2단계 — 클러스터드 인덱스(PK) 탐색:
  PK = 5로 클러스터드 인덱스 B+Tree를 탐색한다
  → 리프 노드에서 실제 데이터 행을 읽는다
  → {id: 5, name: "김철수", age: 25, team_id: 1}

총 디스크 I/O: (세컨더리 인덱스 높이) + (클러스터드 인덱스 높이)
             = 3 + 3 = 6회 (최악의 경우)

1
2
3
4
5
6
7
8
9
10
11
12
13
[물리적 주소를 저장하면 발생하는 문제]

클러스터드 인덱스에서 페이지 분할이 일어나면
→ 데이터 행의 물리적 위치가 바뀐다
→ 모든 세컨더리 인덱스의 포인터를 갱신해야 한다!
→ 세컨더리 인덱스가 10개면 10개 전부 갱신

[PK 값을 저장하면]

클러스터드 인덱스에서 페이지 분할이 일어나도
→ PK 값은 바뀌지 않는다
→ 세컨더리 인덱스를 갱신할 필요가 없다!
→ 대신 검색 시 PK로 한 번 더 탐색해야 한다 (더블 룩업)

1
2
3
4
5
6
7
8
9
10
11
12
[복합 인덱스 (team_id, age)의 정렬 상태]

team_id | age | PK
--------|-----|----
   1    | 20  |  7
   1    | 25  |  1    ← team_id=1 내에서 age 순으로 정렬
   1    | 28  |  2
   2    | 22  |  5
   2    | 30  |  3    ← team_id=2 내에서 age 순으로 정렬
   2    | 35  |  8
   3    | 24  |  4
   3    | 27  |  6    ← team_id=3 내에서 age 순으로 정렬

1
2
3
4
5
6
7
8
✅ WHERE A = 1                          → A만 사용 (인덱스 사용 O)
✅ WHERE A = 1 AND B = 2                → A+B 사용 (인덱스 사용 O)
✅ WHERE A = 1 AND B = 2 AND C = 3      → A+B+C 모두 사용 (인덱스 사용 O)
✅ WHERE A = 1 AND C = 3                → A만 사용 (B를 건너뛰었으므로 C는 인덱스 활용 안 됨)

❌ WHERE B = 2                          → 인덱스 사용 불가
❌ WHERE C = 3                          → 인덱스 사용 불가
❌ WHERE B = 2 AND C = 3                → 인덱스 사용 불가

1
2
3
4
5
6
7
8
9
10
11
인덱스 (team_id, age):

team_id=1에서 age가 정렬되어 있다 (20, 25, 28)
team_id=2에서 age가 정렬되어 있다 (22, 30, 35)
team_id=3에서 age가 정렬되어 있다 (24, 27)

전체에서 age만 보면? (20, 25, 28, 22, 30, 35, 24, 27) → 정렬 안 되어 있음!

따라서:
WHERE team_id = 1 AND age = 25  → team_id=1 그룹 내에서 age=25 탐색 ✅
WHERE age = 25                  → 전체에서 age=25를 찾으려면 Full Scan ❌

1
2
3
4
5
6
7
8
9
최적 인덱스: (status, created_at, total_amount)

이유:
1. status = 'COMPLETED' → 등호 조건, 인덱스의 첫 번째 컬럼으로 정확히 매칭
2. created_at >= '2026-01-01' → 범위 조건, 두 번째 컬럼에서 범위 탐색
3. total_amount DESC → 정렬, 세 번째 컬럼이 이미 정렬되어 있으면 filesort 불필요

잘못된 순서: (created_at, status, total_amount)
→ created_at이 범위 조건이므로, 그 뒤의 status는 인덱스를 활용할 수 없다!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[범위 조건이 인덱스 활용을 끊는 이유]

인덱스 (A, B): A로 정렬 → A가 같으면 B로 정렬

A=1, B 정렬: (1,10), (1,20), (1,30)
A=2, B 정렬: (2,15), (2,25)
A=3, B 정렬: (3,5), (3,35)

WHERE A = 1 AND B > 15:
→ A=1인 구간에서 B > 15 탐색 → (1,20), (1,30) ✅

WHERE A > 1 AND B > 15:
→ A > 1인 구간: (2,15), (2,25), (3,5), (3,35)
→ 이 구간에서 B는 정렬되어 있지 않다! (15, 25, 5, 35)
→ B > 15 조건에 인덱스를 활용할 수 없다!

1
2
3
4
gender: M, F → 카디널리티 2 (낮음)
status: PENDING, COMPLETED, CANCELLED → 카디널리티 3 (낮음)
email: 고유값 수백만 → 카디널리티 높음
created_at: 고유값 수백만 → 카디널리티 높음

1
2
3
4
5
6
7
8
[커버링 인덱스 동작]

일반 인덱스 검색 (더블 룩업):
  세컨더리 인덱스 탐색 → PK 획득 → 클러스터드 인덱스 탐색 → 데이터 반환

커버링 인덱스 검색:
  세컨더리 인덱스 탐색 → 인덱스 리프 노드에서 바로 데이터 반환!
  ↑ 클러스터드 인덱스 접근 불필요! (더블 룩업 제거)

1
2
3
4
5
6
7
system   → 테이블에 행이 1개 (시스템 테이블)
const    → PK/UNIQUE로 1행 조회. WHERE id = 1
eq_ref   → JOIN에서 PK/UNIQUE로 1행씩 매칭
ref      → 인덱스로 여러 행 조회. WHERE status = 'ACTIVE'
range    → 인덱스 범위 검색. WHERE age BETWEEN 20 AND 30
index    → 인덱스 Full Scan (테이블 Full Scan보다는 나음)
ALL      → Full Table Scan (최악)

1
2
3
4
5
Using index            → 커버링 인덱스! 테이블 접근 없이 인덱스만으로 처리 ✅
Using where            → WHERE 조건을 스토리지 엔진이 아닌 MySQL 서버에서 필터링
Using index condition  → ICP(Index Condition Pushdown) 적용 ✅
Using temporary        → 임시 테이블 사용 ⚠️ (GROUP BY, DISTINCT 등)
Using filesort         → 추가 정렬 필요 ⚠️ (ORDER BY를 인덱스로 처리 못 함)

1
2
3
4
1. 인덱스에서 name LIKE '김%'인 모든 행의 PK를 가져온다 (100행)
2. 100행 각각에 대해 클러스터드 인덱스에서 전체 데이터를 읽는다
3. MySQL 서버에서 age > 25 조건을 필터링한다 (30행만 남음)
→ 불필요하게 70행의 클러스터드 인덱스 접근이 발생!

1
2
3
4
5
1. 인덱스에서 name LIKE '김%' AND age > 25인 행의 PK만 가져온다
   (인덱스에 age가 포함되어 있으므로 인덱스 레벨에서 필터링 가능!)
   → 30행
2. 30행에 대해서만 클러스터드 인덱스 접근
→ 70행의 불필요한 클러스터드 인덱스 접근을 제거!

1
2
3
→ Nested loop inner join  (cost=4.5 rows=3) (actual time=0.05..0.08 rows=3 loops=1)
  → Index range scan on m using idx_age  (cost=2.5 rows=3) (actual time=0.03..0.04 rows=3 loops=1)
  → Single-row index lookup on t using PRIMARY (id=m.team_id)  (cost=0.5 rows=1) (actual time=0.01..0.01 rows=1 loops=3)

1
2
3
쿼리 1: (status, team_id) 또는 (team_id, status)
쿼리 2: (member_id, status, created_at) — 등호+등호+정렬
쿼리 3: (category_id, price) — 등호+범위

1
2
3
4
5
6
7
8
9
[인덱스가 없는 경우]
1. team 테이블에서 name = '개발팀' Full Scan → 1행 찾음 (team_id = 1)
2. member 테이블에서 team_id = 1 Full Scan → 전체 행 스캔!
→ member에 1000만 행이면 1000만 행 스캔

[member.team_id에 인덱스가 있는 경우]
1. team 테이블에서 name = '개발팀' 조회 (team.name에 인덱스 있으면 더 빠름)
2. member 테이블에서 team_id = 1 인덱스 검색 → 해당 행만 정확히 접근!
→ 수십 건만 읽음

1
2
3
4
5
6
7
8
9
테이블당 인덱스 권장 개수: 3~5개

인덱스가 너무 많으면:
- INSERT/UPDATE/DELETE마다 모든 인덱스를 갱신해야 한다
- 인덱스 저장 공간이 커진다
- 옵티마이저가 최적 인덱스를 선택하는 데 시간이 걸린다

인덱스가 너무 적으면:
- 자주 사용되는 쿼리에서 Full Scan이 발생한다

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
[인덱스 설계 단계]

1단계 — 쿼리 수집
✅ 애플리케이션의 주요 쿼리를 수집했는가?
✅ 슬로우 쿼리 로그를 활성화했는가?

2단계 — 인덱스 후보 도출
✅ WHERE 절의 등호/범위 조건 컬럼을 식별했는가?
✅ ORDER BY, GROUP BY 컬럼을 식별했는가?
✅ JOIN 조건의 FK 컬럼에 인덱스가 있는가?

3단계 — 복합 인덱스 설계
✅ 등호 조건 → 범위 조건 → 정렬 컬럼 순서를 지켰는가?
✅ 최좌선 접두사 규칙을 고려하여 다양한 쿼리를 커버하는가?
✅ 커버링 인덱스 가능성을 검토했는가?

4단계 — 검증
✅ EXPLAIN으로 type이 ALL이 아닌지 확인했는가?
✅ Extra에 Using filesort/Using temporary가 없는지 확인했는가?
✅ rows가 합리적인 수치인가?

5단계 — 유지보수
✅ 사용되지 않는 인덱스를 주기적으로 확인하고 제거하는가?
✅ 테이블당 인덱스가 5개를 넘지 않는가?
✅ 인덱스 크기를 모니터링하고 있는가?

[인덱스를 만들지 말아야 하는 경우]
❌ 카디널리티가 극도로 낮은 컬럼 (boolean, gender)
❌ 거의 조회되지 않는 컬럼
❌ 쓰기가 99%, 읽기가 1%인 테이블
❌ 행 수가 매우 적은 테이블 (수백 행 이하 → Full Scan이 더 빠름)