데이터베이스 인덱싱 심화 | B-트리·클러스터드·스캔/시크·커버링·운영 패턴

작성 0xmote · 2026년 8월 30일 · 14분 읽기 · 수정 2026년 10월 1일 고급 튜토리얼

이 글의 핵심

인덱스는 빠른 찾기용 부가 구조로만 배우기 쉽지만 실제 성능은 디스크 페이지 I/O, 버퍼 풀 캐시, 옵티마이저 비용 모델과 맞물려 결정됩니다. 이 글은 엔진이 인덱스를 어떻게 쓰는지 이해해 계획이 바뀌는 이유를 추적하게 돕고, 과도한 인덱스를 피하는 기준과 운영 중 인덱스를 추가할 때 주의할 점을 정리합니다.

들어가며

인덱스는 “빠른 찾기를 위한 부가 구조”로 배우기 쉽지만, 실제 성능은 디스크 페이지 단위 I/O, 버퍼 풀 캐시, 옵티마이저의 비용 모델이 함께 결정합니다. 운영 환경에서는 “인덱스를 하나 더 달았는데 왜 풀 스캔이 나오지?”, “같은 쿼리인데 버전만 올렸더니 계획이 바뀌었다” 같은 질문이 반복됩니다. 이런 질문에 답하려면 엔진이 인덱스를 어떻게 저장하고 탐색하는지에 대한 직관이 필요합니다.

이 글은 B-트리(실무에서는 대부분 B+트리)의 구조, 클러스터드 인덱스와 보조 인덱스, 스캔과 시크의 차이, 커버링 인덱스, 운영 환경의 인덱싱 패턴을 차례로 다룹니다. MySQL(InnoDB), PostgreSQL, SQL Server는 용어가 조금씩 다르므로 개념을 먼저 잡고 각 제품의 표현으로 옮겨 보는 방식으로 설명합니다.

B-트리 구조와 균형

왜 트리인가

순차 스캔은 테이블 크기에 비례해 비용이 늘어납니다. 균형 트리는 탐색 비용을 트리 높이에 묶어 O(log N)으로 만듭니다. 디스크 기반 데이터베이스에서는 키 비교 횟수보다 페이지 읽기 횟수가 병목이므로, 한 노드에 키를 최대한 많이 넣어 높이를 낮추는 것이 설계의 핵심입니다.

노드, 팬아웃, 높이

B+트리의 노드는 보통 디스크 페이지 하나에 대응합니다(InnoDB 기본 16KB, PostgreSQL 기본 8KB). 한 내부 노드가 가리킬 수 있는 자식 수를 팬아웃이라고 하며, 페이지 크기를 “키 + 자식 포인터 + 레코드 오버헤드” 크기로 나눈 값에 가깝습니다. 예를 들어 16KB 페이지에 8바이트 정수 키를 쓰면 내부 노드 하나가 대략 수백에서 천 개 정도의 자식을 가리킬 수 있습니다. 팬아웃이 1,000이라면 높이 3인 트리의 리프 수는 1,000²이고, 리프마다 수백 개의 키가 있으면 수억 건을 루트부터 세 번의 페이지 접근으로 찾을 수 있습니다. 게다가 루트와 상위 내부 노드는 거의 항상 버퍼 풀에 캐시되어 있으므로, 실제 디스크 I/O는 리프(와 경우에 따라 그 바로 위 노드) 정도입니다.

반대로 키가 길면 팬아웃이 줄어듭니다. VARCHAR(255) 같은 긴 문자열을 인덱스 앞 컬럼에 두면 같은 데이터에서도 트리가 더 높아지고 인덱스 크기도 커집니다.

B+트리의 탐색 방식

