Ch.11 인덱스의 원리¶

< Binary Search와 B-Tree | 유사 사례와 키워드 정리 >

앞에서 B-Tree가 디스크 I/O를 최소화하면서 O(log_b n) 검색을 제공한다는 걸 봤다. 이제 실제 DB 인덱스가 어떻게 동작하는지, 그리고 왜 종종 "있어도 안 타는지" 본다.

인덱스를 걸면 정확히 무엇이 생기고 무엇이 빨라지나¶

"인덱스를 걸었는데 왜 안 빨라지지?"를 따지려면, 먼저 인덱스가 걸렸을 때 제대로 빨라지는 그림부터 잡아야 한다. 인덱스는 책의 색인(목차)과 같다. 500페이지짜리 책에서 "TCP"라는 단어를 찾으려면:

목차 없음: 1페이지부터 500페이지까지 넘기면서 찾는다 (Full Table Scan)
목차 있음: "T" 섹션을 찾고, "TCP → 342페이지"를 보고 바로 간다 (Index Scan)

DB 인덱스도 이 원리다. CREATE INDEX idx_email ON users(email)을 실행하면, email 컬럼의 값들을 B+Tree로 정렬해서 별도의 자료구조를 만든다. 검색할 때 이 트리를 타고 바로 해당 레코드를 찾는다.

-- 인덱스 없을 때: Full Table Scan (모든 행을 순회)
SELECT * FROM users WHERE email = 'test@test.com';

-- email에 인덱스가 있을 때: Index Scan (B+Tree에서 바로 찾음)
SELECT * FROM users WHERE email = 'test@test.com';

SQL은 동일하다. DB 엔진(쿼리 옵티마이저)이 인덱스 유무를 판단해서 알아서 최적의 경로를 선택한다.

(여기서 "옵티마이저가 알아서 한다"는 말이 위험하다. 안 탈 때가 많다. 그래서 EXPLAIN으로 확인해야 한다.)

그래서 지금 이 쿼리가 인덱스를 타긴 타는지 어떻게 아나¶

"빨라졌을 것"이라는 짐작은 위험하다. 안 탔는데 탔다고 믿는 게 이 장 의문의 출발점이니, 먼저 사실 확인 도구부터 손에 쥔다. 쿼리가 인덱스를 사용하는지 확인하려면 EXPLAIN 명령을 쓴다.

-- 인덱스가 없는 경우
EXPLAIN SELECT * FROM users WHERE email = 'test@test.com';
-- type: ALL (Full Table Scan)

-- 인덱스를 추가한 후
CREATE INDEX idx_users_email ON users(email);
EXPLAIN SELECT * FROM users WHERE email = 'test@test.com';
-- type: ref (Index Scan)

EXPLAIN type 값의 의미¶

MySQL EXPLAIN의 type 컬럼은 인덱스 사용 방식을 보여준다. 좋은 순서대로:

type	의미	비유
`system`	테이블에 행이 0개 또는 1개	"찾을 게 한 권뿐인 도서관"
`const`	PRIMARY KEY/UNIQUE 인덱스로 1행만 매칭	책 번호로 직접 찾기
`eq_ref`	JOIN 시 한쪽 테이블당 1행만 매칭 (PK/UNIQUE)	학번으로 학생 1명
`ref`	일반 인덱스로 매칭, 여러 행 가능	"이름 김"인 사람 다 찾기
`range`	인덱스 범위 스캔 (`BETWEEN`, `>`, `<`, `IN`)	100~200페이지
`index`	인덱스 전체 스캔 (테이블 대신 인덱스만 훑음)	색인 자체를 처음부터 끝까지
`ALL`	Full Table Scan, 인덱스 못 씀	책을 처음부터 끝까지

ALL이 나오면 일단 의심해야 한다. 작은 테이블이면 옵티마이저가 일부러 ALL을 선택하기도 한다(인덱스 타는 비용보다 그냥 다 읽는 게 싸서). 큰 테이블에서 ALL이 나오면 인덱스 설계나 쿼리 작성을 점검해야 한다.

(MySQL이 아닌 PostgreSQL은 EXPLAIN 출력 형식이 다르다. Seq Scan = Full Table Scan, Index Scan = Index 사용, Bitmap Index Scan = 여러 인덱스 조합. 원리는 같다.)

인덱스를 탈 때 빨라지는 폭은 어디서 나오나¶

EXPLAIN이 ref를 찍었다고 끝이 아니다. 그 한 줄이 실제로 얼마나 큰 이득인지 I/O 횟수로 환산해두면, 안 탔을 때 잃는 게 뭔지도 같이 보인다. 같은 "100건 조회"인데 인덱스 유무에 따라 디스크 I/O 횟수가 달라진다.

