B-tree 인덱스 | 1000PAGE

매치 로그가 수십만 행을 넘으면 특정 플레이어의 최근 전적을 찾기 위해 매번 전체 테이블을 훑는 비용이 커진다. 인덱스는 조회 경로를 줄이지만 INSERT·UPDATE·DELETE마다 별도 구조도 갱신해야 한다. 좋은 인덱스는 ‘열마다 하나’가 아니라 실제 WHERE·JOIN·ORDER BY·SELECT 목록에서 출발한다.

한 줄 정의

PostgreSQL B-tree 인덱스는 정렬된 다방향 균형 트리로 키를 관리해 동등·범위·정렬 조회의 후보 위치를 빠르게 좁히는 보조 자료구조다.

인덱스가 존재한다고 PostgreSQL이 반드시 쓰지는 않는다. 통계로 추정한 비용이 순차 스캔보다 낮을 때 선택하며, 작은 테이블이나 많은 행을 읽는 조건에서는 Seq Scan이 더 합리적일 수 있다.

실습 데이터 20만 건 만들기

DROP SCHEMA IF EXISTS index_demo CASCADE;
CREATE SCHEMA index_demo;
SET search_path TO index_demo;

CREATE TABLE players (
    player_id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    nickname text NOT NULL,
    rating integer NOT NULL,
    status text NOT NULL CHECK (status IN ('active', 'dormant', 'banned')),
    last_login_at timestamptz NOT NULL
);

CREATE TABLE match_logs (
    match_id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    player_id bigint NOT NULL REFERENCES players(player_id),
    played_at timestamptz NOT NULL,
    map_id integer NOT NULL,
    result text NOT NULL CHECK (result IN ('win', 'loss')),
    rating_delta integer NOT NULL
);

INSERT INTO players (nickname, rating, status, last_login_at)
SELECT 'Player' || g,
       800 + (g % 2200),
       CASE WHEN g % 20 = 0 THEN 'banned'
            WHEN g % 5 = 0 THEN 'dormant' ELSE 'active' END,
       timestamptz '2026-08-11 00:00+09' - (g % 365) * interval '1 day'
FROM generate_series(1, 10000) AS g;

INSERT INTO match_logs (player_id, played_at, map_id, result, rating_delta)
SELECT 1 + (g % 10000),
       timestamptz '2026-08-11 00:00+09' - g * interval '1 minute',
       1 + (g % 20),
       CASE WHEN g % 2 = 0 THEN 'win' ELSE 'loss' END,
       CASE WHEN g % 2 = 0 THEN 15 ELSE -12 END
FROM generate_series(1, 200000) AS g;

ANALYZE players;
ANALYZE match_logs;

SET search_path TO index_demo;
SELECT (SELECT COUNT(*) FROM players) AS players,
       (SELECT COUNT(*) FROM match_logs) AS match_logs;

 players | match_logs
---------+-----------
   10000 |     200000

B-tree 탐색 비용과 선택도

한 노드가 평균 $b$ 개의 다음 경로를 가지고 인덱스 항목이 $N$ 개라면 루트에서 리프까지의 높이는 개념적으로 로그 크기로 증가한다.

h \approx \lceil \log_b N \rceil

하지만 트리까지 빨리 찾아도 결과 행이 대부분이면 힙 접근 비용이 커진다. 조건에 맞는 행 수를 $M$ 이라 할 때 선택도는 다음처럼 본다. 값이 작을수록 더 선택적인 조건이다.

selectivity=\frac{M}{N},\qquad 0\le selectivity\le1

아래 그래프는 데이터 규모를 $x$ (천 행 단위)로 놓은 교육용 개념 모델이다. 순차 탐색을 $0.2x$ , B-tree 탐색을 $\ln(x+1)$ 로 단순화했다. 실제 PostgreSQL 비용 공식이나 실행시간 예측이 아니며 캐시, 페이지 수, 선택도, 상관도, 힙 접근 비용을 생략했다.

데이터 규모에 따른 탐색 비용의 개념 모델

단일 열 인덱스: 한 가지 선택적 조건

