DB - 인덱스 쿼리 최적화

인덱스 (B-Tree, 쿼리, 옵티마이저)

데이터베이스의 응답 시간은 거의 항상 인덱스(Index) 설계가 좌우한다. 같은 쿼리도 인덱스가 있을 때와 없을 때 1000배 이상 차이가 나고, 같은 인덱스도 컬럼 순서·타입에 따라 사용되거나 무시된다. 본 글은 인덱스의 핵심 자료구조(B-Tree·B+Tree·Hash·Bitmap), 쿼리 옵티마이저의 동작 원리, 그리고 EXPLAIN으로 실행 계획을 분석해 인덱스를 진단하는 실전 절차를 세심하게 정리한다(출처: 위키백과 — Database index). 제가 학교 캡스톤에서 사용자 검색 화면이 30초 걸리던 쿼리에 복합 인덱스 하나를 추가하자 30ms로 떨어진 모습을 본 후로는 "DB 튜닝의 90%는 인덱스 설계와 EXPLAIN 읽기"라는 사실을 손끝으로 받아들였다.

 

인덱스 자료구조 — B-Tree·B+Tree·Hash·Bitmap

데이터베이스의 인덱스는 디스크 기반 자료구조이며, 메모리 자료구조와는 다른 제약(블록 단위 입출력·랜덤 I/O 최소화·정렬된 순차 접근)을 만족해야 한다. 시험과 실무 모두에서 자주 출제되는 네 가지 인덱스 자료구조를 표로 정리하면 다음과 같다.

인덱스	핵심 자료구조	강점	약점
B-Tree	균형 다진(多進) 트리	범위·정렬·등치 모두 O(log n)	디스크 접근 회수가 트리 높이
B+Tree	B-Tree 변형 (리프만 데이터)	범위 스캔에 압도적 강함	B-Tree보다 약간 더 큰 인덱스
Hash 인덱스	해시 테이블	등치 검색 O(1)	범위·정렬 불가
Bitmap 인덱스	컬럼 값마다 비트맵	카디널리티 낮을 때 압축률·AND/OR 빠름	갱신 비용 큼

여기서 B+Tree란 B-Tree의 변형으로 리프 노드만 실제 데이터(또는 데이터 포인터)를 가지고 모든 리프가 연결 리스트로 연결된 트리를 가리키며, MySQL InnoDB·PostgreSQL·Oracle의 기본 인덱스가 모두 B+Tree이다. 리프가 연결되어 있다는 성질 덕분에 범위 검색(WHERE age BETWEEN 20 AND 30)이 리프를 한 번 찾은 뒤 옆으로 스캔하기만 하면 끝나 매우 빠르다.

-- MySQL InnoDB의 기본 인덱스는 B+Tree
CREATE INDEX idx_user_email ON users(email);

-- Hash 인덱스 — 등치만 가능
CREATE INDEX idx_user_id_hash ON users USING HASH (id);   -- PostgreSQL 문법

-- Bitmap 인덱스 — Oracle/Vertica/Greenplum에서 주로 사용
CREATE BITMAP INDEX idx_user_gender ON users(gender);

Hash 인덱스의 등치 검색이 O(1)이라는 사실이 매력적이지만, 범위 검색을 못 한다는 결정적 약점 때문에 실무에서는 B+Tree가 압도적으로 표준이다. 솔직히 제 경험상 학교에서 처음 PostgreSQL의 Hash 인덱스를 시도했다가 BETWEEN 쿼리가 인덱스를 무시하고 풀 스캔으로 가는 모습을 본 후로는, 거의 모든 인덱스는 B-Tree(B+Tree)로 두고 특수한 경우(전문검색·낮은 카디널리티 분석 테이블)에만 다른 인덱스를 검토하는 패턴이 자동으로 자리 잡았다.

Bitmap 인덱스는 성별·결제 상태·요일처럼 카디널리티(서로 다른 값의 개수)가 매우 낮은 컬럼에서 압도적으로 빠르다. 단, 갱신이 잦은 OLTP 환경에서는 비트맵 재계산 비용이 커서 부적합하고, 주로 데이터 웨어하우스·BI 분석 테이블에서 사용된다. 마지막으로 전문 검색이 필요할 때는 Full-Text 인덱스(MySQL FULLTEXT·PostgreSQL GIN/tsvector)와 같은 특수 인덱스를 사용한다.