B+트리에서는 모든 키가 리프에 모여 있고, 리프끼리는 형제 포인터로 이어져 있습니다(InnoDB는 양방향 연결, PostgreSQL B-tree도 좌우 링크를 가집니다). 그래서 범위 조회는 루트에서 리프까지 한 번 내려가 시작 위치를 찾은 뒤, 리프를 옆으로 따라가며 읽습니다. 내부 노드는 어느 리프로 갈지 안내하는 라우팅 역할만 하고, 실제 키와 행(또는 행 포인터)은 리프에 있습니다. 이 구조를 알면 실행 계획의 range 접근이나 Index Scan이 “한 번 내려가고 옆으로 읽는” 동작이라는 것이 자연스럽게 이해됩니다.

삽입 순서와 페이지 분할

노드가 가득 차면 분할(split)되고, 비어 가면 병합(merge)될 수 있습니다. 균형 알고리즘을 직접 구현할 일은 거의 없지만, 키가 어떤 순서로 들어오는지는 성능에 큰 영향을 줍니다.

자동 증가 ID처럼 키가 항상 증가하는 순서로 들어오면 새 레코드는 항상 가장 오른쪽 리프에 추가됩니다. InnoDB는 이런 순차 삽입 패턴을 감지해 페이지를 거의 가득 채운 뒤 새 페이지를 시작하므로, 페이지 활용률이 높고 버퍼 풀에서 필요한 페이지가 적습니다. 반면 UUIDv4처럼 무작위 키를 클러스터드 인덱스(PK)로 쓰면, 삽입이 트리 전체에 흩어져 기존 페이지 중간에서 분할이 반복됩니다. 분할된 페이지는 절반 정도만 차 있게 되므로 같은 데이터에 더 많은 페이지가 필요하고, 쓰기마다 다른 페이지를 건드리니 버퍼 풀 적중률도 떨어집니다. 테이블이 버퍼 풀보다 커지는 시점부터 삽입 속도가 눈에 띄게 떨어지는 전형적인 원인이 이것입니다. UUID가 필요하다면 시간 순서로 증가하는 UUIDv7을 쓰거나, 내부 PK는 정수로 두고 UUID는 별도 유니크 컬럼으로 두는 방식이 흔합니다.

엔진별 저장 구조

InnoDB는 테이블 자체가 PK 기준 클러스터드 인덱스입니다. 리프 페이지에 행 전체가 저장되고, 보조 인덱스의 리프는 행 위치 대신 PK 값을 가지고 있어서 보조 인덱스로 찾은 뒤 PK로 클러스터드 인덱스를 한 번 더 탐색합니다.

PostgreSQL은 행을 힙(순서 없는 테이블 파일)에 저장하고, 모든 B-tree 인덱스는 힙 위치(TID, 페이지 번호와 페이지 내 오프셋)를 가리킵니다. PK 인덱스도 보조 인덱스와 구조가 같습니다. Index Only Scan은 visibility map으로 해당 힙 페이지의 모든 행이 모든 트랜잭션에 보이는 상태임을 확인할 수 있을 때만 힙 접근을 생략합니다.

SQL Server는 테이블마다 클러스터드 인덱스를 두거나(리프가 행 데이터) 힙으로 둘 수 있습니다. 비클러스터드 인덱스는 클러스터드 인덱스가 있으면 클러스터 키를, 힙이면 RID(행 식별자)를 가리킵니다.

클러스터드 vs 비클러스터드 인덱스

클러스터드 인덱스는 테이블의 행 데이터 자체가 인덱스 키 순서로 조직된 인덱스입니다. 행을 한 가지 순서로만 저장할 수 있으므로 테이블당 하나뿐이며, 이 설명은 SQL Server와 InnoDB에 해당합니다. 비클러스터드 인덱스(보조 인덱스)는 별도의 트리이고, 리프가 클러스터 키나 행 위치를 가리키는 간접 단계를 둡니다.

InnoDB에서의 비용 구조

