DB 엔지니어링 — 인덱싱·B+Tree·EXPLAIN

이 글은 데이터베이스 엔지니어링 마스터 노트 시리즈의 두 번째 편입니다. 1편(ACID)에서 트랜잭션을 잡았다면, 이번엔 DB 성능의 핵심 — 인덱싱.

인덱스 없이는 DB가 매번 모든 행을 스캔. 1억 행 테이블에서 1개 찾으려고 1억 비교. 인덱스 = 책의 색인 같이 빠른 조회의 핵심.

인덱스 = 책의 색인

책 1000페이지에서 "트랜잭션" 단어 찾기
  → 색인(목차) 없이 = 1000 페이지 다 읽음
  → 색인 사용 = "ㅌ" → 트랜잭션 → 페이지 245 직행

DB 인덱스도 같음. 자주 검색하는 컬럼에 인덱스를 만들면 풀 스캔 없이 직접 조회.

Primary Index vs Secondary Index

종류	설명
Primary Index	Primary Key에 자동, 데이터 자체가 정렬
Secondary Index	추가로 만든 인덱스, PK 참조

InnoDB (MySQL)

PK 자체가 클러스터 인덱스 — 데이터 = 인덱스.

PK 인덱스 (B+Tree)
  └── leaf node가 곧 행 데이터

Secondary Index
  └── leaf node에 PK 값 저장
       → PK로 다시 한 번 조회 (back to PK)

여기서 정말 중요한 시험 함정 — InnoDB Secondary Index는 두 단계 조회입니다. 인덱스에서 PK 찾고 → PK로 데이터 찾기. PostgreSQL과 다름.

PostgreSQL

PK도 별도 B-Tree 인덱스 + 데이터는 heap에 따로 저장. 모든 인덱스가 heap의 ROWID(CTID) 가리킴.

모든 인덱스 → ROWID 저장
ROWID → heap의 행 위치

여기서 시험 함정이 하나 있어요. PostgreSQL 모든 인덱스는 ROWID 가리킴 → heap fetch 1회. InnoDB는 secondary는 PK 참조 → 두 번 조회.

B-Tree와 B+Tree

B-Tree

균형 트리. 각 노드가 키와 값(또는 데이터 포인터) 모두 저장.

       [25, 50, 75]
       /     |     \
    [10,20] [30,40] [60,70]
     키+값   키+값   키+값

문제 — 내부 노드가 데이터 포함해서 한 노드에 적은 키만 들어감. 트리 깊이 증가.

B+Tree (대부분 DBMS 사용)

내부 노드 = 키만 / leaf 노드 = 키 + 값.

       [25, 50, 75]              ← 내부: 키만
       /     |     \
    [10,20] [30,40] [60,70]      ← leaf: 키+값
       ↔       ↔       ↔
     leaf끼리 연결 (linked list)

장점 두 가지:

1. 내부 노드 키만 저장 → 한 노드에 더 많은 키 → 트리 얕음 (디스크 IO 적음)
2. Leaf 노드끼리 연결 → 범위 쿼리(WHERE x BETWEEN 10 AND 50) 빠름

여기서 정말 중요한 시험 함정 — MySQL InnoDB·PostgreSQL·SQLite 모두 B+Tree 사용. "B-Tree 사용"이라고 흔히 말하지만 실제는 B+Tree.

EXPLAIN — 쿼리 실행 계획

EXPLAIN SELECT * FROM users WHERE id = 100;

-- 출력:
-- Index Scan using users_pkey on users
--   Index Cond: (id = 100)

EXPLAIN ANALYZE SELECT * FROM users WHERE id = 100;
-- 실제 실행 + 시간 측정
-- Planning Time: 0.05ms
-- Execution Time: 0.02ms

4가지 스캔 타입 (빠름 → 느림)

스캔	설명	적합
Index Only Scan	인덱스만 사용, heap 접근 X	가장 빠름
Index Scan	인덱스 → heap	적은 행
Bitmap Heap Scan	인덱스 비트맵 → heap	중간 행
Sequential Scan	전체 테이블	많은 행

Index Only Scan 조건

쿼리가 인덱스에 있는 컬럼만 사용하면 가능.

CREATE INDEX idx_email ON users(email);

-- Index Only Scan 가능
SELECT email FROM users WHERE email = 'alice@example.com';

-- Index Scan (heap fetch 필요)
SELECT * FROM users WHERE email = 'alice@example.com';

PostgreSQL — VACUUM으로 visibility map 갱신해야 Index Only Scan 가능.

Sequential Scan이 더 빠를 때

작은 테이블 또는 결과 행이 많을 때. 옵티마이저가 자동 결정.

-- 1000행 중 800행 반환할 거면
-- 인덱스 → heap 800번 점프 vs 풀 스캔 → 풀 스캔 더 빠름

여기서 시험 함정이 하나 있어요. 인덱스 만들었다고 항상 인덱스 사용 X. 옵티마이저가 통계 기반으로 결정. 작은 테이블·많은 결과면 풀 스캔이 빠를 수 있음.

Composite Index (복합 인덱스)

여러 컬럼을 한 인덱스로.

CREATE INDEX idx_user_email_status ON users(email, status);

Leftmost Prefix 룰

-- ◯ 인덱스 사용
SELECT * FROM users WHERE email = 'a@b.com';
SELECT * FROM users WHERE email = 'a@b.com' AND status = 'active';

