EP 6.1: 밀리초 단위로 10억 행을 검색하는 방법

Source: Dev.to

The Problem: The Full Table Scan

도서관에 책이 100만 권 있다고 상상해 보세요. The Great Gatsby를 찾고 싶지만 책이 정리되지 않은 상태라면, 찾을 때까지 모든 책을 하나씩 살펴봐야 합니다. 데이터베이스 용어로 이것은 전체 테이블 스캔(선형 시간 복잡도)입니다.

데이터베이스가 수천 행에서 수백만 행으로 커지면 SELECT 쿼리는 점점 느려져 결국 타임아웃이 발생하고 애플리케이션이 크래시될 수 있습니다.

Indexes

인덱스는 컬럼의 정렬된 데이터를 실제 행을 가리키는 포인터(참조)와 함께 저장하는 별도의 데이터 구조입니다. 대부분의 관계형 데이터베이스(예: PostgreSQL, MySQL)는 B‑Tree(균형 트리) 구조를 사용합니다.

How a B‑Tree Index Works

1. Root – 검색은 최상위 노드에서 시작합니다.
2. Decision – 시스템은 노드에 있는 값과 여러분이 찾는 값(예: User ID = 505)을 비교하고 왼쪽으로 갈지 오른쪽으로 갈지 결정합니다.
3. Leaf – 트리의 가장 아래에 도달하면 디스크에 저장된 데이터의 정확한 위치를 알 수 있습니다.

이렇게 하면 검색 복잡도가 **O(n)**에서 **O(log n)**으로 바뀝니다. 100만 행을 검색하는 데도 이제는 약 20번의 “점프”만 하면 됩니다.

Analogy

인덱스를 교과서 뒤쪽에 있는 색인과 비유해 보세요:

• “Load Balancing”이라는 키워드를 찾습니다.
• 색인이 페이지 42에 있다고 알려줍니다.
• 앞의 41페이지를 읽지 않고 바로 페이지 42로 이동합니다.

Types of Indexes

Clustered Index (Primary Key)

• 테이블 자체가 물리적으로 이 순서대로 정렬됩니다.
• 테이블당 하나의 클러스터드 인덱스만 가질 수 있습니다.

Non‑Clustered Indexes

• email이나 created_at 같은 컬럼에 추가로 만드는 인덱스입니다.
• 메인 데이터와는 별도의 “폴더”에 저장되며, 클러스터드 인덱스를 가리키는 포인터를 포함합니다.

Composite Indexes

쿼리가 항상 다음과 같이 작성된다면:

WHERE country = 'India' AND city = 'Mumbai'

두 컬럼을 모두 포함하는 단일 인덱스가 데이터베이스가 두 개의 별도 인덱스를 병합하려는 경우보다 훨씬 빠릅니다.

Pro tip: 복합 인덱스에서는 컬럼 순서가 중요합니다. (city, country)에 대한 인덱스는 (country, city)와 동일하지 않습니다.

Trade‑offs

• Read vs. Write: 인덱스는 읽기(SELECT)를 빠르게 하지만 쓰기(INSERT/UPDATE/DELETE)를 느리게 합니다.
• Write Penalty: 새 행을 추가할 때마다 데이터베이스는 해당 테이블과 연결된 모든 B‑Tree에서 올바른 위치를 찾아 트리를 재균형해야 합니다.
• Storage Cost: 인덱스는 디스크 공간을 차지합니다. 대용량 테이블에서는 인덱스가 실제 데이터보다 더 클 수도 있습니다.

Practical Guidelines

• Index Foreign Keys: 외래키에 인덱스를 걸면 JOIN 작업이 크게 빨라집니다.
• Covering Queries: 인덱스에 SELECT에 필요한 모든 데이터가 포함돼 있으면(예: email을 인덱싱하고 email만 선택) 데이터베이스는 메인 테이블을 전혀 조회하지 않습니다. 이를 index‑only scan이라고 합니다.
• Avoid Low‑Cardinality Columns: gender처럼 값이 M/F/O 정도로 제한된 컬럼에 인덱스를 걸면 대부분 쓸모가 없습니다. 데이터베이스가 여전히 테이블의 큰 부분을 스캔해야 하기 때문입니다.
• Monitor with EXPLAIN ANALYZE: 인덱스를 추가하기 전에 EXPLAIN을 실행해 쿼리가 순차 스캔을 하는지, 기존 인덱스를 사용하는지 확인하세요.

Best Practices

인덱스는 데이터베이스 성능을 높이는 가장 강력한 도구이지만, 소금처럼 사용하세요: 너무 많이 쓰면 요리를 망칠 수 있습니다.

1. WHERE 절, JOIN 조건, ORDER BY 구문에 사용되는 컬럼부터 인덱싱을 시작합니다.
2. 쓰기 지연 시간을 모니터링하고 필요에 따라 조정합니다.