InnoDB에서 PK로 조회하면 클러스터드 인덱스를 한 번 탐색해 바로 행을 얻습니다. 보조 인덱스로 조회하면 보조 인덱스에서 PK 값을 얻고, 그 PK로 클러스터드 인덱스를 다시 탐색합니다. 조건에 맞는 행이 많으면 이 두 번째 탐색이 행마다 일어나고, PK 순서와 보조 인덱스 순서가 다르므로 랜덤 I/O가 됩니다. 옵티마이저가 보조 인덱스 대신 풀 스캔을 고르는 흔한 이유가 이것입니다. 조건에 맞는 행의 비율이 일정 수준을 넘으면, 행마다 랜덤하게 클러스터드 인덱스를 찾아가는 것보다 테이블을 순차로 한 번 읽는 편이 싸기 때문입니다. MySQL의 Multi-Range Read(MRR) 최적화는 이 랜덤 접근을 PK 순서로 정렬해 완화합니다.

보조 인덱스 리프가 PK 값을 들고 있다는 사실에서 두 가지가 따라 나옵니다. 첫째, PK가 길면(예: 문자열 복합 PK) 모든 보조 인덱스가 그만큼 커집니다. 둘째, 보조 인덱스에는 PK 컬럼이 암묵적으로 포함되므로, INDEX(email)만 있어도 SELECT id FROM users WHERE email = ?는 클러스터드 인덱스를 읽지 않는 커버링 조회가 됩니다.

PK 값을 바꾸면 행이 클러스터드 인덱스에서 다른 위치로 옮겨져야 하고 모든 보조 인덱스의 해당 엔트리도 바뀌므로, 자주 변경되는 컬럼은 PK로 부적합합니다.

PostgreSQL에서의 비용 구조

PostgreSQL의 인덱스는 모두 힙 TID를 가리키므로 PK 조회도 “인덱스 탐색 + 힙 페이지 읽기”입니다. CLUSTER 명령으로 힙을 특정 인덱스 순서로 한 번 재정렬할 수 있지만, 이후 삽입과 갱신은 그 순서를 유지하지 않고, 명령 실행 중에는 테이블에 배타 잠금이 걸립니다. 그래서 운영 중인 테이블에는 잘 쓰지 않고, 필요하면 pg_repack 같은 도구로 잠금 없이 재정렬합니다. 대신 옵티마이저는 통계의 correlation 값(인덱스 순서와 힙의 물리 순서가 얼마나 일치하는지)을 비용 계산에 반영합니다.

인덱스 스캔 vs 시크(탐색)

시크에 가까운 접근

시크는 트리를 루트에서 리프까지 내려가 조건에 맞는 시작점을 찾고, 필요한 구간만 읽는 접근을 말합니다. SQL Server의 Index Seek가 이 용어의 출처입니다. MySQL EXPLAIN의 type 열로 옮기면 다음과 같습니다.

const: PK나 유니크 인덱스를 상수와 등호로 비교해 최대 한 행을 찾는 경우
eq_ref: 조인에서 앞 테이블의 각 행마다 PK나 유니크 인덱스로 정확히 한 행을 찾는 경우
ref: 유니크하지 않은 인덱스를 등호로 비교해 여러 행을 찾을 수 있는 경우
range: BETWEEN, <, IN 같은 범위 조건으로 인덱스의 일부 구간을 읽는 경우

PostgreSQL에서는 노드 이름만으로는 구분되지 않으므로, Index Scan이나 Index Only Scan 아래의 Index Cond에 어떤 조건이 들어가 트리 탐색 범위를 좁히는지를 봅니다. Filter에만 있는 조건은 읽은 뒤에 거르는 조건입니다.

스캔

스캔은 인덱스나 테이블의 넓은 구간을 처음부터 순서대로 읽는 접근입니다. 인덱스 풀 스캔(MySQL type=index)은 인덱스 리프 전체를 읽습니다. 행 전체보다 폭이 좁으므로 테이블 풀 스캔보다 읽는 양이 적을 때가 많지만, 행 수에 비례하는 비용이라는 점은 같습니다. 테이블 풀 스캔(MySQL type=ALL, PostgreSQL Seq Scan)은 인덱스 없이 클러스터드 인덱스나 힙을 모두 읽습니다.

