인덱스 — B+Tree, 복합 인덱스, 커버링 인덱스의 동작 원리
데이터베이스에 100만 건이 있는데, 왜 어떤 쿼리는 0.001초에 끝나고 어떤 쿼리는 3초가 걸릴까?
대부분의 경우 답은 인덱스 입니다. 공부하다 보니 "인덱스를 걸면 빠르다"는 건 다들 알지만, **왜 빠른지 **, ** 어떤 구조인지 **, ** 언제 오히려 느려지는지 **를 제대로 설명할 수 있는 사람은 생각보다 적었습니다.
Full Table Scan vs Index Scan
인덱스가 없으면 데이터베이스는 Full Table Scan 을 합니다. 테이블의 모든 행을 처음부터 끝까지 읽는 것이죠.
- 100만 건 테이블에서 1건을 찾으려면 → 최악의 경우 100만 건 전부 확인
- 인덱스가 있으면 → 3~4번의 탐색 으로 끝
이 마법 같은 차이를 만드는 자료구조가 바로 B+Tree입니다.
B+Tree 구조
대부분의 RDBMS(MySQL InnoDB, PostgreSQL, Oracle)가 인덱스에 사용하는 자료구조입니다.
핵심 구조
[30 | 60] ← 내부 노드 (키만 저장)
/ | \
[10|20] [40|50] [70|80] ← 내부 노드
/ | \ / | \ / | \
리프 리프 리프 리프 ← 리프 노드 (키 + 데이터 + 다음 포인터)
←→ ←→ ←→ ←→ ← 리프끼리 링크드 리스트로 연결
B+Tree가 일반 B-Tree와 다른 핵심 포인트:
- **내부 노드 **: 키(key)만 저장, 데이터 없음 → 한 노드에 키를 더 많이 담을 수 있음
- ** 리프 노드 **: 키 + 실제 데이터(또는 포인터) 저장
- ** 리프 노드 연결 : 리프끼리 양방향 링크드 리스트로 연결 → ** 범위 검색(Range Scan)에 유리
왜 3~4번이면 되는가
각 노드는 하나의 ** 디스크 페이지 **(보통 8KB~16KB)에 맞춰 설계됩니다.
- 한 노드에 키가 수백 개 들어감 (예: 500개)
- 1단계: 500개 중 범위 좁힘
- 2단계: 500 × 500 = 250,000개 범위
- 3단계: 500^3 = 1억 2,500만 개 범위
100만 건 정도면 트리 높이가 34면 충분합니다. 각 단계가 디스크 I/O 1회이므로, 디스크를 34번만 읽으면 원하는 데이터를 찾을 수 있습니다.
검색 과정
WHERE id = 42를 찾는다고 가정하면:
- 루트 노드에서 42가 속하는 범위의 자식 포인터를 따라감
- 중간 노드에서 다시 범위를 좁혀 자식 포인터를 따라감
- 리프 노드에 도착 → 42에 해당하는 데이터(또는 데이터 포인터)를 반환
범위 검색(WHERE id BETWEEN 10 AND 50)이면 리프 노드의 링크를 따라가며 순차적으로 읽습니다. B-Tree에서는 이게 불가능해서 매번 루트부터 다시 탐색해야 합니다.
복합 인덱스 (Composite Index)
여러 컬럼을 묶어서 하나의 인덱스로 만드는 것입니다.
-- (name, age, city) 복합 인덱스 생성
CREATE INDEX idx_name_age_city ON users(name, age, city);
선두 컬럼 규칙 (Leftmost Prefix Rule)
복합 인덱스는 ** 왼쪽부터 순서대로** 매칭됩니다. 전화번호부가 "성 → 이름" 순서로 정렬되어 있는 것과 같습니다.
-- 인덱스: (name, age, city)
-- ✅ 인덱스 활용 가능
WHERE name = '김철수' -- name만 사용
WHERE name = '김철수' AND age = 25 -- name + age 사용
WHERE name = '김철수' AND age = 25 AND city = '서울' -- 전부 사용
-- ❌ 인덱스 활용 불가
WHERE age = 25 -- 선두 컬럼(name) 빠짐
WHERE city = '서울' -- 선두 컬럼(name) 빠짐
WHERE age = 25 AND city = '서울' -- 선두 컬럼(name) 빠짐
공부하다 보니 여기서 많이 헷갈렸는데,
WHERE name = '김철수' AND city = '서울'은 name까지만 인덱스를 타고, city는 필터링으로 처리됩니다. 중간 컬럼(age)을 건너뛸 수 없기 때문입니다.
복합 인덱스 설계 팁
- ** 카디널리티가 높은 컬럼 **을 앞에 배치 (고유한 값이 많은 컬럼)
- 자주 사용하는 WHERE 조건 순서 에 맞추기
- 등호(=) 조건 → 범위(>, <, BETWEEN) 조건 순서로 배치
커버링 인덱스 (Covering Index)
SELECT에 필요한 모든 컬럼이 인덱스에 포함되어 있어서, ** 테이블 본체에 접근하지 않고 인덱스만으로 쿼리를 완료 **하는 것입니다.
-- 인덱스: (name, age)
SELECT name, age FROM users WHERE name = '김철수';
-- → 인덱스만 읽으면 끝! (커버링 인덱스)
SELECT name, age, email FROM users WHERE name = '김철수';
-- → email이 인덱스에 없으므로 테이블까지 가야 함
MySQL의 EXPLAIN에서 Extra 컬럼에 Using index 가 나오면 커버링 인덱스가 적용된 것입니다.
커버링 인덱스가 빠른 이유:
- 인덱스는 테이블 데이터보다 크기가 작아 메모리에 캐시될 확률이 높음
- 테이블로의 랜덤 I/O 가 사라짐 (이게 가장 큰 성능 차이)
클러스터드 vs 논클러스터드 인덱스
| 구분 | 클러스터드 인덱스 | 논클러스터드(보조) 인덱스 |
|---|---|---|
| 리프 노드 | 실제 데이터 행 전체 | 키 + PK(클러스터드 인덱스 키) |
| 테이블당 개수 | 1개 | 여러 개 |
| 순서 | 데이터 물리 저장 순서 = 인덱스 순서 | 별도 구조 |
| 예시 | MySQL InnoDB의 PK | CREATE INDEX로 만든 인덱스 |
논클러스터드 인덱스로 검색하면:
- 보조 인덱스에서 PK 값을 찾고
- PK로 클러스터드 인덱스를 다시 탐색 (** 이를 "테이블 액세스" 또는 "룩업"이라고 함 **)
이 2단계 과정 때문에 커버링 인덱스가 더 빠른 것입니다.
인덱스가 오히려 느린 경우
인덱스가 항상 좋은 건 아닙니다.
카디널리티가 낮은 컬럼
-- gender 컬럼의 값이 'M', 'F' 두 종류뿐이라면
CREATE INDEX idx_gender ON users(gender);
-- → 인덱스를 타도 전체의 50%를 읽어야 함 → Full Scan이 더 효율적
일반적으로 ** 전체 데이터의 10~15% 이상을 읽어야 하면** 옵티마이저가 인덱스를 무시하고 Full Scan을 선택합니다.
쓰기 부하
- INSERT: 테이블 + 모든 인덱스에 새 항목 추가
- UPDATE: 인덱스 키가 변경되면 기존 항목 삭제 + 새 항목 추가
- DELETE: 인덱스에서도 항목 삭제 (실제로는 마킹)
인덱스가 10개인 테이블에 INSERT하면 테이블 쓰기 1회 + 인덱스 쓰기 10회가 발생합니다. 쓰기가 많은 테이블에 인덱스를 남발하면 성능이 크게 떨어집니다.
인덱스 컬럼에 함수 적용
-- ❌ 인덱스 활용 불가
WHERE YEAR(created_at) = 2026
-- ✅ 인덱스 활용 가능
WHERE created_at >= '2026-01-01' AND created_at < '2027-01-01'
컬럼에 함수를 씌우면 인덱스의 정렬 순서가 깨져서 인덱스를 활용할 수 없습니다. (MySQL 8.0+에서는 함수 기반 인덱스로 해결 가능)
정리
- B+Tree는 내부 노드에 키만 저장하고, 리프 노드끼리 연결되어 범위 검색이 효율적
- 100만 건이어도 3~4번의 디스크 I/O로 검색 가능
- 복합 인덱스는 선두 컬럼부터 순서대로 매칭 — 중간을 건너뛸 수 없음
- 커버링 인덱스로 테이블 접근 자체를 없앨 수 있음
- 카디널리티가 낮거나 쓰기가 많은 경우 인덱스가 오히려 독이 됨
인덱스는 "읽기 성능 vs 쓰기 비용"의 트레이드오프입니다. 무조건 만드는 게 아니라, 실행 계획(EXPLAIN)을 확인하면서 필요한 곳에만 정확히 만드는 것이 핵심입니다.