Ch.11 유사 사례와 키워드 정리

< 인덱스의 원리

---

앞에서 Binary Search, B-Tree, 인덱스의 원리, 그리고 인덱스가 안 타게 만드는 안티패턴을 확인했다. 같은 원리가 적용되는 유사 사례를 보고 키워드를 정리한다.

11-6. 유사 사례

사례 1: 정렬을 매번 하는 랭킹 API

유저 랭킹을 보여주는 API에서 매 요청마다 SELECT * FROM scores ORDER BY score DESC LIMIT 10을 실행한다. score 컬럼에 인덱스가 없으면 매번 Full Table Scan + 전체 정렬이 일어난다.

해결: CREATE INDEX idx_scores_score ON scores(score DESC) 한 줄이면 된다.

(실무에서는 랭킹처럼 갱신 빈도 대비 조회 빈도가 높은 데이터는 Redis Sorted Set을 쓰기도 한다. Sorted Set 내부는 Skip List 기반인데, Skip List도 정렬된 자료구조에서 O(log n) 검색을 제공한다는 점에서 B+Tree와 사촌이다. Ch.17에서 다룬다.)

사례 2: 로그 검색에서 날짜 범위 쿼리

SELECT * FROM logs WHERE created_at BETWEEN '2024-01-01' AND '2024-01-31'이 느리다. created_at에 인덱스가 없으면 수백만 건의 로그를 전부 스캔한다. B+Tree 인덱스가 있으면 해당 범위의 시작점을 O(log_b n)으로 찾고, 리프 노드를 순회하면 된다.

날짜 컬럼에 함수를 씌우는 실수가 많다.

-- 안 탐: DATE() 함수 때문에 인덱스 무효
SELECT * FROM logs WHERE DATE(created_at) = '2024-01-15';

-- 탐: 함수를 값 쪽으로
SELECT * FROM logs WHERE created_at >= '2024-01-15' AND created_at < '2024-01-16';

사례 3: 페이지네이션과 OFFSET 문제

흔한 페이지네이션 코드다.

-- 100페이지 = OFFSET 1980
SELECT * FROM products ORDER BY created_at DESC LIMIT 20 OFFSET 1980;

OFFSET N은 "앞에서 N개 건너뛰기"인데, 건너뛴다고 안 읽는 게 아니다. DB는 정렬된 1980개를 다 만들고 나서 버린다. 페이지 번호가 커질수록 점점 느려지는 이유다.

해결: Cursor-based Pagination (Keyset Pagination)을 쓴다.

-- 마지막으로 본 created_at 값을 커서로 사용
SELECT * FROM products
WHERE created_at < '2024-05-16 12:00:00'  -- 이전 페이지 마지막 값
ORDER BY created_at DESC
LIMIT 20;

이 방식은 인덱스를 타고 바로 시작 지점으로 점프한다. 페이지 번호와 상관없이 항상 같은 속도다. (created_at에 인덱스가 있어야 함.)

graph LR
    subgraph "OFFSET 방식"
        A1[1페이지] -->|"OFFSET 20"| A2[2페이지]
        A2 -->|"OFFSET 40"| A3[3페이지]
        A3 -.->|"OFFSET 1980<br/>1980개 다 읽고 버림"| A100[100페이지]
    end
    subgraph "Cursor 방식"
        B1[1페이지] -->|"WHERE id < cursor"| B2[2페이지]
        B2 -->|"WHERE id < cursor"| B3[3페이지]
        B3 -.->|"항상 같은 속도"| B100[100페이지]
    end

GitHub API, Slack API, Twitter API 등 대규모 API는 전부 Cursor 방식이다. OFFSET이 운영 가능한 규모가 아니라서다.

(Cursor 방식의 단점도 있다. "5페이지로 점프" 같은 임의 페이지 이동이 안 된다. 무한 스크롤이나 "다음 페이지" 형태의 UI에 맞다. 페이지 번호 UI가 진짜 필요한지부터 점검해야 한다.)

