CS학습2026.10.056 min read

Index: 정렬된 보조 구조로 조회를 O(log N)으로 줄이는 B-Tree 인덱스

인덱스(Index)는 테이블의 특정 컬럼 값을 정렬된 구조로 따로 저장해 전체 스캔 없이 행을 찾게 해주는 보조 자료구조다. PostgreSQL의 기본 인덱스인 B-Tree는 등호·범위 조회와 정렬에서 O(log N) 탐색을 제공한다. 대신 쓰기 비용과 저장 공간이 늘어나므로 조회 패턴에 맞춰 설계해야 한다. 이 글은 동작 원리, EXPLAIN 확인법, 복

By 송민성

1. 개념

인덱스(Index)는 테이블의 하나 이상의 컬럼 값을 기준으로 정렬해 저장하고, 각 값이 가리키는 행의 물리적 위치(PostgreSQL에서는 ctid)를 함께 보관하는 보조 자료구조다. 책 뒤의 색인과 같은 역할이다. 원본 데이터(힙, heap)는 그대로 두고, 검색용 경로만 별도로 만든다.

PostgreSQL이 제공하는 주요 인덱스 종류는 다음과 같다.

종류	용도
B-Tree	기본값. 등호, 범위, 정렬
Hash	등호 비교 전용
GIN	배열, JSONB, 전문 검색 같은 다중 값 컬럼
GiST	지리 정보, 범위 타입 등
BRIN	물리적 순서와 상관관계가 높은 대용량 테이블

이 글은 가장 널리 쓰이는 B-Tree를 중심으로 설명한다.

2. 왜 사용하는가

인덱스가 없으면 WHERE email = 'a@b.com' 같은 조회도 테이블의 모든 행을 읽는 순차 스캔(Sequential Scan)으로 처리된다. 행이 N개면 O(N)이다. 인덱스가 있으면 트리를 따라 내려가 O(log N)으로 대상을 찾는다.

인덱스가 도움이 되는 연산은 다음과 같다.

WHERE 조건의 등호·범위 검색
JOIN 조건 컬럼 탐색
ORDER BY, MIN/MAX: 이미 정렬된 상태라 별도 정렬을 생략할 수 있다.
UNIQUE 제약의 중복 검사

3. 동작 원리

B-Tree는 균형 잡힌 다진 트리다. 노드 하나가 디스크 페이지(PostgreSQL 기본 8KB) 하나에 대응하며, 한 노드에 수백 개의 키가 들어간다. 그래서 트리 높이가 매우 낮게 유지된다. 수백만~수억 건 규모에서도 보통 3~4단계 정도다.

구조는 세 층으로 나뉜다.

루트(root) 노드: 탐색의 시작점
내부(internal) 노드: 키 범위에 따라 자식 노드로 분기
리프(leaf) 노드: 키와 힙 튜플 위치(ctid)를 보관하며, 서로 연결되어 있어 범위 스캔이 쉽다.

탐색 과정은 다음과 같다.

루트에서 시작해 키 비교로 알맞은 자식을 고른다.
리프까지 내려간다.
리프에서 ctid를 얻어 힙에서 실제 행을 읽는다.

범위 조회(BETWEEN)는 시작 키를 찾은 뒤 리프 노드의 연결을 따라 순서대로 읽는다.

삽입 시에는 해당 리프에 키를 넣고, 페이지가 가득 차면 페이지 분할(page split)이 일어난다. 이 비용이 쓰기 부담으로 이어진다.

복합 인덱스(composite index) (a, b)는 a로 먼저 정렬하고, a가 같은 것끼리 b로 정렬한다. 그래서 선두 컬럼(leftmost column) a 조건이 있어야 효율적으로 쓰인다.

4. 코드 예제

PostgreSQL에서 실행해 볼 수 있는 예제다. 100만 건을 만들고 인덱스 전후의 실행 계획을 비교한다.

sql

-- 1) 테스트 테이블과 데이터 생성
DROP TABLE IF EXISTS users;
CREATE TABLE users (
    id         bigserial PRIMARY KEY,
    email      text NOT NULL,
    country    text NOT NULL,
    created_at timestamptz NOT NULL
);

INSERT INTO users (email, country, created_at)
SELECT
    'user' || g || '@example.com',
    (ARRAY['KR','US','JP','DE','FR'])[1 + (g % 5)],
    now() - (g || ' seconds')::interval
FROM generate_series(1, 1000000) AS g;

ANALYZE users;

-- 2) 인덱스 없이 조회: Seq Scan
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM users WHERE email = 'user500000@example.com';

-- 3) B-Tree 인덱스 생성 후 재조회: Index Scan
CREATE INDEX idx_users_email ON users (email);

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM users WHERE email = 'user500000@example.com';

-- 4) 복합 인덱스: 선두 컬럼 순서의 영향
CREATE INDEX idx_users_country_created ON users (country, created_at);

-- 인덱스를 효율적으로 사용 (선두 컬럼 country 사용)
EXPLAIN SELECT * FROM users
WHERE country = 'KR' AND created_at >= now() - interval '1 day';

-- 선두 컬럼 없이 created_at만 조회: 이 복합 인덱스는 비효율적
EXPLAIN SELECT * FROM users
WHERE created_at >= now() - interval '1 day';