조건	디스크 I/O	비유
100만 행 Full Scan, 한 페이지에 100행	10,000 페이지 읽음	책 전체 훑기
B+Tree 깊이 3, 리프에서 100행 연속	3 + 1 = 4 페이지 읽음	색인 보고 한 챕터만

데이터가 메모리에 다 있으면 차이가 별로 안 난다. 디스크에 있는 순간(또는 워킹셋이 메모리보다 크면) 차이가 수천 배로 벌어진다.

그렇게 좋으면 전부 다 걸면 안 되는 이유¶

"안 빨라진다"의 반대편에는 "걸수록 느려지는 곳"이 있다. 무작정 인덱스를 늘리기 전에 대가부터 확인하자. 인덱스가 공짜는 아니다.

항목	비용
디스크 공간	인덱스도 저장해야 한다 (테이블 크기의 10~30% 추가)
메모리(버퍼 풀)	자주 쓰는 인덱스는 메모리에 캐시 → 인덱스 많으면 캐시 경쟁
INSERT 성능	레코드를 추가할 때 모든 인덱스도 갱신해야 한다
UPDATE 성능	인덱스 컬럼이 변경되면 인덱스도 재정렬
DELETE 성능	인덱스에서도 제거해야 한다

읽기 성능은 올라가지만 쓰기 성능은 내려간다. 그래서 "모든 컬럼에 인덱스를 걸면 빠르겠지"는 틀린 생각이다. 자주 검색하는 컬럼에만 전략적으로 걸어야 한다.

쓰기가 많은 테이블(예: 로그 적재 테이블, 카운터 테이블)에 인덱스가 5~10개 붙어 있으면 INSERT TPS가 절반 이하로 떨어진다. 검색은 안 하면서 인덱스만 잔뜩 쌓인 테이블도 흔히 보는 안티패턴이다.

(인덱스 설계 원칙은 Ch.14에서 자세히 다룬다. 카디널리티, 복합 인덱스 순서, 안 쓰는 인덱스 찾는 법 등.)

인덱스를 탔는데도 느리면, 테이블을 또 읽고 있는 건 아닌가¶

인덱스를 제대로 타고도 기대만큼 안 빨라지는 흔한 이유 하나가, 인덱스로 위치만 찾고 본체를 다시 읽는 두 단계다. 이 "두 단계"가 정확히 무엇인지는 InnoDB가 인덱스를 저장하는 방식에서 나온다.

InnoDB에는 두 종류의 B+Tree가 있다.

Clustered Index(클러스터형 인덱스): Primary Key 순으로 정렬된 B+Tree인데, 그 리프 노드에 행 데이터 전체가 들어 있다. 즉 테이블 자체가 PK로 정렬된 B+Tree다.
Secondary Index(보조 인덱스): CREATE INDEX idx_email ...로 만드는 인덱스. 리프 노드에 행 데이터가 아니라 그 행의 Primary Key 값만 들어 있다.

그래서 WHERE email = ...로 secondary index를 타면 두 번의 트리 탐색이 일어난다.

1단계: Secondary Index(email) B+Tree 탐색 → 리프에서 PK 값을 얻음
2단계: 그 PK로 Clustered Index B+Tree를 다시 탐색 → 리프에서 행 전체를 읽음
       (이 2단계를 'Double Lookup' 또는 북마크 룩업이라 한다)

이 두 번째 탐색이 SELECT email, name에서 name을 가져오기 위한 비용이다. 이걸 한 단계로 줄이는 게 Covering Index다. 쿼리에서 필요한 모든 컬럼이 인덱스 안에 들어 있으면, 2단계(Clustered Index 재탐색)를 생략하고 secondary index 리프에서 바로 응답을 만들 수 있다. 이걸 Covering Index라고 한다.

-- 일반 쿼리: 인덱스로 위치 찾고 → 테이블에서 다른 컬럼 읽기 (I/O 2단계)
SELECT email, name FROM users WHERE email = 'test@test.com';
CREATE INDEX idx_email ON users(email);

-- Covering Index: 인덱스만으로 끝 (I/O 1단계)
CREATE INDEX idx_email_name ON users(email, name);
SELECT email, name FROM users WHERE email = 'test@test.com';

EXPLAIN의 Extra 컬럼에 Using index라고 뜨면 Covering Index가 동작한 것이다. 테이블을 안 만지고 인덱스만 본 거니까 디스크 I/O가 절반 이하로 줄어든다.

(주의: 모든 컬럼을 인덱스에 넣으면 인덱스 크기가 폭증해서 그 자체로 캐시 효율이 떨어진다. SELECT가 자주 도는 핵심 쿼리에만 신중히 적용한다.)

