[CS] 인덱스

인덱스의 필요성

• 인덱스란 데이터를 빠르게 찾기 위한 장치
• 책의 목차/찾아보기와 같은 역할
• 테이블 전체를 스캔하는 풀 테이블 스캔(Full Scan) 없이 빠른 탐색 가능

---

B-트리

B-트리 구조

• 대부분의 인덱스는 B-트리 구조로 구성됨
• 탐색은 루트 → 브랜치 → 리프 노드 순으로 내려감

B-트리 탐색 예시

• 전체 테이블에서 57을 찾을 때:
  - 풀 스캔: 1 → 2 → ... → 57 (느림)
  - B-트리: 루트 → 브랜치 → 리프 (빠름)
  

대수 확장성 (Logarithmic Growth)

• 트리 깊이 1 증가 → 인덱스 항목 수 4배 증가
• 깊이 10이면 100만 건도 빠르게 탐색 가능

깊이	최대 항목 수
3	64
6	4,096
10	1,048,576

인덱스 종류와 생성

📌 MySQL 기준

구분	설명
클러스터형 인덱스	PRIMARY KEY 또는 UNIQUE NOT NULL 필드에 생성 (테이블당 1개)
세컨더리 인덱스	CREATE INDEX로 생성. 복합 쿼리나 검색 최적화용. 여러 개 가능

• 세컨더리 인덱스는 보조 인덱스로 다중 필드 검색 시 필요
• 단일 필드 조회만 많다면 클러스터형 인덱스만으로도 충분

📌 MongoDB 기준

• 기본 키로 ObjectID 자동 생성 (타임스탬프 + 랜덤값 + 카운터)
• 복합 인덱스 설정 가능: db.collection.createIndex({name: 1, age: -1})

---

인덱스 최적화 기법

📌 1. 인덱스는 비용이다

• 읽기 전: 인덱스 → 테이블 두 번 조회 = 오버헤드
• 쓰기 시: 컬렉션 변경 시 인덱스도 자동 재정렬 필요
• 무조건 많은 인덱스 = X 오히려 느릴 수 있음

대량 데이터는 풀스캔이 더 빠를 수 있음

📌 2. 항상 테스팅하라

• EXPLAIN 명령어로 실제 인덱스가 사용되는지 확인

// MySQL 예시
EXPLAIN SELECT * FROM t1 JOIN t2 ON t1.c1 = t2.c1;

// MongoDB 예시
db.collection.find({ age: 25 }).explain("executionStats");

📌 3. 복합 인덱스는 같음, 정렬, 다중 값, 카디널리티 순이다

권장 순서: 같음 → 정렬 → 범위 → 카디널리티

항목	설명
같음 조건	=, == 쿼리에 사용하는 필드
정렬 필드	ORDER BY, sort 대상
범위 조건	>, <, BETWEEN 등 다중 값 쿼리 대상
카디널리티	유니크 값 수가 많은 필드 우선 (예: email > gender)

---

참고: 북스터디 - 면접을 위한 CS 전공지식 노트 (Chapter 4-5)