인덱스 — B+Tree·클러스터형·커버링 (PostgreSQL·MySQL)

인덱스가 하는 일과 그 대가

100만 행 테이블에서 email = 'x'인 행을 찾는다고 하자. 인덱스가 없으면 DB는 100만 행을 처음부터 한 줄씩 다 읽어 비교한다(풀 스캔, O(n)). 인덱스가 있으면 — 책 뒤의 색인처럼 몇 번의 탐색으로 그 행에 닿는다(O(log n)). 수백만 행에서 한 행을 찾는 일이 수십만 배 빨라진다.

그런데 인덱스는 공짜가 아니다. 인덱스는 별도의 정렬된 자료구조라 — 행을 INSERT/UPDATE/DELETE할 때마다 그 인덱스도 함께 갱신해야 하고, 디스크·메모리도 더 쓴다. 즉 인덱스는 읽기를 빠르게 하는 대신 쓰기를 느리게 한다. 그래서 인덱스의 핵심은 "많이 만들기"가 아니라 "어떤 쿼리를 위해, 어떤 칼럼을, 어떤 순서로" 신중히 고르기다. (출처: Use The Index, Luke! / PostgreSQL — Indexes.)

왜 B+Tree인가 — 디스크에 맞춰 설계된 트리

인덱스가 이진 탐색 트리가 아니라 B+Tree(한 노드가 수백 개 키를 담는 넓고 얕은 트리)인 데는 디스크의 물리적 성질이 있다. 디스크는 1바이트가 아니라 페이지(보통 8KB/16KB) 단위로 읽는다 — 한 번 디스크에 다녀오는 비용이 비싸다. 그러니 한 번 읽을 때 키를 최대한 많이 담아야(fan-out을 키워야) 이득이다. 이진 트리라면 100만 행에 높이가 20쯤 되어 20번 디스크에 다녀와야 하지만, fan-out이 수백인 B+Tree는 높이 3~4면 닿는다 — 디스크 접근이 3~4번으로 끝난다.

다이어그램 로딩 중…

B+Tree가 일반 B-Tree와 다른 결정적 한 가지 — 실제 데이터(또는 포인터)가 리프에만 있고, 리프끼리 연결 리스트로 이어져 있다는 점이다. 덕분에 *범위 검색(BETWEEN·ORDER BY·>)*이 리프를 옆으로 쭉 훑기만 하면 되어 빠르다 — 등치 검색뿐 아니라 범위·정렬에도 강한 이유다.

클러스터형 vs 비클러스터형 — InnoDB와 PostgreSQL의 결정적 차이

이게 두 엔진의 가장 큰 구조 차이이고, UUID PK 논쟁·보조 인덱스 비용의 뿌리다.

MySQL InnoDB — PK가 곧 데이터(클러스터형 인덱스): InnoDB는 테이블 자체가 PK 기준 B+Tree다. 리프에 행 전체가 PK 순서로 저장된다. 결과가 셋이다. (1) 보조 인덱스(secondary index)의 리프는 행 위치가 아니라 PK 값을 담는다 — 그래서 보조 인덱스로 찾으면 ①보조 인덱스 트리에서 PK를 찾고 → ②PK 트리에서 행을 찾는 2단계 조회가 된다. (2) PK가 크면 모든 보조 인덱스가 그 PK 값을 품어 함께 커진다 → PK는 작아야 한다. (3) PK는 단조 증가(AUTO_INCREMENT)가 유리하다 — 랜덤 UUIDv4를 PK로 쓰면 삽입이 트리 중간 여기저기에 일어나 페이지 분할·단편화가 심해진다(그래서 시간순 정렬되는 UUIDv7·ULID가 대안).

PostgreSQL — 힙(heap) + 전부 비클러스터형: PostgreSQL은 행을 힙에 순서 없이 저장하고, PK조차 별도 인덱스다. 모든 인덱스 리프는 *행의 물리 위치(TID)*를 가리킨다. CLUSTER 명령으로 한 번 물리 정렬할 수 있지만 유지되지 않는다(이후 삽입은 다시 흩어짐). 그래서 PG엔 "클러스터형 PK" 개념이 없다 — 같은 "PK 인덱스"라도 InnoDB에선 데이터 그 자체, PostgreSQL에선 힙을 가리키는 별도 구조다.

복합 인덱스 — 왜 칼럼 순서가 전부인가

여러 칼럼을 묶은 **복합 인덱스 (a, b, c)**는 칼럼 순서가 결정적이다. 이유는 B+Tree가 a로 먼저 정렬하고, a가 같은 것끼리 b로, b가 같은 것끼리 c로 정렬하기 때문이다(전화번호부가 성→이름 순인 것과 같다). 그래서 *왼쪽 접두사(leftmost prefix)*부터만 쓸 수 있다.