Covering Index (커버링 인덱스)

쿼리가 필요로 하는 모든 컬럼이 포함되어 있어서 테이블 본체를 읽지 않고 인덱스만으로 답할 수 있는 인덱스다. 디스크 I/O를 한 단계 줄여서 빠르다. WHERE/SELECT/ORDER BY/GROUP BY에 등장하는 모든 컬럼이 인덱스에 있어야 한다. Ch.14에서 복합 인덱스 설계와 같이 다룬다.

인덱스를 걸었는데 왜 안 빨라지지: 범인은 대개 쿼리 쪽이다¶

이 장의 핵심 의문이 여기서 풀린다. EXPLAIN에 ALL이 찍히는데 인덱스는 분명히 걸려 있다면, 의심할 곳은 인덱스가 아니라 쿼리를 어떻게 썼느냐다. 인덱스를 걸어놓고도 옵티마이저가 안 쓰는 경우가 있다. 대부분 쿼리를 어떻게 썼느냐의 문제다.

안티패턴 1: 함수를 적용한 컬럼¶

-- 안 탐: name 컬럼에 인덱스가 있어도 LOWER(name)은 다른 값이다
SELECT * FROM users WHERE LOWER(name) = 'teo';

-- 탐: 함수를 값 쪽으로 옮기거나
SELECT * FROM users WHERE name = 'Teo';

-- 또는 함수 기반 인덱스(Functional Index)를 만든다
CREATE INDEX idx_users_lower_name ON users((LOWER(name)));

인덱스는 컬럼 값을 정렬해둔 자료구조다. LOWER(name)은 인덱스가 미리 정렬해둔 값이 아니다. 그래서 옵티마이저는 인덱스를 포기하고 Full Scan으로 간다.

안티패턴 2: 형변환(Implicit Type Conversion)¶

-- id가 INT 컬럼인데 문자열로 비교
SELECT * FROM users WHERE id = '123';
-- → DB가 모든 행의 id를 문자열로 변환한 뒤 비교 = 인덱스 못 씀

-- 타입 맞춰서 비교
SELECT * FROM users WHERE id = 123;

암묵적 형변환은 컬럼 쪽에 함수가 붙는 것과 같은 효과다. 옵티마이저가 인덱스를 못 탄다. ORM이 자동으로 잘못된 타입을 박는 경우도 흔하다. 운영 쿼리 로그에서 항상 의심해야 할 부분이다.

안티패턴 3: 부정 조건 (NOT IN, !=, NOT LIKE)¶

-- 안 탐: "이게 아닌 것"은 인덱스로 좁히기 어렵다
SELECT * FROM orders WHERE status != 'COMPLETED';
SELECT * FROM orders WHERE status NOT IN ('COMPLETED', 'CANCELED');

부정 조건은 "해당하지 않는 모든 값"을 봐야 하므로 옵티마이저가 인덱스로 좁히지 못한다. 가능하면 긍정 조건으로 바꾼다.

-- 좋음: status가 가능한 값이 적으면 IN으로 나열
SELECT * FROM orders WHERE status IN ('PENDING', 'PROCESSING');

안티패턴 4: LIKE의 앞쪽 와일드카드¶

-- 안 탐: 앞이 비었으니까 어디서부터 시작할지 모름
SELECT * FROM products WHERE name LIKE '%phone%';

-- 탐: 앞이 고정되어 있으면 인덱스 범위 스캔 가능
SELECT * FROM products WHERE name LIKE 'phone%';

B+Tree는 앞쪽(왼쪽) 문자부터 정렬한다. 앞이 와일드카드면 트리의 어디서 시작할지 결정할 수 없다.

부분 일치 검색이 핵심 기능이면 인덱스로는 한계가 있다. Full Text Search(MySQL FULLTEXT, PostgreSQL tsvector) 또는 검색 엔진(Elasticsearch, OpenSearch)이 필요하다.

(이 네 가지 안티패턴은 운영 장애의 단골 원인이다. "인덱스를 걸었는데 왜 안 빨라지죠?"라는 질문의 9할이 이 중 하나다.)

쿼리는 멀쩡한데 안 빨라진다면, 그 컬럼이 애초에 안 걸리는 컬럼은 아닌가¶

안티패턴 네 개를 다 피했는데도 인덱스 효과가 없을 수 있다. 이번엔 쿼리가 아니라 컬럼 자체의 성질을 의심할 차례다. 인덱스는 컬럼의 값이 얼마나 다양한지에 따라 효과가 달라진다. 이걸 Cardinality(카디널리티)라고 한다.