높은 레이팅 구간을 자주 조회한다면 rating 단일 인덱스가 범위 조건과 내림차순 정렬을 지원할 수 있다. B-tree는 =, <, <=, >=, >와 범위, 정렬에 적합하다.

SET search_path TO index_demo;
CREATE INDEX idx_players_rating ON players (rating DESC);
ANALYZE players;

EXPLAIN (ANALYZE, BUFFERS)
SELECT player_id, nickname, rating
FROM players
WHERE rating >= 2980
ORDER BY rating DESC
LIMIT 10;

Limit
  ->  Index Scan using idx_players_rating on players
        Index Cond: (rating >= 2980)
Planning Time: ...
Execution Time: ...

계획의 비용·시간·버퍼 수는 PostgreSQL 버전, 하드웨어, 캐시 상태와 통계 표본에 따라 달라지므로 생략했다. 핵심 확인점은 Index Scan과 Index Cond다. 결과가 넓어지면 같은 인덱스가 있어도 Seq Scan으로 바뀔 수 있다.

복합 인덱스와 선두 열

플레이어별 최근 전적 쿼리에는 (player_id, played_at DESC)가 자연스럽다. B-tree 복합 인덱스는 선두 열의 동등 조건과 그 다음 열의 범위·정렬 조건이 있을 때 스캔 범위를 가장 효과적으로 줄인다.

SET search_path TO index_demo;
CREATE INDEX idx_match_player_played
ON match_logs (player_id, played_at DESC);
ANALYZE match_logs;

EXPLAIN (ANALYZE, BUFFERS)
SELECT match_id, played_at, result
FROM match_logs
WHERE player_id = 42
  AND played_at >= timestamptz '2026-07-01 00:00+09'
ORDER BY played_at DESC
LIMIT 20;

played_at만 조건에 둔 조회도 이 인덱스를 사용할 가능성은 있지만 선두 player_id가 빠져 일반적으로 덜 효율적이다. PostgreSQL 18의 B-tree skip scan이 특정 통계에서 도움을 줄 수 있으므로 ‘절대 사용 불가’라고 단정하지 말고 EXPLAIN으로 확인한다. 전역 시간 범위 조회가 중요하면 played_at 단일 인덱스를 별도로 검토한다.

부분 인덱스: 중요한 일부 행만 저장

운영 화면이 활성 플레이어만 검색한다면 전체 상태를 인덱싱하지 않고 active 행만 저장할 수 있다. 인덱스가 작아지고 해당 행의 쓰기만 유지하면 된다. 다만 쿼리의 WHERE 조건이 인덱스 조건을 논리적으로 함의한다고 플래너가 인식해야 한다.

SET search_path TO index_demo;
CREATE INDEX idx_players_active_last_login
ON players (last_login_at DESC)
WHERE status = 'active';

EXPLAIN (ANALYZE, BUFFERS)
SELECT player_id, nickname, last_login_at
FROM players
WHERE status = 'active'
  AND last_login_at >= timestamptz '2026-08-01 00:00+09'
ORDER BY last_login_at DESC;

표현식 인덱스: 검색식 자체를 키로

대소문자를 무시한 닉네임 검색에서 WHERE lower(nickname) = lower($1)를 반복한다면 lower(nickname) 값을 인덱싱한다. 표현식이 쿼리와 맞아야 하며, 원본 nickname을 그대로 비교하는 조건을 위한 인덱스와는 다르다.

SET search_path TO index_demo;
CREATE INDEX idx_players_lower_nickname
ON players ((lower(nickname)));

EXPLAIN (ANALYZE, BUFFERS)
SELECT player_id, nickname
FROM players
WHERE lower(nickname) = 'player4242';

 player_id |  nickname
-----------+------------
      4242 | Player4242

커버링 인덱스: INCLUDE로 조회 열 싣기

검색과 정렬에 쓰는 열은 키로 두고, 결과에만 필요한 열은 INCLUDE payload로 넣을 수 있다. 다음 인덱스는 플레이어별 최근 전적 카드에 필요한 값을 모두 담는다. 조건이 맞고 힙 페이지의 all-visible 비트가 충분하면 Index Only Scan이 가능하지만, 갱신이 잦은 최신 로그에서는 가시성 확인 때문에 힙을 방문할 수 있다.

