02. B-Tree 인덱스와 탐색 원리 상세

이 문서를 통해 아래 질문들에 답할 수 있게 됩니다.

• B-Tree 계열 인덱스는 어떤 조회에 강한가?
• 동등 조건, 범위 조건, 정렬 조건은 인덱스에서 어떻게 달라지는가?
• 인덱스 스캔이 항상 빠르지 않은 이유는 무엇인가?

개요

대부분의 관계형 DB에서 기본 인덱스는 B-Tree 계열이다. PostgreSQL도 B-Tree를 기본 인덱스 방식으로 제공하고, MySQL InnoDB도 B+Tree 구조를 중심으로 인덱스를 구성한다.

B-Tree를 세부 구현까지 외울 필요는 없지만, 백엔드 개발자는 이 정도는 알아야 한다.

• 값이 정렬된 구조로 저장된다.
• 동등 조건과 범위 조건에 강하다.
• 정렬된 순서로 읽을 수 있어 ORDER BY와 잘 맞을 수 있다.
• 조건이 너무 넓으면 인덱스를 타도 많은 행을 읽어 느릴 수 있다.

원리

B-Tree 계열 인덱스는 루트에서 시작해 중간 노드를 거쳐 리프 노드까지 내려가며 원하는 값의 위치를 찾는다. 테이블 전체를 처음부터 끝까지 훑는 대신 정렬된 키를 따라 탐색한다.

실무에서 중요한 것은 자료구조 그림을 외우는 것보다 “DB가 인덱스에서 어디까지 조건을 처리하고, 어디부터 테이블 row를 읽은 뒤 필터링하는가”를 구분하는 것이다. PostgreSQL 실행 계획에서는 Index Cond와 Filter가 이 차이를 드러낸다. MySQL에서는 key, rows, filtered, Extra를 함께 보며 비슷한 질문을 던진다.

CREATE INDEX idx_members_created_at ON members (created_at);
 
SELECT id, name, created_at
FROM members
WHERE created_at >= timestamp '2026-01-01'
  AND created_at < timestamp '2026-02-01'
ORDER BY created_at ASC
LIMIT 50;

이 쿼리는 created_at 범위 조건과 같은 방향 정렬을 가진다. 인덱스가 있으면 DB는 2026년 1월이 시작되는 지점을 찾아서 순서대로 읽을 수 있다.

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, name, created_at
FROM members
WHERE created_at >= timestamp '2026-01-01'
  AND created_at < timestamp '2026-02-01'
ORDER BY created_at ASC
LIMIT 50;

이때 확인할 것은 “인덱스 이름이 보이는가”가 아니다. 시작 위치를 잘 찾았는지, limit 때문에 일찍 멈췄는지, heap/table 접근이 과한지, sort가 사라졌는지를 본다.

동등 조건

동등 조건은 인덱스가 가장 다루기 쉬운 조건이다.

SELECT id, email
FROM members
WHERE email = 'joseph@example.com';

email이 Unique 인덱스라면 DB는 최대 한 행만 찾으면 된다. 로그인, 주문 번호 조회, 외부 결제 ID 조회처럼 유일 값으로 찾는 API는 인덱스 효과가 크다.

CREATE UNIQUE INDEX uq_members_email ON members (email);

실무에서 이메일 중복 검사 API를 만들 때 다음 패턴만 믿으면 위험하다.

if (memberRepository.existsByEmail(command.email())) {
    throw new DuplicateEmailException();
}
memberRepository.save(new Member(command.email()));

동시 요청 두 개가 동시에 existsByEmail을 통과할 수 있다. 서비스 코드는 사용자 친화적인 에러 메시지를 위해 남겨도 되지만, 최종 중복 방지는 Unique 인덱스가 맡아야 한다.

범위 조건

범위 조건은 특정 구간을 순서대로 읽는다.

SELECT id, title, created_at
FROM posts
WHERE created_at >= timestamp '2026-06-01'
  AND created_at < timestamp '2026-07-01';

범위가 좁으면 인덱스가 유리하다. 하지만 한 달 데이터가 전체 테이블의 절반이라면 DB는 인덱스 스캔보다 테이블 스캔을 고를 수 있다. 인덱스를 타는 것 자체가 목적이 아니라 적게 읽는 것이 목적이다.

범위 조건 뒤에 오는 복합 인덱스 컬럼은 활용 폭이 줄어들 수 있다.

CREATE INDEX idx_posts_created_status ON posts (created_at, status);
 
SELECT id
FROM posts
WHERE created_at >= timestamp '2026-06-01'
  AND created_at < timestamp '2026-07-01'
  AND status = 'PUBLISHED';

이 인덱스는 created_at 범위로 먼저 넓게 읽은 뒤 status를 필터링할 수 있다. 반대로 status = 'PUBLISHED'가 강한 조건이고 그 안에서 최신순 목록을 본다면 (status, created_at)이 더 나을 수 있다.

정렬 조건

B-Tree 인덱스는 정렬된 구조이므로 ORDER BY를 도울 수 있다.

SELECT id, title, created_at
FROM posts
WHERE board_id = 7
ORDER BY created_at DESC, id DESC
LIMIT 20;

이 쿼리에는 다음 인덱스가 잘 맞을 수 있다.