사례 4: 검색 + 정렬 + 필터 조합

상품 검색 페이지의 흔한 쿼리.

SELECT * FROM products
WHERE category_id = 5
  AND status = 'AVAILABLE'
  AND price BETWEEN 10000 AND 50000
ORDER BY created_at DESC
LIMIT 20;

조건이 네 개다: category_id, status, price 범위, ORDER BY created_at. 어떤 인덱스를 걸어야 할까?

원칙은 "등치 조건 → 범위 조건 → 정렬 컬럼" 순으로 복합 인덱스를 구성한다.

-- 권장: 등치(category_id, status) → 범위(price) 순으로
CREATE INDEX idx_products_search ON products(category_id, status, price);

-- ORDER BY까지 인덱스로 풀고 싶다면
CREATE INDEX idx_products_search_sort
  ON products(category_id, status, created_at);
-- 단, price 범위는 인덱스를 못 타고 필터로만 적용됨

복합 인덱스는 "가장 왼쪽 컬럼부터 순서대로 써야" 효과가 있다(Leftmost Prefix Rule). 그래서 어떤 컬럼을 앞에 둘지가 인덱스 설계의 핵심이다.

(이 부분은 Ch.14에서 자세히 다룬다. 지금은 "단일 인덱스만 거는 게 아니라 쿼리 패턴에 맞춘 복합 인덱스가 따로 필요하다"는 점만 짚는다.)

사례 5: 통계/분석 쿼리에서 정렬과 GROUP BY

-- 일별 매출 집계
SELECT DATE(created_at), SUM(amount)
FROM orders
GROUP BY DATE(created_at)
ORDER BY DATE(created_at);

GROUP BY는 내부적으로 정렬을 수반한다. 그룹화하려면 같은 값끼리 모아야 하고, 그러려면 정렬이 필요하다(또는 Hash 기반 그룹화).

여기서 두 가지 문제가 겹친다.

1. DATE(created_at)이 함수라서 created_at 인덱스를 못 탄다.
2. 그룹화 결과를 다시 정렬한다.

해결:

-- DATE 컬럼을 미리 만들거나(생성 컬럼), 범위 조건으로 바꾼다
CREATE INDEX idx_orders_created ON orders(created_at);
SELECT
  DATE_TRUNC('day', created_at) AS day,
  SUM(amount)
FROM orders
WHERE created_at >= NOW() - INTERVAL '30 days'  -- 범위 좁히기 먼저
GROUP BY day
ORDER BY day;

집계 쿼리는 데이터를 좁히는 게 우선이다. 인덱스로 좁히고 → 좁힌 결과만 GROUP BY 한다. 전체 테이블 집계가 일상이면 OLTP DB로는 한계가 있고, OLAP DB(BigQuery, ClickHouse, Redshift)나 Materialized View가 답이다.

(OLTP는 짧고 빈번한 트랜잭션에 최적화된 DB, OLAP은 대량 집계 분석에 최적화된 DB다. MySQL/PostgreSQL은 OLTP, BigQuery/ClickHouse는 OLAP다. Ch.16에서 이 구분을 더 다룬다.)

사례 6: Python에서 bisect로 정렬된 리스트 검색

정렬된 리스트에서 값을 찾을 때 in 연산자를 쓰면 O(n)이다. bisect를 쓰면 O(log n)이다.

import bisect

sorted_prices = sorted(all_prices)  # 한 번만 정렬

# 나쁜 코드: O(n)
if target_price in sorted_prices:
    pass

# 좋은 코드: O(log n)
idx = bisect.bisect_left(sorted_prices, target_price)
if idx < len(sorted_prices) and sorted_prices[idx] == target_price:
    pass

# 진짜 잘 쓰는 코드: 범위 검색
left = bisect.bisect_left(sorted_prices, 100)
right = bisect.bisect_right(sorted_prices, 200)
count_in_range = right - left  # 100~200 사이 상품 개수, O(log n)