높은 카디널리티: 값이 다양함 (예: 이메일, 유저 ID, UUID)
낮은 카디널리티: 값이 적음 (예: 성별, boolean 컬럼, 상태값 5개)

-- 높은 카디널리티 컬럼에 인덱스: 효과 좋음
CREATE INDEX idx_email ON users(email);
SELECT * FROM users WHERE email = 'test@test.com';
-- → 1건만 매칭, 인덱스 한 방에 끝

-- 낮은 카디널리티 컬럼에 인덱스: 효과 미미
CREATE INDEX idx_gender ON users(gender);
SELECT * FROM users WHERE gender = 'M';
-- → 100만 건 중 50만 건 매칭. 인덱스 타도 결국 절반을 다 읽음
-- 옵티마이저가 차라리 Full Scan을 선택하기도 함

낮은 카디널리티 컬럼은 단독 인덱스로는 의미가 없다. 다른 컬럼과 묶어서 복합 인덱스(CREATE INDEX idx ON users(gender, age))로 만들면 의미가 생긴다. 복합 인덱스 설계는 Ch.14에서 다룬다.

선택도가 낮은 쿼리는 인덱스 효과를 못 보는 게 정상이다. 무조건 인덱스를 걸기 전에 "이 컬럼으로 좁히면 결과가 얼마나 줄어드는가?"부터 본다. 줄어드는 비율이 5% 이하 정도여야 인덱스 효과가 확실하다.

Cardinality (카디널리티, 선택도)

컬럼이 가질 수 있는 고유한 값의 다양성이다. 이메일이나 유저 ID처럼 거의 모든 행이 다른 값이면 카디널리티가 높고, 성별이나 boolean처럼 두세 가지 값만 있으면 낮다. 카디널리티가 높을수록 인덱스 효과가 크다. 옵티마이저는 통계 정보로 카디널리티를 추정해서 인덱스 사용 여부를 결정한다.

다시 사례로: 그래서 정렬은 왜 DB에 맡기는 게 맞나¶

인덱스의 동작과 한계를 다 봤으니 처음 질문으로 돌아가자. 사례에서 "애플리케이션에서 정렬하지 말고 DB에서 하라"고 했다. DB가 정렬을 더 잘하는 이유:

인덱스가 있으면 정렬이 필요 없다 (이미 정렬된 B+Tree)
인덱스가 없어도, DB는 디스크 기반 외부 정렬(External Sort)에 최적화되어 있다
LIMIT이 있으면 전체를 정렬하지 않고 상위 N개만 추출하는 최적화가 가능하다 (Top-N Sort)
정렬 결과를 네트워크로 전부 보내지 않는다 (LIMIT 20이면 20건만 전송)

Tim Sort (팀 정렬)

Python의 list.sort()와 sorted()가 사용하는 정렬 알고리즘이다. Merge Sort와 Insertion Sort를 결합한 하이브리드 정렬로, 실제 데이터에서 자주 나타나는 "거의 정렬된" 패턴에 특히 효율적이다. 최선 O(n), 평균/최악 O(n log n)이다. Java의 Arrays.sort()도 객체 배열에 Tim Sort를 사용한다.

Full Table Scan (풀 테이블 스캔)

테이블의 모든 행을 처음부터 끝까지 읽는 것이다. 인덱스를 사용하지 않는다. 데이터가 적을 때는 문제없지만, 수십만 건 이상이면 성능 문제의 주범이 된다. Ch.10의 List에서 Linear Search하는 것과 같은 원리다. EXPLAIN에서 type: ALL로 나타난다.

Index Scan (인덱스 스캔)

인덱스를 사용해서 필요한 행만 빠르게 찾는 것이다. B+Tree를 타고 원하는 위치로 바로 이동한다. Full Table Scan 대비 수십~수백 배 빠를 수 있다. EXPLAIN에서 type: ref, type: range 등으로 나타난다.

Top-N Sort

전체 정렬을 하지 않고 상위 N개만 뽑는 최적화 기법이다. 크기 N짜리 힙(heap)을 유지하면서 한 번 스캔하면 된다. 시간 복잡도가 O(n log n)에서 O(n log k)로 떨어진다. Python의 heapq.nsmallest/nlargest, DB의 ORDER BY ... LIMIT N이 이 최적화를 적용한다.

정렬 알고리즘 자체를 외우는 것보다, "정렬이 필요한 상황에서 가장 효율적인 방법이 뭔가"를 판단하는 능력이 실무에서 중요하다. 대부분의 경우 그 답은 "DB에 인덱스를 걸고 DB에서 하라"이고, 그게 안 되면 Top-N Sort, 그것도 안 되면 미리 정렬해서 캐시에 둔다.

< Binary Search와 B-Tree | 유사 사례와 키워드 정리 >