-- X 인덱스 사용 X (email 없음)
SELECT * FROM users WHERE status = 'active';

여기서 정말 중요한 시험 함정 — 복합 인덱스는 왼쪽부터 차례로. 첫 컬럼 빠지면 인덱스 무용지물. 컬럼 순서 = 카디널리티 높은 것 먼저.

인덱스 모범 사례

인덱스 만들 컬럼

• WHERE 절에 자주 등장
• JOIN 조건
• ORDER BY
• 카디널리티 높음 (다양한 값)

인덱스 만들면 안 되는 컬럼

• 카디널리티 낮음 (성별·status — 2~3개 값)
• 자주 UPDATE 되는 컬럼 (인덱스도 매번 갱신)
• 작은 테이블 (전체 스캔이 더 빠름)

인덱스의 비용

INSERT/UPDATE/DELETE 시 인덱스도 갱신 → 쓰기 성능 ↓
저장 공간 추가 사용

균형 — 읽기 패턴과 쓰기 패턴.

Bloom Filter

특정 키가 테이블에 없는지 빠르게 확인.

키 X가 Bloom Filter 통과 못 하면 → 100% 없음
키 X가 Bloom Filter 통과하면 → 있을 수도 (false positive)

용도 — Cassandra·HBase 같은 NoSQL이 디스크 조회 전 체크. 없는 키 검색 비용 절감.

UUID 인덱스 함정

-- AUTO_INCREMENT (순차 PK)
INSERT INTO users (id, ...) VALUES (1, ...);
INSERT INTO users (id, ...) VALUES (2, ...);
-- 새 행이 인덱스 마지막에 추가 → 빠름

-- UUID v4 (랜덤 PK)
INSERT INTO users (id, ...) VALUES ('a3f9...', ...);
INSERT INTO users (id, ...) VALUES ('e8b2...', ...);
-- 무작위 위치에 삽입 → 페이지 분할·캐시 미스 → 느림

여기서 정말 중요한 시험 함정 — UUID v4를 PK로 사용 시 InnoDB 성능 30~50% 저하 가능. UUID v7(시간 순서) 또는 ULID 권장.

동시 인덱스 생성

-- PostgreSQL
CREATE INDEX CONCURRENTLY idx_email ON users(email);

-- MySQL InnoDB Online DDL
CREATE INDEX idx_email ON users(email) ALGORITHM=INPLACE, LOCK=NONE;

테이블 락 없이 인덱스 생성. 운영 환경 필수.

수십억 행 테이블

대용량 테이블 인덱스 전략:

1. 파티셔닝 (3편)
2. 샤딩 (4편)
3. 부분 인덱스 — CREATE INDEX ... WHERE status = 'active'
4. 표현식 인덱스 — CREATE INDEX ON users(LOWER(email))

시험 직전 한 번 더 — 자주 헷갈리는 함정 모음

여기까지가 2편의 핵심입니다. 시험 직전 또는 실무에서 헷갈릴 때 다시 펼쳐 볼 수 있게 압축 노트로 마무리할게요.

• 인덱스 = 책의 색인 — 풀 스캔 없이 직접 조회
• Primary (PK 자동) vs Secondary (추가 인덱스)
• InnoDB Secondary = 두 단계 조회 (인덱스 → PK → 데이터)
• PostgreSQL 모든 인덱스 = ROWID 가리킴, heap fetch 1회
• B-Tree 모든 노드에 데이터 / B+Tree 내부 키만 + leaf만 데이터
• 대부분 DBMS = B+Tree (잘못 B-Tree로 부르기도)
• B+Tree leaf linked list = 범위 쿼리 빠름
• EXPLAIN = 실행 계획 / EXPLAIN ANALYZE = 실제 실행 + 시간
• 4 스캔 — Index Only / Index / Bitmap Heap / Sequential
• Index Only Scan = 가장 빠름, 인덱스 컬럼만 사용
• PostgreSQL VACUUM 후 Index Only 가능
• Sequential Scan이 더 빠를 때 — 작은 테이블·많은 결과
• 옵티마이저가 자동 결정 — 인덱스 만들어도 안 쓸 수 있음
• 복합 인덱스 Leftmost Prefix — 첫 컬럼 빠지면 X
• 카디널리티 높은 컬럼 먼저
• 인덱스 만들 곳 — WHERE / JOIN / ORDER BY / 카디널리티 높음
• 인덱스 비용 — INSERT/UPDATE 갱신·저장 공간
• Bloom Filter = 없는 키 빠르게 확인 (false positive 가능)
• UUID v4 PK = 성능 함정 (랜덤 위치 삽입)
• UUID v7·ULID = 시간 순서, 권장
• CONCURRENTLY (PostgreSQL) / Online DDL (MySQL) = 락 없는 생성
• 부분 인덱스 / 표현식 인덱스 = 대용량 최적화

시리즈 다른 편

• 1편 — ACID·트랜잭션
• 2편 — 인덱싱 (현재 글)
• 3편 — 파티셔닝
• 4편 — 샤딩
• 5편 — 복제
• 6편 — 동시성 제어
• 7편 — 내부 구조
• 8편 — 고급 주제

공식 문서: PostgreSQL Indexes에서 더 깊이.

다음 글(3편)에서는 파티셔닝 — 수평 vs 수직, Range·List·Hash 3종, 파티션 프루닝까지 풀어 갑니다.