INDEX (a, b, c) 가 도움 되는 조회:
  WHERE a = ?                       ✅
  WHERE a = ? AND b = ?             ✅
  WHERE a = ? AND b = ? AND c = ?   ✅
  WHERE b = ?                       ❌ (a를 건너뛰면 정렬이 무의미)
  WHERE a = ? AND c = ?             △ (a까지만 인덱스, c는 걸러내기)

전화번호부에서 이름만으로는 못 찾는 것과 같다(성을 모르면 정렬이 소용없다). 그래서 — 등치(=) 조건 칼럼을 앞에, 범위(>·BETWEEN) 칼럼을 뒤에 둔다(범위 조건 뒤의 칼럼은 인덱스 정렬을 못 쓴다). 그리고 ORDER BY가 인덱스 순서와 맞으면 별도 정렬 연산 없이 끝난다.

커버링 인덱스 — 테이블을 아예 안 본다

쿼리가 필요로 하는 모든 칼럼이 인덱스 안에 다 있으면, DB는 테이블(힙/PK 트리)에 가지 않고 인덱스만으로 답한다 — 커버링 인덱스(index-only scan). 테이블 접근(특히 InnoDB의 2단계 조회)을 통째로 생략하니 I/O가 크게 준다.

-- PostgreSQL: INCLUDE로 비검색 칼럼을 리프에 얹어 커버링
CREATE INDEX idx_member_email ON member (email) INCLUDE (created_at);
-- SELECT created_at FROM member WHERE email = ?  → 인덱스만으로 처리(힙 접근 0)

InnoDB는 보조 인덱스에 PK가 이미 포함되므로 SELECT pk 같은 건 자연스레 커버링이 되고, PostgreSQL의 index-only scan은 가시성 맵까지 봐야 해 VACUUM이 잘 돈 테이블에서 더 잘 통한다([05·08]).

인덱스가 안 먹는 흔한 경우

인덱스를 만들어도 옵티마이저가 안 쓰는 전형적 함정 — 이걸 모르면 *"인덱스 걸었는데 왜 느리지?"*에 빠진다.

칼럼에 함수·연산 — WHERE YEAR(created_at) = 2026 ❌. 인덱스는 칼럼 원본 값으로 정렬됐는데 함수를 씌우면 그 정렬을 못 쓴다 → *범위(>= '2026-01-01' AND < '2027-01-01')*로 풀거나 표현식 인덱스(ON t (lower(email))·MySQL functional index).
앞 와일드카드 — LIKE '%kim' ❌(B+Tree는 앞부터 정렬이라 앞을 모르면 못 탄다). 뒤 와일드카드 'kim%'는 ✅. 전문검색은 GIN+tsvector(PG)/FULLTEXT(MySQL).
묵시적 형변환 — 문자열 칼럼에 숫자를 비교하면 형변환이 일어나 인덱스를 깬다.
선택도가 낮은 칼럼 — gender처럼 값이 두세 개뿐이면, 인덱스가 대부분 행을 가리켜 풀 스캔이 오히려 빠르다(카디널리티/선택도가 핵심). 옵티마이저가 일부러 인덱스를 안 쓴다.

엔진별 특수 인덱스

PostgreSQL — 종류가 풍부하다: B-tree(기본), Hash(등치 전용), GIN(역색인 — 전문검색·jsonb·배열에 강함), GiST/SP-GiST(기하·범위·근접), BRIN(아주 큰 자연 정렬 테이블 — 블록 범위만 저장해 초경량, 시계열에 적합). 거기에 부분 인덱스(WHERE status='active'로 조건 맞는 행만 색인 → 작고 빠름)·표현식 인덱스. MySQL — InnoDB B+Tree 중심에 FULLTEXT·SPATIAL(R-tree)·functional/descending/invisible index(8.0+ — invisible로 지우기 전 영향 시험).

비용 — 안 쓰는 인덱스는 부채

다시 강조하면 — 인덱스는 읽기를 빠르게, 쓰기를 느리게 한다(매 변경마다 관련 인덱스 모두 갱신). 안 쓰는 인덱스는 디스크·쓰기 성능을 갉아먹는 순수 부채다. 원칙은 "느린 쿼리의 EXPLAIN을 보고, 그 쿼리를 위한 인덱스만 신중히 추가"([07])다 — 칼럼마다 무작정 인덱스를 거는 건 안티패턴이다.

한 줄 요약 — 인덱스=B+Tree(넓고 얕음·디스크 페이지에 맞춰 fan-out↑·리프 연결로 범위 강함). InnoDB는 PK=클러스터형(데이터 그 자체·보조 인덱스 2단계·작은 단조 PK 선호·랜덤 UUID는 분할), PostgreSQL은 힙+전부 비클러스터형(TID). 복합 인덱스는 왼쪽 접두사·등치 먼저 범위 나중. 커버링이면 테이블 생략. 함수·앞와일드카드·형변환·낮은 선택도는 인덱스를 깬다. 안 쓰는 인덱스는 부채.

(출처: Use The Index, Luke! / PostgreSQL 17 — Index Types / MySQL 8.4 — InnoDB Index Types / Optimization.)