SET search_path TO index_demo;
DROP INDEX idx_match_player_played;
CREATE INDEX idx_match_player_played_cover
ON match_logs (player_id, played_at DESC)
INCLUDE (result, rating_delta, map_id);

VACUUM (ANALYZE) match_logs;

EXPLAIN (ANALYZE, BUFFERS)
SELECT played_at, result, rating_delta, map_id
FROM match_logs
WHERE player_id = 42
ORDER BY played_at DESC
LIMIT 20;

Limit
  ->  Index Only Scan using idx_match_player_played_cover on match_logs
        Index Cond: (player_id = 42)
        Heap Fetches: 0
Planning Time: ...
Execution Time: ...

Heap Fetches: 0은 이 정적 실습 직후 VACUUM 상태에서 기대하는 대표 결과다. 실제 운영에서는 동시 변경과 가시성 맵 상태에 따라 0보다 클 수 있다. 넓은 text·jsonb payload를 무작정 INCLUDE하면 인덱스가 커지고 삽입이 실패할 만큼 인덱스 튜플이 커질 수도 있다.

쓰기 비용: 인덱스는 공짜 복사본이 아니다

행을 INSERT하면 관련된 각 인덱스에도 항목을 추가한다. 인덱스 키를 바꾸는 UPDATE와 DELETE도 새 버전·정리 비용, WAL, 캐시 사용량을 늘린다. 인덱스가 $k$ 개일 때 쓰기 비용을 단순히 일정 배수라고 단정할 수는 없지만, 유지해야 할 구조가 늘수록 비용과 저장 공간이 증가한다.

C_{write} \approx C_{heap}+\sum_{i=1}^{k}C_{index_i}

이는 비용 구성요소를 설명하는 개념식이지 PostgreSQL 플래너의 공식이 아니다. 실제로는 pg_stat_user_indexes의 idx_scan, pg_relation_size·pg_indexes_size, 쓰기 지연과 WAL 양을 함께 측정하고 사용하지 않는 중복 인덱스를 정리한다.

EXPLAIN을 읽는 최소 기준

ANALYZE를 먼저 실행해 실제 분포 통계를 갱신한다. 작은 장난감 데이터만으로 운영 인덱스를 결정하지 않는다.
Index Cond는 인덱스 탐색 범위를 줄인 조건이고 Filter는 후보를 읽은 뒤 제거한 조건이다.
예상 rows와 actual rows 차이가 크면 통계·상관관계·데이터 치우침을 조사한다.
BUFFERS로 캐시 적중과 실제 읽기 블록을 보고 한 번의 따뜻한 캐시 실행시간만 비교하지 않는다.
쓰기 문장에 EXPLAIN ANALYZE를 쓰면 실제 변경된다. BEGIN 안에서 측정한 뒤 ROLLBACK한다.

인덱스 선택 체크리스트

느린 실제 쿼리와 호출 빈도, 반환 행 수를 확보한다.
동등 조건을 복합 B-tree 앞쪽에, 그다음 범위·정렬 열을 배치하고 반대 방향 쿼리도 점검한다.
일부 상태만 반복 조회하면 부분 인덱스, 함수 결과로 찾으면 표현식 인덱스를 검토한다.
읽기 전용에 가까운 조회에서만 필요한 좁은 열을 INCLUDE 후보로 삼는다.
EXPLAIN (ANALYZE, BUFFERS)와 운영 통계로 읽기 이득이 쓰기·공간 비용보다 큰지 확인한다.

참고 자료

PostgreSQL 18 공식 문서 — 인덱스 장과 B-tree (2026-08-11 확인)
PostgreSQL 18 공식 문서 — 복합 인덱스와 선두 열·skip scan (2026-08-11 확인)
PostgreSQL 18 공식 문서 — 부분·표현식 인덱스와 CREATE INDEX (2026-08-11 확인)
PostgreSQL 18 공식 문서 — Index Only Scan과 커버링 인덱스 (2026-08-11 확인)
PostgreSQL 18 공식 문서 — EXPLAIN과 인덱스 사용 점검 (2026-08-11 확인)

댓글을 불러오는 중…