"있느냐 없느냐"만 확인할 거면 Set이 더 낫다. bisect는 "위치를 알아야 할 때"나 "범위 검색"이 필요할 때 쓴다. 메모리 내 자료구조에서 인덱스 효과를 흉내내고 싶을 때 유용한 도구다.

11-7. 면접 Q&A (이 챕터로 답할 수 있는 단골 질문)

Binary Search의 전제 조건이 뭔가요?

두 가지다. 첫째, 데이터가 정렬되어 있어야 한다. 정렬돼 있어야 "중간값과 비교해서 왼쪽 또는 오른쪽으로 간다"는 결정이 의미를 갖는다. 둘째, 랜덤 접근이 O(1)이어야 한다. 연결 리스트처럼 i번째 접근에 O(n)이 드는 자료구조에 Binary Search를 적용하면 전체 시간이 O(n)으로 퇴화한다. 배열이나 디스크 페이지처럼 인덱싱 가능한 자료구조여야 한다.

DB는 왜 Hash Index 대신 B-Tree Index를 기본으로 쓰나요?

Hash Index는 "같은 값 찾기"에는 O(1)이지만 범위 검색을 못 한다. 실무 쿼리에서 BETWEEN, >, <, ORDER BY 같은 범위·정렬 연산은 흔하다. B+Tree는 O(log_b n)이긴 해도 정렬된 상태를 유지하고 리프 노드가 연결 리스트로 이어져 있어서 범위 검색이 효율적이다. 그래서 RDBMS의 기본 인덱스는 B+Tree다. PostgreSQL은 옵션으로 Hash Index도 제공하지만, 실무에서 쓰는 경우는 드물다.

B-Tree와 B+Tree의 차이가 뭔가요?

B-Tree는 모든 노드(루트, 중간, 리프)에 데이터를 저장한다. B+Tree는 리프 노드에만 데이터를 저장하고, 리프 노드끼리 연결 리스트로 이어져 있다. 그래서 B+Tree는 범위 검색에서 리프의 시작 지점을 찾은 뒤 연결 리스트를 따라가기만 하면 된다. 중간 노드는 키만 저장하니까 한 노드에 더 많은 키가 들어가서 트리 깊이가 얕다. MySQL InnoDB, PostgreSQL 모두 B+Tree를 쓴다.

인덱스를 많이 걸면 항상 좋은가요?

아니다. 인덱스는 디스크 공간을 추가로 쓰고, INSERT/UPDATE/DELETE 시에 인덱스도 함께 갱신해야 한다. 읽기는 빨라지지만 쓰기는 느려진다. 자주 검색하는 컬럼에만 전략적으로 거는 게 원칙이다. 특히 쓰기 부하가 많은 테이블(로그 적재 등)에 인덱스가 5~10개 붙어 있으면 INSERT TPS가 절반 이하로 떨어진다. "모든 컬럼에 인덱스를 걸면 빠르겠지"는 흔한 오해다.

쿼리가 인덱스를 타는지 어떻게 확인하나요?

EXPLAIN 명령을 쓴다. MySQL이라면 type 컬럼이 핵심이다. type: ALL이면 Full Table Scan, type: ref나 type: range면 인덱스를 타는 것이고, const나 eq_ref면 최선이다. 좋은 순서대로 const, eq_ref, ref, range, index, ALL이다. ALL이 나오면 인덱스 설계를 점검해야 한다. PostgreSQL에서는 EXPLAIN ANALYZE로 실제 실행 시간과 함께 본다.

인덱스를 걸었는데 안 타요. 왜 그런가요?

