B-Tree 인덱스는 실제로 어떻게 동작하는가
균형 트리, 그런데 왜 하필 B-Tree인가
이진 트리로도 정렬된 데이터를 빠르게 찾을 수 있는데 왜 PostgreSQL은 기본 인덱스로 B-Tree를 쓸까요. 답은 디스크입니다. 이진 트리는 노드 하나에 값 하나만 담기 때문에 깊이가 깊어지고, 깊이만큼 디스크 I/O가 늘어납니다. B-Tree는 노드(페이지) 하나에 수백 개의 키를 담아 트리의 높이 자체를 낮춥니다. PostgreSQL의 인덱스 페이지 하나는 기본 8KB이고, 여기에 정렬된 키와 자식 페이지 포인터가 빼곡히 들어갑니다. 실무에서 다루는 대부분의 테이블은 인덱스 트리 깊이가 3~4단계 정도에서 끝납니다. 수백만 행이 들어 있어도 루트에서 리프까지 서너 번의 페이지 접근이면 도달한다는 뜻입니다.
리프 노드까지 가는 길
트리 구조를 그림으로 보면 이해가 빠릅니다.
flowchart TD R["루트 페이지: 50, 200"] -->|"< 50"| L1["내부 페이지: 10, 30"] R -->|"50~200"| L2["내부 페이지: 80, 150"] R -->|"> 200"| L3["내부 페이지: 300, 500"] L2 --> LF1["리프: 51,55,...,79"] L2 --> LF2["리프: 80,81,...,149"] LF1 -->|"다음 리프 포인터"| LF2
리프 페이지끼리 양방향 연결 리스트로 이어져 있다는 점이 중요합니다. id = 100 같은 등호 조건이든 id BETWEEN 80 AND 150 같은 범위 조건이든, 루트에서 시작 지점까지 내려간 다음에는 리프를 옆으로 훑으면 됩니다. 그래서 B-Tree는 등호와 범위 조건 모두에 강합니다. 반면 id % 2 = 0 같은 조건은 인덱스에 저장된 값 자체를 변형해야 판단할 수 있어서, 인덱스가 있어도 못 씁니다. 이건 인덱스의 한계가 아니라 애초에 정렬된 구조로는 풀 수 없는 질문이라서 그렇습니다.
실제로 몇 번 읽는지 확인하기
말로만 설명하면 추상적이니 직접 확인해봅시다. BUFFERS 옵션을 붙이면 몇 개의 페이지를 읽었는지 나옵니다.
CREATE INDEX idx_orders_created_at ON orders (created_at);
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE created_at = '2026-03-14';Index Scan using idx_orders_created_at on orders
(cost=0.42..8.44 rows=1 width=64) (actual time=0.031..0.033 rows=1 loops=1)
Index Cond: (created_at = '2026-03-14'::date)
Buffers: shared hit=4shared hit=4 — 딱 4개 페이지만 읽고 답을 찾았습니다. 테이블이 100만 행이어도 이 숫자는 거의 그대로입니다. 트리 깊이가 로그 스케일로 늘기 때문입니다. 이게 인덱스의 진짜 위력입니다 — 데이터가 10배 늘어도 접근 페이지 수는 거의 늘지 않습니다.
정렬 순서도 공짜로 따라온다
B-Tree 인덱스는 값을 정렬된 상태로 저장하기 때문에 ORDER BY 도 덤으로 해결해줍니다.
EXPLAIN SELECT * FROM orders ORDER BY created_at LIMIT 10;
-- Index Scan using idx_orders_created_at on orders (cost=0.42..2.51 rows=10 width=64)정렬 노드(Sort)가 계획에 아예 안 보입니다. 인덱스를 처음부터 순서대로 읽기만 하면 되니까요. 반대로 인덱스가 없는 컬럼으로 정렬하면 전체 행을 메모리(혹은 work_mem이 부족하면 디스크)에 올려 정렬해야 합니다. LIMIT 이 걸린 정렬 쿼리에서 인덱스 유무가 체감 성능에 미치는 영향이 유독 큰 이유입니다.
다만 오해하지 말아야 할 게, 이 모든 이점은 등호·범위·정렬처럼 "순서"를 활용하는 질의에서만 나옵니다. 다음 장에서 다룰 복합 인덱스는 이 순서라는 개념을 컬럼 여러 개로 확장한 것이고, 순서를 잘못 정하면 있으나 마나 한 인덱스가 됩니다.