계획을 판단하는 기준

실행 계획에서 중요한 것은 연산자 이름이 아니라 실제로 읽는 행 수, 랜덤 I/O와 순차 I/O의 비율, 읽은 뒤 버려지는 행의 비율, 조인 순서입니다. 스캔이 나왔다고 무조건 나쁜 것은 아닙니다. 조건에 맞는 행이 테이블의 상당 부분을 차지하면 옵티마이저가 인덱스 대신 순차 스캔을 고르는 것이 오히려 정상입니다. 반대로 인덱스를 탔는데 느리다면, 인덱스로 좁힌 행이 여전히 많고 그 행마다 랜덤 접근이 일어나는 경우가 대부분입니다.

커버링 인덱스 최적화

커버링 인덱스는 쿼리에 필요한 모든 컬럼을 인덱스 엔트리만으로 얻을 수 있는 인덱스입니다. 클러스터드 인덱스나 힙까지 가지 않으므로 행마다 발생하던 랜덤 I/O가 사라집니다.

MySQL(InnoDB)

EXPLAIN의 Extra에 Using index가 보이면 인덱스만으로 결과를 만들었다는 뜻입니다. Using index condition은 이름이 비슷하지만 다른 의미로, 인덱스 컬럼 조건을 스토리지 엔진 단계에서 먼저 걸렀다는 Index Condition Pushdown 표시이며 여전히 행을 읽습니다. MySQL은 INCLUDE 절을 지원하지 않으므로 커버링을 만들려면 필요한 컬럼을 복합 인덱스 키 뒤에 덧붙입니다. 앞서 설명했듯 PK 컬럼은 보조 인덱스에 자동으로 포함됩니다.

PostgreSQL

Index Only Scan은 visibility map에서 해당 힙 페이지가 all-visible로 표시된 경우에만 힙 접근을 생략합니다. 갱신이 잦아 VACUUM이 따라가지 못하는 테이블에서는 계획상 Index Only Scan이어도 힙을 많이 읽을 수 있습니다. EXPLAIN (ANALYZE, BUFFERS) 출력의 Heap Fetches 값이 실제로 힙을 읽은 횟수이며, 이 값이 크다면 VACUUM 설정(autovacuum 빈도)을 먼저 확인합니다.

INCLUDE 열

PostgreSQL 11 이상과 SQL Server는 INCLUDE 절로 키가 아닌 컬럼을 리프에만 붙일 수 있습니다. INCLUDE 컬럼은 트리 탐색이나 정렬에 쓰이지 않고 내부 노드에도 들어가지 않으므로, 키를 짧게 유지해 팬아웃을 지키면서 커버링 범위를 넓힐 수 있습니다. 유니크 인덱스에 INCLUDE 컬럼을 붙이면 유니크 제약은 키 컬럼에만 적용된다는 점도 유용합니다.

-- PostgreSQL / SQL Server 문법
-- status로 좁히고 created_at으로 범위·정렬, 자주 조회하는 비검색 컬럼은 INCLUDE
CREATE INDEX idx_orders_status_created
  ON orders (status, created_at)
  INCLUDE (user_id, total_amount);

-- MySQL에서는 키 뒤에 덧붙이는 방식으로 같은 효과
CREATE INDEX idx_orders_status_created
  ON orders (status, created_at, user_id, total_amount);

이 구성이 항상 최선은 아닙니다. 커버링 인덱스는 컬럼이 늘어날수록 크기가 커지고 해당 컬럼이 갱신될 때마다 인덱스도 갱신해야 하므로, 실행 빈도가 높은 쿼리에 한해 쓰는 것이 좋습니다.

프로덕션 인덱싱 패턴

읽기 경로부터 정의