네 가지 안티패턴부터 의심한다. (1) 컬럼에 함수를 씌웠는가 (LOWER(name), DATE(created_at)). (2) 암묵적 형변환이 일어나는가 (INT 컬럼을 문자열로 비교). (3) 부정 조건인가 (!=, NOT IN). (4) LIKE의 앞쪽 와일드카드인가 ('%xxx%'). 그게 다 아니면 컬럼의 카디널리티가 낮아서(예: 성별) 옵티마이저가 일부러 Full Scan을 선택했을 수 있다. 통계 정보가 오래된 경우(ANALYZE 안 돌린 경우)도 있다.

ORDER BY price LIMIT 20이 인덱스가 있으면 왜 빠른가요?

인덱스가 이미 정렬된 B+Tree이기 때문이다. 전체 데이터를 정렬할 필요 없이, 인덱스 리프 노드의 앞에서 20개만 추출하면 된다. 시간 복잡도가 O(n log n) 정렬에서 O(log_b n + k)로 떨어진다. 이걸 Top-N Sort 최적화라고 한다. price 컬럼에 인덱스가 없으면 DB는 어쩔 수 없이 전체를 정렬하고 앞 20개를 자른다.

정렬된 리스트에서 검색할 거면 Set과 bisect 중 뭘 써야 하나요?

"있느냐 없느냐"만 보면 Set이 O(1)이라 더 빠르다. bisect를 쓰는 경우는 "삽입 위치를 알아야 할 때"나 "범위 검색"이 필요할 때다. 예를 들어 정렬된 가격 리스트에서 특정 가격 이하 상품이 몇 개인지 세거나, 일정 구간 내 값들을 잘라내야 할 때 bisect가 적합하다. DB로 치면 Hash Index와 B-Tree Index의 차이와 같다.

Cursor-based Pagination이 왜 OFFSET보다 빠른가요?

OFFSET은 "앞의 N개를 건너뛴다"인데, 건너뛴다고 안 읽는 게 아니다. DB는 정렬된 N개를 다 만들고 버린다. 100페이지면 1,980개를 만들고 1,960개를 버린다. Cursor 방식은 "마지막으로 본 값보다 작은(또는 큰) 것부터"라는 WHERE 조건으로 인덱스를 타고 바로 시작 지점으로 점프한다. 페이지 번호와 상관없이 항상 일정한 속도다. 대규모 API(GitHub, Slack 등)는 전부 이 방식이다.

복합 인덱스의 컬럼 순서가 왜 중요한가요?

B+Tree는 "가장 왼쪽 컬럼부터 정렬"되어 있다(Leftmost Prefix Rule). INDEX(a, b, c)라면 a로 먼저 정렬, 같은 a 안에서 b로 정렬, 같은 (a,b) 안에서 c로 정렬이다. 그래서 WHERE a=1, WHERE a=1 AND b=2는 인덱스를 타지만 WHERE b=2만으로는 못 탄다. 등치 조건을 먼저, 범위 조건을 나중에 두는 게 원칙이다. Ch.14에서 자세히 다룬다.

오늘의 키워드 정리

새 키워드

Binary Search (이진 탐색)

정렬된 데이터에서 절반씩 범위를 줄여가며 찾는 O(log n) 탐색 알고리즘이다. 전제 조건은 데이터가 정렬되어 있어야 한다는 것과 랜덤 접근이 O(1)이어야 한다는 것. Python에서는 bisect 모듈이 이 기능을 제공한다. DB의 B-Tree 인덱스가 이 원리를 디스크에 최적화한 것이다.

B-Tree / B+Tree

디스크 기반 저장소에 최적화된 균형 트리 자료구조다. 하나의 노드에 여러 키를 저장해서 디스크 I/O 횟수를 줄인다. 대부분의 RDBMS가 인덱스 자료구조로 B+Tree를 사용한다. B+Tree는 리프 노드끼리 연결 리스트로 연결되어 범위 검색이 효율적이다. 시간 복잡도 O(log_b n)이고, b가 커질수록 트리가 얕아져 I/O가 줄어든다. Ch.14에서 실무 인덱스 설계를 다룬다.

Index (인덱스)

