인덱스 기초

2. 핵심 원리

2.1 인덱스가 조회를 빠르게 하는 이유 — B-tree

인덱스의 기본 구조는 B-tree(균형 트리)입니다. 컬럼 값을 정렬된 상태로 트리 모양에 나눠 담아, 루트에서 리프까지 몇 단계만 내려가면 원하는 값의 위치를 찾습니다.

행이 늘어도 트리의 깊이는 아주 천천히만 늘어납니다. 백만 건이든 천만 건이든 비교 횟수가 몇 번 차이 나지 않는 것이 B-tree 가 큰 테이블에서도 빠른 이유입니다.

핵심

인덱스가 없으면 WHERE 조건에 맞는 행 하나를 찾는 데도 전체 행을 다 읽어야 합니다(O(n)). 인덱스가 있고 그 인덱스를 제대로 타면 트리 깊이만큼만 비교해 찾습니다(O(log n)).

2.2 DB 별 기본 인덱스 구조

세 DB 모두 기본 인덱스 구조는 B-tree 계열이지만, 이름과 테이블 자체의 저장 방식이 다릅니다.

MySQL 의 InnoDB 는 PK 자체가 클러스터드 인덱스라, 테이블 데이터가 PK 순서로 물리적으로 쌓입니다. 보조 인덱스(secondary index)는 값을 찾은 뒤 그 PK 값으로 다시 실제 행을 찾아갑니다.

MSSQL 도 PK 를 만들면 기본적으로 클러스터드 인덱스가 되어 테이블당 하나만 존재하고, 나머지 인덱스는 모두 논클러스터드입니다. Oracle 의 기본 테이블은 힙 구조라 행 순서가 정해져 있지 않고, 클러스터드와 비슷한 구조가 필요하면 IOT(인덱스 구성 테이블)를 따로 씁니다. 이 레슨의 H2 예제는 이 저장 구조 차이까지는 재현하지 않고, EXPLAIN 의 인덱스 이름·tableScan 여부로 "인덱스를 탔는지"만 확인합니다.

2.3 PK · UNIQUE 제약과 자동 생성 인덱스

PRIMARY KEY 와 이름 붙인 UNIQUE 제약은 컬럼 값을 검사하기 위해 내부적으로 인덱스를 함께 만듭니다. CREATE INDEX 를 따로 쓰지 않아도, 테이블을 만드는 순간 이미 인덱스가 생겨 있습니다.

3절 예제 2 에서 CREATE INDEX 를 한 번도 안 쓴 테이블에 인덱스가 이미 2개 있는 걸 직접 확인합니다. 이 동작은 Oracle · MySQL · MSSQL 모두 같습니다.

2.4 복합 인덱스와 선두 컬럼

인덱스는 컬럼 하나가 아니라 여러 컬럼을 묶어서 만들 수 있습니다. (dept, hired) 처럼 두 컬럼을 묶은 인덱스를 복합 인덱스라고 부릅니다.

복합 인덱스는 맨 앞에 온 컬럼(선두 컬럼) 기준으로 정렬됩니다. 그래서 WHERE 조건에 선두 컬럼이 빠져 있으면, 그 인덱스는 대부분 못 타고 다른 컬럼만으로는 정렬된 순서를 활용할 수 없습니다.

팁

복합 인덱스의 컬럼 순서는 자주 쓰는 조건 순서에 맞춰 정합니다. dept = ? 조건만 단독으로도 자주 쓰인다면 dept 를 선두에 두고, dept 없이 hired 만 조건으로 걸리는 쿼리가 많다면 hired 단독 인덱스를 따로 둡니다.

2.5 인덱스의 비용

인덱스는 조회만 빠르게 하고 대가 없이 따라오지 않습니다. INSERT · UPDATE · DELETE 가 일어날 때마다 데이터뿐 아니라 그 위에 걸린 인덱스도 함께 갱신해야 해서, 인덱스가 많을수록 쓰기 작업이 느려집니다.

인덱스 자체도 별도 저장 공간을 차지합니다. 컬럼 값과 위치 정보를 따로 저장하므로, 인덱스가 여러 개면 테이블 원본보다 더 큰 공간을 인덱스가 차지하는 경우도 흔합니다.

선택도(selectivity)가 낮은 컬럼, 즉 성별처럼 값의 종류가 몇 개 안 되는 컬럼은 인덱스를 걸어도 효과가 작습니다. 조건에 맞는 행이 전체의 절반 가까이 되면, 인덱스를 타는 비용이 그냥 순서대로 훑는 것보다 오히려 클 수 있습니다.

2.6 실행 계획으로 인덱스 사용 확인하기

쿼리가 인덱스를 실제로 탔는지는 짐작이 아니라 실행 계획으로 확인합니다. DB 마다 실행 계획을 보는 명령이 다릅니다.

H2 의 EXPLAIN 은 실제 실행 없이 계획만 보여줍니다. 계획에 쓰인 인덱스 이름이 나오면 그 인덱스를 탄 것이고, tableScan 이라고 나오면 인덱스를 안 타고 테이블을 처음부터 훑은 것입니다. 이 레슨에서 보이는 결과는 H2 의 계획 표기이며 실제 Oracle · MySQL · MSSQL 의 출력 형태는 다릅니다. 실행 계획을 줄 단위로 읽는 방법은 SQL 고급 09 레슨에서 더 다룹니다.

2.7 인덱스를 못 타는 대표 조건

아래 조건은 인덱스가 있어도 옵티마이저가 못 타고 풀 스캔으로 넘어가는 대표적인 경우입니다.

부정 조건(!=, NOT IN)은 "이 값이 아닌 모든 행"을 찾아야 해서 정렬된 인덱스로 좁혀 들어갈 범위 자체가 애매해 대체로 풀 스캔으로 처리됩니다. 선두 컬럼이 없어도 Oracle 은 특정 조건에서 INDEX SKIP SCAN 이라는 예외적인 방식으로 인덱스를 쓸 수 있으나, 뒤 컬럼의 값 종류가 적을 때만 동작하는 최적화라 기본적으로는 선두 컬럼 조건을 갖추는 편이 안전합니다.

주의

IS NULL 은 DB 마다 다릅니다. Oracle 의 단일 컬럼 B-tree 인덱스는 NULL 값을 아예 저장하지 않아 WHERE col IS NULL 에 그 인덱스를 못 씁니다. MySQL · MSSQL 은 NULL 도 인덱스에 저장해 그대로 씁니다. 4절 예제 10 에서 보듯 H2 는 NULL 도 인덱스에 저장해 이 조건에서도 인덱스를 타므로, 이 한 곳은 H2 옵티마이저 판단이며 Oracle 과는 다릅니다.