인덱스는 어떻게 조회를 빠르게 하나

테이블에서 조건에 맞는 행을 찾는 가장 단순한 방법은 처음부터 끝까지 다 읽는 것이다(풀 스캔). 100만 행이면 100만 번 비교한다. 인덱스는 이 비용을 줄이기 위해 특정 컬럼 값을 미리 정렬된 별도 구조로 빼둔 것이다. 책 뒤의 찾아보기가 본문 전체를 훑지 않고 페이지 번호로 바로 가게 해주는 것과 같은 원리다.

B-tree — 정렬을 유지하는 균형 트리

대부분의 DBMS가 인덱스 기본 구조로 B-tree(정확히는 B+tree) 계열을 쓴다. 값이 정렬된 채로 트리에 담겨 있어, 루트에서 리프까지 내려가며 범위를 절반 이하로 계속 좁힌다. 탐색 비용은 트리 높이에 비례하므로 대략 O(log n) — 100만 행이라도 몇 번의 노드 이동으로 원하는 값에 도달한다. 트리가 항상 균형을 유지하도록 삽입·삭제 때 노드를 분할·병합하는 것이 B-tree의 핵심 성질이다.

정렬을 유지하기 때문에 등호 조건뿐 아니라 범위 조건(BETWEEN, <, >)과 정렬(ORDER BY)에도 인덱스가 먹힌다. 반면 해시 인덱스는 등호 조회는 빠르지만 정렬이 없어 범위 검색에 쓸 수 없다 — 시험에서 두 구조를 비교하는 단골 포인트다.

인덱스는 공짜가 아니다

인덱스가 빠르게 하는 건 읽기뿐이다. 쓰기는 오히려 느려진다.

• 삽입·수정·삭제 비용: 행이 바뀔 때마다 걸려 있는 모든 인덱스도 함께 갱신해야 한다. 인덱스가 5개면 INSERT 한 번에 5개의 트리를 손본다.
• 저장 공간: 인덱스는 별도 구조라 그만큼 디스크를 더 쓴다.
• 선택도가 낮으면 무용지물: 성별처럼 값 종류가 몇 개 없는 컬럼은 인덱스를 타도 결국 행 대부분을 읽게 되어 이득이 없다. 값이 고르게 퍼진(선택도 높은) 컬럼일수록 효과가 크다.

그래서 인덱스는 WHERE·JOIN·ORDER BY에 자주 등장하는 컬럼에 선별적으로 건다. 기본키에는 DBMS가 자동으로 인덱스를 만든다.

-- 주문 테이블에서 고객별 조회가 잦다면
CREATE INDEX idx_orders_customer ON orders (customer_id);

-- 복합 인덱스: 선두 컬럼(customer_id) 조건 없이 status만으로는 못 탄다
CREATE INDEX idx_orders_cust_status ON orders (customer_id, status);

복합 인덱스는 컬럼 순서가 곧 정렬 순서다. 전화번호부가 “성, 이름” 순으로 정렬돼 있으면 성 없이 이름만으로는 찾을 수 없는 것과 같다.

클러스터드 vs 넌클러스터드

클러스터드 인덱스는 테이블의 실제 저장 순서 자체를 인덱스 순서로 만든 것이다. 데이터가 곧 정렬이므로 테이블당 하나만 만들 수 있다. 넌클러스터드 인덱스는 별도 구조에 값과 행 위치(포인터)만 담아, 여러 개를 만들 수 있는 대신 인덱스에서 실제 행으로 한 번 더 찾아가는 비용이 든다.

시험 관점 요약

정처기에서 인덱스는 “조회는 빠르게, 갱신은 느리게”라는 트레이드오프로 출제된다. B-tree는 범위 검색 가능·해시는 등호만, 기본키 자동 인덱스, 클러스터드는 테이블당 1개 — 이 네 가지 대비만 잡아두면 개념 문제는 대부분 풀린다. 결국 인덱스 설계란 읽기와 쓰기 중 무엇이 잦은 테이블인지 판단하는 일이다.