자주 실행되는 API, 배치, 리포트 쿼리의 WHERE, JOIN, ORDER BY, GROUP BY를 먼저 목록으로 만들고, 그에 맞춰 복합 인덱스의 컬럼 순서를 정합니다. 흔히 쓰는 규칙은 “등호 조건 컬럼, 그다음 정렬 컬럼 또는 범위 조건 컬럼”입니다. B+트리에서 범위 조건 뒤에 오는 컬럼은 트리 탐색 범위를 좁히는 데 쓰이지 못하기 때문입니다. 예를 들어 (status, created_at) 인덱스는 WHERE status = 'paid' ORDER BY created_at 쿼리에서 정렬 없이 순서대로 읽을 수 있지만, (created_at, status)라면 created_at 범위를 먼저 훑으면서 status를 걸러야 합니다. 다만 등호 조건 컬럼끼리의 순서는 다른 쿼리와 인덱스를 공유할 수 있는지(왼쪽 접두사 규칙)까지 고려해서 정합니다.

부분 인덱스와 표현식 인덱스

PostgreSQL의 부분 인덱스는 WHERE 절을 붙여 조건을 만족하는 행만 인덱싱합니다. 전체 주문 중 처리 대기 상태인 주문만 자주 조회한다면 CREATE INDEX ... ON orders (created_at) WHERE status = 'pending'으로 인덱스 크기와 쓰기 비용을 크게 줄일 수 있습니다. 쿼리의 조건이 인덱스의 WHERE 조건을 논리적으로 포함해야 옵티마이저가 이 인덱스를 사용합니다.

MySQL은 부분 인덱스를 지원하지 않습니다. 8.0.13부터 지원하는 함수형(표현식) 인덱스로 LOWER(email) 같은 표현식에 인덱스를 걸 수 있고, 부분 인덱스와 비슷한 효과가 필요하면 생성 컬럼에 조건부 값(조건을 만족하지 않으면 NULL)을 넣고 그 컬럼을 인덱싱하는 우회 방법을 씁니다.

시계열·로그 테이블

시간 범위 조회가 대부분이고 데이터가 시간 순서로 쌓인다면, PostgreSQL의 BRIN 인덱스가 좋은 선택일 수 있습니다. BRIN은 블록 범위마다 최솟값과 최댓값만 저장하므로 같은 컬럼의 B-tree 인덱스보다 훨씬 작지만, 힙의 물리 순서와 값의 순서가 일치할 때만 효과가 있습니다. 시간 기준 파티셔닝을 함께 쓰면 오래된 파티션을 DROP하는 것만으로 데이터를 지울 수 있어서, 대량 DELETE로 인한 인덱스 비대화와 VACUUM 부담을 피할 수 있습니다. 인덱스만으로 해결하려 하기보다 보관 기간을 정해 데이터 양 자체를 줄이는 것이 비용에 더 큰 영향을 줄 때가 많습니다.

과도한 인덱스 방지

인덱스는 쓰기마다 유지해야 합니다. (a)와 (a, b)가 함께 있다면 (a)는 대부분 중복이므로 제거 후보입니다. 사용되지 않는 인덱스는 PostgreSQL의 pg_stat_user_indexes.idx_scan, MySQL의 sys.schema_unused_indexes 뷰로 찾을 수 있습니다. 다만 이 통계는 서버 재시작이나 통계 초기화 이후의 값이고, 월말 배치처럼 드물게 실행되는 쿼리가 쓰는 인덱스일 수도 있으므로 충분한 관찰 기간을 둡니다. MySQL 8.0의 invisible index(ALTER TABLE ... ALTER INDEX ... INVISIBLE)를 쓰면 인덱스를 지우지 않고 옵티마이저에서만 숨겨 영향을 확인한 뒤 되돌릴 수 있습니다.

통계 관리

옵티마이저는 통계로 조건에 맞는 행 수를 추정합니다. 통계가 오래되면 스키마가 그대로여도 계획이 바뀌어 갑자기 풀 스캔이 나올 수 있습니다. PostgreSQL은 autovacuum이 ANALYZE를 자동으로 실행하지만, 대량 적재 직후에는 수동으로 실행하는 편이 안전합니다. MySQL은 ANALYZE TABLE로 인덱스 통계를 갱신하고, 8.0부터는 인덱스가 없는 컬럼에 히스토그램을 만들어(ANALYZE TABLE ... UPDATE HISTOGRAM ON col) 분포가 치우친 컬럼의 행 수 추정을 개선할 수 있습니다.