DB에서 검색 성능을 높이기 위해 특정 컬럼의 값을 별도의 자료구조(주로 B+Tree)로 정리해둔 것이다. 책의 색인과 같은 역할이다. 읽기는 빨라지지만 쓰기(INSERT/UPDATE/DELETE) 성능은 떨어진다. EXPLAIN 명령으로 인덱스 사용 여부를 확인할 수 있다. 잘못 쓴 쿼리(함수 적용, 형변환, 부정 조건, LIKE 앞쪽 와일드카드)는 인덱스를 못 탄다.

Covering Index (커버링 인덱스)

쿼리가 필요로 하는 모든 컬럼이 포함되어 있어서 테이블 본체를 읽지 않고 인덱스만으로 답할 수 있는 인덱스다. 디스크 I/O를 한 단계 줄여서 빠르다. EXPLAIN의 Extra에 Using index로 표시된다. 인덱스 크기가 커지는 단점이 있어서 핵심 쿼리에만 적용한다.

Cardinality (카디널리티, 선택도)

컬럼이 가질 수 있는 고유한 값의 다양성이다. 이메일이나 유저 ID처럼 거의 모든 행이 다른 값이면 카디널리티가 높고, 성별이나 boolean처럼 두세 가지 값만 있으면 낮다. 카디널리티가 높을수록 인덱스 효과가 크다. 옵티마이저는 통계 정보로 카디널리티를 추정해서 인덱스 사용 여부를 결정한다.

Full Table Scan (풀 테이블 스캔)

테이블의 모든 행을 처음부터 끝까지 읽는 것이다. 인덱스가 없거나 인덱스를 탈 수 없는 쿼리에서 발생한다. 데이터 양에 비례해서 느려지는 O(n) 연산이다. EXPLAIN에서 type: ALL로 나타나면 Full Table Scan이다.

Top-N Sort

전체 정렬을 하지 않고 상위 N개만 뽑는 최적화 기법이다. 크기 N짜리 힙을 유지하면서 한 번 스캔하면 된다. 시간 복잡도가 O(n log n)에서 O(n log k)로 떨어진다. Python의 heapq.nsmallest/nlargest, DB의 ORDER BY ... LIMIT N이 이 최적화를 적용한다.

Tim Sort (팀 정렬)

Python과 Java가 사용하는 하이브리드 정렬 알고리즘이다. Merge Sort + Insertion Sort를 결합했고, 실제 데이터에서 흔한 "거의 정렬된" 패턴에 최적화되어 있다. 평균/최악 O(n log n), 최선 O(n)이다.

EXPLAIN

DB에서 쿼리 실행 계획(Query Execution Plan)을 보여주는 명령어다. 쿼리가 인덱스를 타는지, Full Table Scan을 하는지, 어떤 순서로 테이블을 조인하는지 등을 확인할 수 있다. MySQL의 type 컬럼은 좋은 순서대로 const, eq_ref, ref, range, index, ALL이다. PostgreSQL에서는 EXPLAIN ANALYZE로 실측 시간까지 확인한다. 성능 문제를 진단하는 첫 번째 도구다. Ch.14에서 EXPLAIN 결과 해석을 자세히 다룬다.

Cursor-based Pagination (커서 기반 페이지네이션)

OFFSET 대신 "마지막으로 본 값"을 커서로 사용하는 페이지네이션 방식이다. WHERE 조건으로 인덱스를 타고 바로 시작 지점으로 점프하므로, 페이지 번호와 상관없이 항상 일정한 속도를 낸다. Keyset Pagination이라고도 한다. GitHub, Slack, Twitter 등 대규모 API의 기본 방식이다. 단점은 임의의 페이지 번호로 점프할 수 없다는 것.

인덱스 안티패턴

인덱스가 있어도 쿼리 작성 방식 때문에 안 타게 되는 패턴들. 대표 네 가지: (1) 컬럼에 함수를 씌움 (LOWER(name), DATE(created_at)), (2) 암묵적 형변환, (3) 부정 조건 (!=, NOT IN), (4) LIKE의 앞쪽 와일드카드 ('%xxx%'). 운영 장애의 단골 원인이라 첫 번째 의심 대상이다.