인덱스 설계의 4가지 원칙

좋은 인덱스 설계의 기준은 네 가지이며, 시험에서 자주 출제되는 항목이다.

원칙	의미	실무 가이드
선택도 (Selectivity)	인덱스가 얼마나 많은 행을 걸러 내는가	선택도 높은 컬럼부터
카디널리티 (Cardinality)	컬럼의 서로 다른 값 개수	너무 낮으면 인덱스 무의미
복합 인덱스 순서	왼쪽 우선 (Leftmost Prefix)	자주 같이 검색되는 컬럼 묶기
커버링 인덱스	쿼리의 모든 컬럼을 인덱스만으로 처리	테이블 접근 0회

여기서 선택도(selectivity)란 인덱스 컬럼의 한 값이 전체 행 중에서 차지하는 비율의 역수를 가리키며, 1 / 해당 컬럼의 distinct 값 개수로 근사된다. 선택도가 낮은 컬럼(예: 성별)에 인덱스를 걸면 인덱스를 타도 절반 가까운 행을 다 읽게 되어 옵티마이저가 풀 스캔을 선택해 버리는 경우가 많다.

복합 인덱스(Composite Index)의 왼쪽 우선 원칙(Leftmost Prefix Rule)은 시험에서 가장 자주 출제되는 함정이다. 인덱스 (a, b, c)는 WHERE a=?, WHERE a=? AND b=?, WHERE a=? AND b=? AND c=? 같은 쿼리에는 적용되지만, WHERE b=?만 있는 쿼리에는 적용되지 않는다. 즉 왼쪽 컬럼부터 차례로 사용해야 인덱스가 동작한다.

-- 복합 인덱스 (a, b, c)
CREATE INDEX idx_order ON orders(user_id, status, created_at);

-- ✅ 인덱스 사용 (왼쪽 우선 만족)
SELECT * FROM orders WHERE user_id = 123;
SELECT * FROM orders WHERE user_id = 123 AND status = 'PAID';
SELECT * FROM orders WHERE user_id = 123 AND status = 'PAID' AND created_at >= '2026-01-01';

-- ❌ 인덱스 사용 불가 (왼쪽 컬럼 빠짐)
SELECT * FROM orders WHERE status = 'PAID';
SELECT * FROM orders WHERE created_at >= '2026-01-01';

여기서 커버링 인덱스(Covering Index)란 쿼리가 요청한 모든 컬럼이 인덱스 안에 포함되어 인덱스만 읽고도 결과를 만들 수 있어 테이블 본체에 한 번도 접근하지 않는 인덱스를 가리키며, SELECT user_id, status FROM orders WHERE user_id = 123이 위 인덱스로 커버링 인덱스가 된다. 테이블 접근(bookmark lookup) 비용을 0으로 만드는 가장 강력한 튜닝 기법이다.

솔직히 이건 예상 밖이었는데, 학교 캡스톤에서 복합 인덱스 순서를 잘못 잡아 6개월간 쿼리 한 줄이 인덱스를 무시하고 풀 스캔으로 가는 줄도 모르고 운영했다가, 멘토 코드 리뷰에서 처음 EXPLAIN을 띄워 보고 나서야 알게 된 경험을 한 후로는 "인덱스를 만들기 전에 EXPLAIN으로 적용 여부를 확인"하는 습관이 자리 잡았다.

쿼리 옵티마이저와 EXPLAIN 실행 계획

데이터베이스에는 쿼리 옵티마이저(Query Optimizer)가 있어 같은 쿼리에 대해 가능한 여러 실행 계획 중 가장 비용이 낮은 계획을 자동으로 선택한다. 옵티마이저는 두 가지 방식으로 분류된다(출처: PostgreSQL 공식 문서 — Query Planning).

옵티마이저	동작 방식	채택 DBMS
규칙 기반 (Rule-Based, RBO)	사전 정의된 규칙(인덱스 우선·조인 순서 등)을 적용	구 Oracle 8 이전
비용 기반 (Cost-Based, CBO)	통계 정보로 계획별 비용을 계산해 최소 비용 선택	현대 모든 주요 DBMS