CREATE INDEX idx_posts_board_created_id
ON posts (board_id, created_at DESC, id DESC);

DB는 board_id = 7인 구간으로 이동한 뒤 이미 최신순에 가까운 순서로 20개를 읽을 수 있다. 인덱스가 없다면 많은 게시글을 찾고 정렬한 뒤 20개를 잘라야 할 수 있다.

정렬 방향은 DBMS와 인덱스 정의에 따라 세부 동작이 다를 수 있다. PostgreSQL은 B-Tree 인덱스를 역방향으로도 스캔할 수 있지만, 여러 컬럼의 방향이 섞인 ORDER BY created_at DESC, id ASC 같은 요구는 인덱스 정의와 정확히 맞춰 봐야 한다. MySQL도 버전과 엔진에 따라 descending index 지원과 실행 계획 표기가 달라질 수 있으므로 실제 계획으로 확인한다.

인덱스 스캔이 느릴 수 있는 경우

인덱스 스캔은 무조건 빠른 이름표가 아니다. 인덱스로 많은 row pointer를 찾은 뒤 테이블 행을 랜덤하게 읽어야 하면 오히려 비싸질 수 있다.

SELECT id, status
FROM orders
WHERE status = 'PAID';

만약 전체 주문의 90%가 PAID라면 status 단독 인덱스는 별 도움이 안 될 수 있다. 대부분의 행을 읽어야 하기 때문이다. 그러나 다음처럼 목록 조회와 결합하면 의미가 달라진다.

SELECT id, status, created_at
FROM orders
WHERE status = 'PAID'
ORDER BY created_at DESC
LIMIT 50;

CREATE INDEX idx_orders_status_created
ON orders (status, created_at DESC);

낮은 선택도의 컬럼도 정렬과 LIMIT을 함께 지원하는 복합 인덱스의 선행 컬럼으로는 충분히 유용할 수 있다.

반대로 SELECT 컬럼이 인덱스에 모두 들어 있다고 해서 항상 테이블 접근이 사라지는 것도 아니다. PostgreSQL의 index-only scan은 visibility map 상태에 영향을 받고, MySQL InnoDB의 secondary index는 PK 값을 통해 clustered record 접근이 필요할 수 있다. “커버링 가능성”은 공식 문서와 실제 실행 계획으로 확인해야 한다.

실전 팁

• 동등 조건은 앞쪽에, 범위와 정렬 조건은 쿼리 패턴에 맞춰 배치한다.
• ORDER BY ... LIMIT 목록 API는 정렬까지 인덱스가 지원하는지 확인한다.
• 낮은 선택도 컬럼도 단독 인덱스와 복합 인덱스에서 의미가 다르다.
• 인덱스 스캔 여부보다 실제 읽은 행 수와 실행 시간을 본다.
• 운영 데이터의 분포가 바뀌면 같은 쿼리도 다른 계획을 선택할 수 있다.
• PostgreSQL에서는 Index Cond와 Filter를 구분해 인덱스가 실제로 처리한 조건을 본다.
• 정렬 방향이 여러 컬럼에서 섞이면 DBMS별 인덱스 스캔 지원과 실제 Sort 여부를 확인한다.

위험 신호!

• WHERE active = true 같은 낮은 선택도 단독 인덱스를 무작정 추가한다.
• 범위 조건을 복합 인덱스 앞쪽에 두고 뒤 컬럼이 모두 잘 쓰일 것이라고 기대한다.
• 정렬 조건이 있는 목록 API에서 실행 계획의 Sort 여부를 보지 않는다.
• 개발 DB의 작은 데이터로 인덱스 효과를 확정한다.
• Index Scan이라는 단어만 보고 heap/table 접근량과 filter로 버린 row 수를 보지 않는다.
• covering/index-only가 될 것이라고 기대하면서 DBMS별 조건과 visibility/clustered 구조를 확인하지 않는다.

확인 질문

• B-Tree 계열 인덱스가 동등 조건과 범위 조건에 강한 이유는 무엇인가?
  • 키가 정렬된 구조로 저장되어 특정 값이나 구간의 시작 위치를 빠르게 찾고 순서대로 읽을 수 있기 때문이다.
• 낮은 선택도 컬럼이 복합 인덱스에서 유용할 수 있는 경우는 언제인가?
  • status처럼 값 종류는 적어도 그 안에서 created_at 정렬과 LIMIT 목록 조회를 자주 수행할 때 유용할 수 있다.
• 인덱스 스캔이 느릴 수 있는 이유는 무엇인가?
  • 조건이 넓어 많은 행을 읽거나 테이블 랜덤 접근이 많아지면 전체 스캔보다 비용이 커질 수 있기 때문이다.
• 실행 계획에서 Index Cond와 Filter를 구분해야 하는 이유는 무엇인가?
  • Index Cond는 인덱스 탐색에 직접 쓰인 조건이고, Filter는 읽어온 row에 추가로 적용된 조건이므로 실제로 얼마나 많이 읽고 버렸는지 판단할 수 있기 때문이다.

참고 문서

• PostgreSQL Documentation, Index Types
• PostgreSQL Documentation, Multicolumn Indexes
• MySQL Reference Manual, B-Tree Index Characteristics