재등장 키워드

키워드	최초 등장	이번 챕터에서의 역할
Time Complexity	Ch.8	O(n log n) vs O(log n) vs O(log_b n) 비교
Linear Search	Ch.10	Full Table Scan = Linear Search
Hash Table	Ch.10	Hash Table과 B+Tree의 용도 차이
디스크 I/O	Ch.2	B-Tree 깊이 = I/O 횟수

키워드 연관 관계

graph TD
    subgraph "정렬"
        TS["Tim Sort<br/>O(n log n)"]
        TN["Top-N Sort<br/>O(n log k)"]
        TS --> TN
    end

    subgraph "검색"
        LS["Linear Search<br/>O(n)<br/>(Ch.10)"]
        BS["Binary Search<br/>O(log n)"]
        HT["Hash Table<br/>O(1)<br/>(Ch.10)"]
    end

    subgraph "DB 인덱스"
        BT["B-Tree / B+Tree<br/>O(log_b n)"]
        IDX["Index"]
        CI["Covering Index"]
        FTS["Full Table Scan"]
        EXP["EXPLAIN"]
        AP["인덱스 안티패턴"]
        CARD["Cardinality"]
        CUR["Cursor Pagination"]
    end

    BS --> BT
    BT --> IDX
    IDX --> CI
    IDX --> EXP
    IDX --> AP
    IDX --> CARD
    IDX --> CUR

    LS --> FTS
    HT -->|"같은 값 찾기"| IDX
    BS -->|"범위 검색"| IDX

    TS -.->|"인덱스 있으면<br/>정렬 불필요"| IDX
    TN -.->|"LIMIT N 최적화"| IDX

    IDX -.->|"Ch.14"| ADV["복합 인덱스<br/>인덱스 설계"]

여기까지의 지도 (누적)

위의 "키워드 연관 관계"가 이번 챕터 안의 연결이라면, 아래는 Ch.1부터 지금까지 도메인별로 쌓인 키워드다. 빈 레인은 앞으로 그 챕터에서 채워진다 — 다 채워지는 과정이 곧 이 강의의 지도다. (이번 챕터에서 추가된 키워드는 굵게.)

도메인	누적 키워드 (등장 챕터)
OS·실행	System Call·Kernel·Mode Switch·Buffer·File Descriptor(2) → CPU/IO Bound·GIL·Event Loop·async/await·Thread/Process Pool·Context Switch·IPC(3) → Process·Thread·PCB/TCB·Memory Layout·Virtual Memory·Page·TLB·OOM(4)
동시성·트랜잭션	Race Condition·Critical Section·Mutex/Lock·Deadlock·Semaphore·Starvation(5)
자료구조·알고리즘	Hash Table·Time/Space Complexity·Linear Search·Load Factor(10) → Binary Search·B-Tree/B+Tree·Index·Full Table Scan·Tim Sort·EXPLAIN(11)
DB·캐시·튜닝	— (Ch.13에서 시작)
네트워크·분산	TCP/IP·Socket·3/4-Way Handshake·Connection Pool·Keep-Alive·TIME_WAIT(6)
설계·AI·품질·보안	Computational Thinking·CS 키워드(1) → LLM·Token·Context Window·Hallucination·Prompt Engineering(7) → 키워드 사전·DNS·Load Balancing·Circuit Breaker·CQRS(8) → Code Review·YAGNI·Cache Stampede(9)

다음 챕터(Ch.12)에서는 트리와 그래프를 다룬다. B+Tree는 "디스크를 위한 트리"였다면, Ch.12의 트리/그래프는 "계층 데이터와 의존성"을 위한 자료구조다. 같은 트리라도 풀려는 문제가 다르면 모양도 다르다.

---

< 인덱스의 원리