운영 중 인덱스 추가

대용량 테이블에 인덱스를 추가할 때는 잠금과 리플리카 지연을 먼저 확인합니다. PostgreSQL의 일반 CREATE INDEX는 생성하는 동안 테이블 쓰기를 막으므로, 운영 중에는 CREATE INDEX CONCURRENTLY를 씁니다. 이 방식은 테이블을 두 번 스캔해 더 오래 걸리고 트랜잭션 블록 안에서 실행할 수 없으며, 실패하면 INVALID 상태의 인덱스가 남으므로 삭제 후 다시 만들어야 합니다. MySQL InnoDB는 보조 인덱스 추가를 온라인 DDL(ALGORITHM=INPLACE, LOCK=NONE)로 처리해 쓰기를 막지 않지만, 시작과 끝에 짧은 메타데이터 잠금이 필요해서 오래 실행 중인 트랜잭션이 있으면 그 뒤에 대기열이 생길 수 있습니다. 또 리플리카는 소스에서 DDL이 끝난 뒤 같은 작업을 다시 수행하므로 그동안 복제 지연이 생깁니다.

트러블슈팅 메모

인덱스를 탔는데도 느리다면, 인덱스로 좁힌 결과가 여전히 많아 행마다 랜덤 접근이 일어나거나, 조인 이후 행 수가 크게 불어나는 경우가 대부분입니다. EXPLAIN ANALYZE로 단계별 실제 행 수를 확인하면 어느 단계에서 행이 늘어나는지 보입니다.

예상 행 수와 실제 행 수가 크게 다르다면 통계가 오래되었거나, 컬럼 간 상관관계(예: 도시와 우편번호)를 옵티마이저가 독립으로 가정하고 있거나, 바인딩 값의 분포가 치우친 경우를 의심합니다. PostgreSQL에서는 CREATE STATISTICS로 컬럼 간 확장 통계를 만들 수 있습니다.

인덱스에 쓰인 컬럼에 함수를 적용하거나(WHERE DATE(created_at) = ...), 타입이 다른 값과 비교하면(문자열 컬럼을 숫자와 비교) 인덱스를 탐색에 쓰지 못합니다. 이때는 조건을 범위 비교로 바꾸거나(created_at >= '2026-01-01' AND created_at < '2026-01-02') 타입을 맞춥니다.

PostgreSQL에서 커버링을 기대했는데 힙을 읽는다면 visibility map이 갱신되지 않은 것이므로, Heap Fetches와 autovacuum 상태를 확인합니다.

같은 주제를 MySQL 실행 계획 예제와 함께 보려면 MySQL EXPLAIN 글을 참고하세요.

자주 묻는 질문 (FAQ)

Q. EXPLAIN의 Extra에 Using index가 나오지 않는데, 커버링 인덱스로 만들려면 어떻게 하나요?

Using index는 쿼리에 필요한 컬럼을 인덱스 엔트리만으로 모두 얻었을 때 표시되므로, SELECT 목록이나 WHERE, ORDER BY에 인덱스에 없는 컬럼이 하나라도 있으면 테이블 본체까지 읽게 됩니다. SELECT *를 필요한 컬럼으로 줄이고, 복합 인덱스를 WHERE와 ORDER BY에서 쓰는 컬럼 순서에 맞춘 뒤 조회 컬럼을 뒤에 덧붙이는 방식으로 구성합니다. InnoDB에서는 PK 컬럼이 보조 인덱스에 자동으로 들어 있으므로 따로 추가할 필요가 없습니다. 다만 인덱스에 컬럼을 추가할수록 쓰기 비용과 저장 공간이 늘어나므로 자주 실행되는 쿼리에만 적용하는 것이 좋습니다.