-- 5) 부분 인덱스와 커버링 인덱스
CREATE INDEX idx_users_kr_recent ON users (created_at) WHERE country = 'KR';
CREATE INDEX idx_users_email_cover ON users (email) INCLUDE (country);

-- 6) 인덱스 크기와 사용 통계 확인
SELECT indexrelname, pg_size_pretty(pg_relation_size(indexrelid)) AS size, idx_scan
FROM pg_stat_user_indexes
WHERE relname = 'users';

2번 쿼리는 Seq Scan, 3번 쿼리는 Index Scan 또는 Index Only Scan이 나오는 것이 일반적이다. 실제 계획과 시간은 환경과 통계에 따라 달라진다.

5. 시간 복잡도 또는 성능 특성

연산	인덱스 없음	B-Tree 인덱스
등호 조회	O(N)	O(log N)
범위 조회	O(N)	O(log N + K) (K는 결과 행 수)
삽입/수정/삭제	테이블만 갱신	테이블 + 인덱스 갱신(인덱스당 O(log N))

인덱스 조회는 힙 접근이 추가로 필요하다. 결과 행이 많아 테이블의 큰 비율을 읽게 되면 무작위 접근(random access) 비용 때문에 순차 스캔이 더 빠를 수 있고, 옵티마이저는 이를 비용 기반으로 판단해 선택한다.
인덱스 온리 스캔(Index Only Scan)은 필요한 컬럼이 모두 인덱스에 있고, 가시성 맵(visibility map)상 해당 페이지가 모두 보이는 상태일 때 힙 접근을 생략한다. VACUUM이 가시성 맵을 갱신한다.
인덱스는 디스크 공간을 차지하고 메모리 캐시(shared buffers, OS 캐시)도 소비한다.

6. 실무 사용 사례

기본키(PRIMARY KEY)와 UNIQUE 제약: PostgreSQL이 자동으로 B-Tree 인덱스를 만든다.
외래키(foreign key) 컬럼: PostgreSQL은 참조하는 쪽에 인덱스를 자동 생성하지 않는다. 조인이나 부모 행 삭제 시 성능을 위해 직접 만드는 경우가 많다.
목록 페이징: ORDER BY created_at DESC LIMIT 20 같은 쿼리는 created_at 인덱스로 정렬 비용을 없앨 수 있다.
소프트 삭제 테이블: WHERE deleted_at IS NULL 조건의 부분 인덱스로 크기와 갱신 비용을 줄인다.
JSONB 검색: GIN 인덱스를 사용한다.
운영 중 생성: CREATE INDEX CONCURRENTLY를 쓰면 쓰기를 오래 막지 않고 만들 수 있다. 단, 트랜잭션 블록 안에서는 실행할 수 없고 시간이 더 걸린다.

7. 주의할 점

쓰기 비용: 인덱스가 많을수록 INSERT/UPDATE/DELETE가 느려진다. 사용되지 않는 인덱스는 pg_stat_user_indexes의 idx_scan으로 찾아 정리한다.
선두 컬럼 규칙: (a, b) 인덱스는 WHERE b = ...만으로는 효율적으로 쓰이지 않는다. 등호 조건 컬럼을 앞에, 범위 조건 컬럼을 뒤에 두는 것이 일반적인 원칙이다.
인덱스 컬럼 가공: WHERE lower(email) = ...처럼 컬럼에 함수를 적용하면 일반 인덱스를 쓰지 못한다. 이때는 표현식 인덱스 CREATE INDEX ON users (lower(email))를 만든다.
앞쪽 와일드카드: LIKE '%abc'는 B-Tree를 활용하지 못한다. 접두어 검색 LIKE 'abc%'는 로케일 설정에 따라 text_pattern_ops 같은 연산자 클래스가 필요할 수 있다.
암묵적 형변환: 컬럼과 비교 값의 타입이 달라 캐스팅이 일어나면 인덱스를 못 쓸 수 있다.
낮은 선택도(selectivity): 값의 종류가 적은 컬럼(예: 성별)에 단독 인덱스를 걸면 효과가 작다.
통계 정보: 오래된 통계는 잘못된 실행 계획을 만든다. ANALYZE와 autovacuum 상태를 확인한다.
비대화(bloat): 잦은 갱신·삭제로 인덱스가 부풀 수 있으며, 필요하면 REINDEX(CONCURRENTLY 옵션 지원)를 고려한다.
판단은 추측이 아니라 EXPLAIN (ANALYZE, BUFFERS) 결과로 한다.

8. 핵심 정리

인덱스는 정렬된 보조 구조로, B-Tree 기준 등호·범위 조회를 O(log N)에 처리한다.
B-Tree는 높이가 낮고 리프가 연결되어 있어 범위 스캔과 정렬에 유리하다.
인덱스는 조회를 빠르게 하는 대신 쓰기 비용, 저장 공간, 캐시 사용량을 늘린다.
복합 인덱스는 컬럼 순서가 핵심이며 선두 컬럼 조건이 있어야 효율적이다.
컬럼 가공, 앞쪽 와일드카드, 형변환은 인덱스 사용을 막는다.
옵티마이저가 순차 스캔을 택할 수도 있으므로 EXPLAIN (ANALYZE, BUFFERS)로 실제 계획을 검증한다.