여기서 비용 기반 옵티마이저(CBO)란 통계 정보(테이블 크기·인덱스 카디널리티·컬럼 값 분포·캐시 적중률)를 사용해 각 실행 계획의 예상 비용을 계산하고 가장 낮은 비용을 선택하는 옵티마이저를 가리키며, 따라서 통계가 오래되거나 부정확하면 옵티마이저가 잘못된 계획을 선택한다. 그래서 운영 환경에서는 ANALYZE 명령으로 정기적으로 통계를 갱신하는 일이 표준이다.

옵티마이저의 동작을 들여다 보는 도구가 EXPLAIN이다. MySQL·PostgreSQL·Oracle 모두 동일한 이름의 명령으로 실행 계획을 보여 준다.

-- PostgreSQL EXPLAIN ANALYZE — 실제 실행 시간까지 측정
EXPLAIN ANALYZE
SELECT u.name, COUNT(o.id) AS order_count
FROM users u
LEFT JOIN orders o ON o.user_id = u.id
WHERE u.created_at >= '2026-01-01'
GROUP BY u.name;

-- 결과 예시 (요약)
-- HashAggregate  (cost=1234..1567 rows=100 width=40)
--   ->  Hash Right Join  (cost=234..1100 rows=10000)
--         Hash Cond: (o.user_id = u.id)
--         ->  Seq Scan on orders o  (cost=0..800 rows=20000)
--         ->  Hash  (cost=200..200 rows=500)
--               ->  Index Scan using idx_user_created on users u (cost=0.42..200)

EXPLAIN 결과를 읽을 때 주목할 핵심 키워드는 다음과 같다.

키워드	의미	해석
Seq Scan	풀 테이블 스캔	인덱스 없음 또는 옵티마이저가 무시
Index Scan	인덱스로 행 위치 찾고 테이블 접근	일반적 정상
Index Only Scan	인덱스만 읽음 (커버링)	최고 성능
Bitmap Heap Scan	비트맵으로 위치 모은 뒤 일괄 테이블 접근	중간 선택도
Nested Loop	작은 테이블 + 인덱스 있는 큰 테이블	한쪽이 작을 때 유리
Hash Join	한쪽을 해시 테이블화	중간 크기 양쪽
Merge Join	양쪽 정렬 후 병합	둘 다 큰 테이블 + 정렬됨

특히 Index Only Scan이 보이면 커버링 인덱스가 잘 동작한 것이고, 의도하지 않은 Seq Scan이 보이면 인덱스가 없거나 옵티마이저가 비효율로 판단한 경우이다. 후자라면 통계 갱신(ANALYZE)·인덱스 추가·쿼리 재작성 중 하나로 대응해야 한다.

-- 통계 갱신
ANALYZE orders;

-- 강제 인덱스 사용 (MySQL — 신중히)
SELECT * FROM orders USE INDEX (idx_user_status)
 WHERE user_id = 123 AND status = 'PAID';

마지막으로 시험 답안에서 자주 쓰이는 정형 표현을 정리하면, "인덱스는 디스크 기반 자료구조로 B-Tree(B+Tree)가 표준이며, 좋은 인덱스 설계는 선택도·카디널리티·복합 인덱스의 왼쪽 우선 원칙·커버링 인덱스의 네 원칙을 따른다. 현대 모든 주요 DBMS는 비용 기반 옵티마이저(CBO)를 채택하므로 통계 갱신(ANALYZE)이 필수이며, EXPLAIN으로 실행 계획을 분석해 Seq Scan과 Index Scan을 구분하는 것이 튜닝의 출발점이다"는 두 문장이 표준 답안 표현으로 통한다. DB응용 시리즈는 이제 ERD 설계·인덱스/쿼리 최적화 두 편을 채웠으며, 다음 글에서는 트랜잭션·동시성 제어·격리 수준 같은 후속 영역을 이어 다룬다.

---

메타 디스크립션: 데이터베이스 인덱스의 4대 자료구조(B-Tree·B+Tree·Hash·Bitmap), 선택도·카디널리티·복합 인덱스·커버링 인덱스의 4가지 설계 원칙, 비용 기반 옵티마이저(CBO)와 EXPLAIN으로 실행 계획을 읽는 실전 절차를 DB 입문자 관점에서 세심하게 정리합니다.