인덱스의 동작 원리 — B-Tree부터 커버링 인덱스까지
100만 건 테이블에서 특정 행 하나를 찾을 때, 인덱스가 있으면 20번 비교로 끝나고 없으면 100만 번 비교해야 한다. 이 차이는 어디서 오는 걸까?
인덱스가 없으면 어떻게 되나
SELECT * FROM users WHERE name = 'sim';
인덱스가 없으면 테이블 전체를 처음부터 끝까지 훑습니다. Full Table Scan. 100만 건이면 100만 건을 다 봅니다. O(n).
인덱스가 있으면? O(log n). 100만 건에서도 약 20번의 비교로 찾습니다.
B-Tree
대부분의 RDBMS(MySQL, PostgreSQL, Oracle)가 인덱스에 사용하는 자료구조입니다.
왜 Binary Tree가 아니라 B-Tree인가
자료구조 글에서 한 번 언급했는데, 핵심은 ** 디스크 I/O**입니다.
DB 데이터는 디스크에 있고, 디스크는 한 번에 ** 페이지(4KB~16KB)** 단위로 읽습니다. Binary Tree는 노드당 키가 1개라서 한 번 디스크를 읽어도 하나의 비교만 할 수 있습니다. 트리 높이가 20이면 디스크를 20번 읽어야 합니다.
B-Tree는 노드당 키가 수백수천 개입니다. 한 번 디스크를 읽으면 수백 번의 비교를 할 수 있어서, ** 트리 높이가 34로 충분합니다 **.
Binary Tree (높이 20) B-Tree (높이 3~4)
디스크 I/O: 20번 디스크 I/O: 3~4번
B-Tree의 구조
차수(order)가 m인 B-Tree:
- 각 노드는 최대 m-1개의 키 를 가짐
- 각 노드는 최대 m개의 자식 을 가짐
- 루트를 제외한 모든 노드는 최소 ⌈m/2⌉개의 자식을 가짐
- 모든 리프 노드의 깊이가 같음 (균형 유지)
차수 3인 B-Tree:
[10, 20]
/ | \
[5, 7] [13, 15] [25, 30]
B+Tree
MySQL InnoDB가 실제로 사용하는 건 B+Tree입니다. B-Tree의 변형입니다.
B-Tree vs B+Tree
| B-Tree | B+Tree | |
|---|---|---|
| 데이터 위치 | 모든 노드 | ** 리프 노드에만** |
| 리프 연결 | 없음 | 리프끼리 ** 연결 리스트 **로 연결 |
| 범위 검색 | 비효율적 | ** 효율적** (리프를 순회) |
B+Tree:
[10 | 20] ← 내부 노드: 키만 저장
/ | \
[5, 7] → [10, 13] → [20, 25, 30] ← 리프 노드: 키 + 데이터 (연결 리스트)
** 범위 검색 **이 효율적인 이유: WHERE age BETWEEN 20 AND 30은 리프 노드에서 20을 찾고, 연결 리스트를 따라 30까지 순회하면 됩니다. B-Tree는 트리를 다시 탐색해야 합니다.
Clustered vs Non-Clustered Index
Clustered Index (클러스터형 인덱스)
테이블의 ** 물리적 정렬 순서 **와 인덱스 순서가 같습니다. InnoDB에서 Primary Key 가 클러스터형 인덱스입니다.
- 테이블당 1개만 가능
- 리프 노드에 ** 실제 데이터 행(row)**이 저장됨
- PK로 조회하면 바로 데이터를 읽을 수 있어서 매우 빠름
Non-Clustered Index (비클러스터형 인덱스)
리프 노드에 PK 값(포인터) 이 저장됩니다. 인덱스로 PK를 찾고, PK로 다시 클러스터형 인덱스를 타서 실제 데이터를 찾습니다.
Non-Clustered Index의 조회 과정:
1. name 인덱스에서 'sim' 검색 → PK = 123 발견
2. PK(Clustered) 인덱스에서 123 검색 → 실제 row 반환
이 "다시 찾아가는" 과정을 랜덤 I/O 라 하는데, 이게 느립니다. 그래서 커버링 인덱스 가 중요합니다.
커버링 인덱스 (Covering Index)
쿼리에서 필요한 컬럼이 인덱스에 모두 포함 되어 있으면, 실제 데이터 행을 읽을 필요 없이 인덱스만으로 쿼리를 완료할 수 있습니다.
-- name, age를 포함하는 복합 인덱스가 있으면
CREATE INDEX idx_name_age ON users(name, age);
-- 이 쿼리는 인덱스만으로 해결 (커버링 인덱스)
SELECT name, age FROM users WHERE name = 'sim';
-- 이 쿼리는 인덱스로 안 됨 (email이 인덱스에 없음)
SELECT name, email FROM users WHERE name = 'sim';
EXPLAIN에서 Using index가 보이면 커버링 인덱스가 적용된 겁니다.
복합 인덱스에서 순서가 중요한 이유
CREATE INDEX idx_abc ON users(a, b, c);
이 인덱스는 (a) → (a, b) → (a, b, c) 순서로 정렬됩니다. 마치 전화번호부가 성 → 이름 → 전화번호 순으로 정렬된 것과 같습니다.
-- 인덱스를 탈 수 있는 쿼리
WHERE a = 1
WHERE a = 1 AND b = 2
WHERE a = 1 AND b = 2 AND c = 3
-- 인덱스를 못 타는 쿼리
WHERE b = 2 -- a 없이 b만으로는 못 찾음
WHERE b = 2 AND c = 3 -- 첫 번째 컬럼이 없음
이걸 ** 최좌측 접두사 규칙 (Leftmost Prefix Rule)**이라고 합니다. 전화번호부에서 이름만 가지고 찾을 수 없는 것과 같은 원리입니다.
주의할 점
"인덱스를 걸면 INSERT가 느려지는 이유는?"
데이터를 삽입할 때마다 인덱스 트리에도 키를 추가해야 합니다. B+Tree의 노드가 가득 차면 ** 분할(split)**이 발생하고, 이건 디스크 I/O를 유발합니다.
인덱스가 많을수록 INSERT/UPDATE/DELETE가 느려집니다. 그래서 인덱스를 무작정 많이 만들면 안 됩니다.
"인덱스를 타지 않는 경우는?"
- ** 함수나 연산을 적용한 경우 **:
WHERE YEAR(created_at) = 2026→ 인덱스 못 탐 - **LIKE의 앞부분에 와일드카드 **:
WHERE name LIKE '%sim'→ Full Scan - ** 타입 불일치 **: 문자열 컬럼에 숫자를 비교하면 형변환이 발생
- **NOT, !=, <> 조건 **: 옵티마이저가 Full Scan이 더 효율적이라 판단할 수 있음
- ** 데이터 분포가 고르지 않은 경우 **: 전체 행의 대부분을 선택하면 Full Scan이 더 빠름
"Hash 인덱스는 왜 잘 안 쓰나요?"
Hash 인덱스는 동등 비교(=)에서 O(1)로 매우 빠르지만:
- ** 범위 검색 불가 **:
WHERE age > 20같은 쿼리를 처리할 수 없음 - ** 정렬 불가 **: ORDER BY에 활용할 수 없음
- ** 부분 일치 불가 **: 복합 키의 일부만으로 검색 불가
B+Tree는 범위 검색, 정렬, 부분 일치가 모두 가능해서 범용적으로 사용됩니다.
"EXPLAIN 결과를 어떻게 읽나요?"
주요 항목:
- type: ALL(Full Scan) → index → range → ref → const 순으로 좋음
- key: 실제 사용된 인덱스
- rows: 예상 검사 행 수
- Extra:
Using index(커버링),Using filesort(추가 정렬),Using temporary(임시 테이블)
파생되는 개념들
- ** 트랜잭션과 ACID** — 데이터 정합성 보장
- ** 트랜잭션 격리 수준** — READ COMMITTED, REPEATABLE READ 등
- ** 정규화와 반정규화** — 테이블 설계 원칙
- ** 쿼리 최적화** — 실행 계획 분석, 슬로우 쿼리 튜닝
- NoSQL과 CAP 정리 — 관계형 DB가 아닌 선택지