[SQL] 3. 인덱스(Index)란?

인덱스(Index)란?

책에서 특정 단어를 찾을 때, 페이지를 처음부터 끝까지 넘기면 상당히 오래 걸린다. 하지만 책 뒤에 있는 인덱스를 보면 해당 단어가 있는 페이지 번호(위치)를 바로 알 수 있다.

데이터베이스에서도 마찬가지로 테이블이 커질수록 WHERE/ ORDER BY/ JOIN 작업은 테이블 풀스캔( O(N) )이면 I/O 지옥으로 지연과 락이 많아질 수 있다. 이 때 인덱스를 사용하면 원하는 데이터의 위치를 먼저 찾아서 빠르게 접근할 수 있게 된다.

인덱스를 사용하면 정렬된 데이터 구조(대부분 B+Tree), 빠른 주소록(해시)을 사용해 O(logN) 또는 평균 O(1)에 가까운 탐색 속도를 제공할 수 있다. 인덱스를 통해 데이터 베이스 조회 시 읽기 경로 단축 + 불필요한 페이지 접근 제거 + 정렬/조인 비용 감소를 기대할 수 있게 된다.

---

B-Tree 와 B+Tree

MySQL의 인덱스는 B+Tree 구조로 되어있다.

• MySQL(InnoDB)의 클러스터형 인덱스 = PK 기반 B+Tree
• MySQL의 비클러스터형 인덱스 = B+Tree 기반 + PK Lookup

그렇기 때문에 MySQL의 인덱스를 제대로 이해하려면 B+Tree 구조를 이해하는 것이 중요하다.

Binary Tree

Binary Search Tree

바이너리 트리는 각 노드가 최대 2개의 자식을 가지는 트리 구조이다. 

자식 수가 2개로 제한되어 있어 노드 개수가 많아지면 높이가 커진다. 그래서 디스크/메모리 접근 관점에서 페이지 효율이 낮다.

DB에서는 한 번 디스크를 읽을 때 페이지 단위로 읽기 때문에, 자식 수를 늘려서 한 번의 접근에 더 많은 키를 담는 B-Tree 계열을 사용하게 되었다. 이 글은 DB 정리 글이므로 트리에 대한 자세한 내용은 추후 다시 정리해봐야 겠다.

B-Tree

바이너리 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리구조이다.

각 노드가 여러 개의 키와 여러 자식 포인터를 가지며, 모든 리프의 깊이가 같다.

노드 하나가 디스크 1페이지에 딱 들어가게 설계되어 한 번의 I/O로 많은 키를 검사할 수 있다. 그래서 트리 높이가 매우 낮아 I/O 횟수가 적어 대용량에서도 빠르다.

B+Tree

 

현대 DB 인덱스의 표준. B-Tree를 범위 조회/ 순차 스캔에 최적화한 형태이다.

B-Tree와 다르게 내부 노드는 키와 자식 포인터만 보관하고 실제 데이터는 없다. 그래서 한 페이지에 더 많은 키를 담을 수 있다.

실제 데이터는 리프에만 저장되고, 리프끼리 연결 리스트로 연결되어 첫 리프만 찾으면 옆으로 진행하며 BETWEEN, ORDER BY, LIMIT 명령에 탁월하다. 내부를 타고 리프 첫 칸에 도달하면 끝 키까지 연결되어 쭉 가져올 수 있는 것이다.

(루트, 내부노드)
  [ 30 | 60 ]                 ← 내부 노드는 “분기용 키”만
   /         \
 (..)<30     (>=30)
             /        \
          [30~59]   [60~89]   ← 내부/리프는 모두 '페이지' 단위
            |           |
   ┌────(리프)────┐  ┌────(리프)────┐
   | 30, 31, ... |->| 60, 61, ... |->  ...  ← 리프는 '키'들이 정렬 + 옆 리프 포인터
   └─────────────┘  └─────────────┘

요약하자면 루트에서 시작해서 키 값을 비교하면서 어느 자식으로 갈지 결정 (이진 탐색처럼)하고 리프 노드에 도착하면 정확히 일치하는 키를 찾거나 범위의 시작 위치를 찾고 리프노드 들은 연결 리스트로 이어져있으니, 한 번 찾으면 오른쪽으로 계속 이동하면서 빠르게 읽어냄.

(미리 말하면 보조 인덱스 리프에는 물리 포인터가 아니라 PK 값이 저장됨, 항상 PK 탐색으로 행을 찾음)

---

클러스터형 vs 비클러스터형 인덱스

HEAP TABLE(힙 테이블)

우선 인덱스를 알기 전 *Heap Table (힙테이블) 에 대해 알아보자.

힙테이블은 인덱스가 전혀 없는 테이블의 저장 방식이며, 데이터는 순서를 지정하지 않고 힙에 저장된다. 힙으로 저장된 테이블에 하나 이상의 비클러스터형 인덱스를 만들 수 있다. 쿼리 결과에서 데이터 순서를 예측할 수 없고, 힙에서 반환된 행의 순서를 보장하려면 ORDER BY 절을 사용해야한다. 행을 저장하기 위한 영구 논리 순서를 지정하려면 테이블이 힙이 아니도록 테이블에 클러스터형 인덱스를 만들어야 한다. 힙 테이블에 클러스터형 인덱스를 생성하면 데이터 페이지 자체가 B-Tree 정렬구조로 재배치 된다.

하지만 MySQL(InnoDB)에서는 항상 클러스터형 인덱스를 사용하는데, 만약 사용자가 기본키(PK)를 지정하지 않더라도 UNIQUE NOT NULL 인덱스가 있으면 그것을 클러스터형 인덱스로 사용하고, 그마저도 없다면 숨겨진 6바이트 Row ID를 자동 생성하여 클러스터형 인덱스로 구성한다.

 

MySQL은 설계 철학과 성능 안정성 추구 때문에 처음부터 B+Tree 기반의 클러스터형 인덱스 구조를 기본 저장 방식으로 삼았다.

 

PK 기반 랜덤 접근 최적화

• 대부분의 트랜잭션성 서비스(은행, 쇼핑몰, SNS)는 PK(기본키)로 단일 행 조회를 많이 한다.
• PK가 곧 데이터 저장 순서이므로, 인덱스 탐색 후 바로 데이터 페이지에 접근할 수 있어 효율적이다.

범위 검색 성능 보장

• PK 순서대로 정렬된 상태이므로 BETWEEN, ORDER BY, LIMIT 같은 범위 조회가 빠르다.
• Heap Table처럼 무작위 저장 시 범위 검색은 비효율적(풀스캔)이다.

데이터 무결성 관리 용이

• 클러스터 인덱스 구조는 항상 유일한 키를 갖기 때문에 중복 데이터를 제어하기 쉽다.
• InnoDB는 MVCC(다중 버전 동시성 제어)도 PK 기반으로 작동하므로, PK 없는 구조는 설계상 불편하다.

InnoDB(MySQL)에서 클러스터형 인덱스는 기본키(PK) 순서로 실제 행 데이터를 리프 페이지에 저장하는 인덱스이다.
보조인덱스(비클러스터형) 인덱스의 리프는 행 주소 대신에 PK 값을 담고, 최종 행은 PK를 따라 찾아가는 구조이다.

 

 

클러스터형 인덱스 (Clustered Index)

테이블 자체를 인덱스 구조 (B-Tree)로 변환한 형태이다. 테이블의 물리적 저장 순서가 클러스터형 인덱스의 키 순서와 동일하다.

데이터 페이지 자체가 B-Tree의 리프(Leaf)인 것이다. 그래서 테이블이 곧 클러스터형 인덱스로 볼 수 있다.

그래서 보조 인덱스 없이 PK만 있는 테이블이라면, 별도의 인덱스 저장 구조는 없다. 테이블 자체가 클러스터형 인덱스이기 때문이다.

클러스터 인덱스 키: user_id

B-Tree 구조:
  Root
    ├── Page1 (user_id: 1~100)
    ├── Page2 (user_id: 101~200)
    ├── Page3 (user_id: 201~300)
리프 페이지 = 실제 데이터 페이지

MySQL InnoDB에서는 PK가 클러스터형 인덱스이다.

 

장점

• 정렬이 되어 있어서 범위 검색이 빠르고, PK 검색이 매우 빠르다.

단점

• 데이터의 물리 순서가 고정되어서, 키 변경 시 페이지 분할(Page Split)이 발생해 성능이 저하될 수 있다.
• 삽입이 키 순서에 맞지 않으면 성능이 떨어질 수 있다.

주의

• PK가 길면 모든 보조 인덱스 리프에도 긴 PK가 저장되므로 이는 인덱스와 쓰기에 비용이 높아진다.  그래서 PK는 짧고 단조롭게 증가하는 값에 사용하는 것이 좋다.(BIGINT AUTO_INCREMENT, 또는 UUIDv7 계열)

 

비클러스터형 인덱스 (Non-Clustered Index)

데이터 페이지와 별도로 인덱스 페이지를 구성한다. 인덱스의 리프 페이지에는 데이터 자체가 아니라 데이터의 위치(포인터)가 들어 있다.

MySQL (InnoDB)의 경우 클러스터형 인덱스의 PK 값이 포함된다.

[Non-Clustered Index on name]

B-Tree:
  Root
    ├── "Alice" → PK=101
    ├── "Bob"   → PK=305
    ├── "Eve"   → PK=502

→ PK를 이용해 클러스터형 인덱스에서 실제 데이터 페이지 찾아감

MySQL InnoDB에서는 PK 외 모든 인덱스는 보조 인덱스(비클러스터형)이다.

장점

• 특정 컬럼 기반 검색이 빠름 (email, status, created_at 와 같이 자주 검색 되는 컬럼에 주로 사용)
• 여러 개 만들 수 있음 (다양한 조회 최적화 가능)

단점

• 인덱스 검색 후 한 번 더 데이터 페이지를 찾아가는 과정(Bookmark Lookup) 필요 → 랜덤 I/O 증가
• 인덱스 유지 비용 발생 (INSERT/UPDATE/DELETE 시 인덱스도 수정)
  • 너무 많이 만들면 DML(쓰기) 성능이 급격히 하락하므로, 자주 쓰는 컬럼 위주로만 만드는 것이 좋다.
• 읽기 성능은 향상되지만, 쓰기 (INSERT/UPDATE/DELETE) 는 느려짐

---

인덱스 구조

B+Tree 인덱스

• 구조: 트리 형태, 리프 노드가 정렬된 상태로 연결
• 탐색 과정: 루트 → 중간노드 → 리프 → (비클러스터형이면) PK 따라 테이블 접근
• 장점: 범위 검색, 정렬, MIN/MAX, ORDER BY 최적화 가능

Hash 인덱스

• 구조: 키를 해시 함수로 변환 → 버킷에 저장
• 장점: 동등 비교(=) 매우 빠름
• 단점: 정렬/범위 검색 불가
• MySQL InnoDB는 해시 인덱스를 직접 만들 수는 없고, 내부적으로 Adaptive Hash를 사용

커버링 인덱스

쿼리에 필요한 모든 컬럼이 인덱스에 들어있어 테이블로 되돌아가지 않는 케이스

• 정의: 쿼리에 필요한 모든 컬럼이 인덱스에 포함된 경우 → 테이블 접근 생략
• 장점: Back to Table 제거 → 디스크 I/O 감소 → 응답속도 향상
• 주의점
  • 형태가 따로 있다기 보다는 B+Tree 인덱스가 어떤 쿼리를 전부 커버할 때 부르는 상태 또는 효과를 나타내는 느낌이다.
  • 컬럼을 많이 넣을 수록 인덱스 폭이 커져서 DML 비용이 높아진다.
  • 핵심 API나 화면 단과 같이 정말 자주 쓰는 조회 경로에만 설계하는 것이 좋다.
• MySQL EXPLAIN: Extra: Using index

인덱스 종류별 구조와 특징 정리

인덱스 종류	구조	특징	실무 사용 예
B+Tree 인덱스	정렬된 트리 구조, 리프끼리 연결	범위 검색 / 정렬 / ORDER BY / LIMIT 최적	MySQL, PostgreSQL 기본 인덱스
Hash 인덱스	해시 테이블 (Key→버킷 매핑)	= 비교 빠름, 정렬/범위 불가	InnoDB 내부 Adaptive Hash Index 자동 사용
커버링 인덱스	쿼리에 필요한 모든 컬럼이 인덱스 리프에 포함	Back to Table 불필요 → 디스크 I/O 제거	SELECT id, email FROM user WHERE email='x'
Fulltext 인덱스	단어 단위 토큰화 + 역색인	LIKE '%단어%' 효율적, 자연어 검색	검색 서비스 / 블로그 검색
Spatial (R-Tree)	좌표 기반 트리	위치·지도 데이터	GIS, 위치기반 앱

복합 인덱스와 컬럼 순서

• (A, B, C) 인덱스는 A만 또는 A,B 또는 A,B,C 조건에서 사용 가능
• 순서 설계 원칙
  1. WHERE에서 동등 조건인 컬럼을 앞에 둔다
  2. 그 다음 범위 조건 컬럼
  3. ORDER BY 컬럼까지 고려
• 잘못된 예시
  • 인덱스 (D, A)인데 WHERE A=10 → 인덱스 사용 안 함
  • B만, B+C만, C만은 기본적으로 불가 (왼쪽이 비었기 때문)
• 인덱스가 사용되지 않는 경우
  • 조건에 함수/연산 적용: WHERE DATE(created_at) = '2025-08-15'
  • 데이터 타입 불일치: INT vs '문자열'
  • 앞 와일드카드: LIKE '%abc'
  • 복합 인덱스의 첫 컬럼 미사용
  • 범위 조건 뒤의 컬럼 사용
  • 카디널리티 낮은 조건
  • ORDER BY 방향과 인덱스 순서 불일치

// 1. 함수, 연산 적용
-- ❌ 인덱스 사용 안 됨
WHERE DATE(created_at) = '2025-08-15';

// 해결 방법
WHERE created_at >= '2025-08-15 00:00:00'
  AND created_at <  '2025-08-16 00:00:00';
  
// 2. 데이터 타입 불일치
-- ❌ 인덱스 사용 안 될 수 있음
WHERE user_id = '100';   -- user_id는 INT

// 3. 앞 와일드 카드
-- ❌ 인덱스 사용 불가
WHERE name LIKE '%kim';
// 해결
WHERE name LIKE 'kim%';   -- 접두어만 지정하면 인덱스 사용 가능

// 4. 복합 인덱스 첫 컬럼 미사용
INDEX (A, B)
-- ❌ 인덱스 사용 안 됨
WHERE B = 10;

// 5. 범위 조건 뒤의 컬럼 사용
INDEX (A, B, C)
-- ❌ C 인덱스 미사용
WHERE A = 10 AND B > 5 AND C = 'x';

// B에서 **범위 조건(BETWEEN, >, <, LIKE 'abc%')**이 나오면
// 그 뒤의 컬럼(C)은 인덱스 정렬 연속성이 끊어져 사용 불가.
// C 조건은 필터링만 수행.
// 쿼리 패턴이 이런 경우라면 (A,B) 인덱스 따로 두고
// C 조건은 필터로만 처리하거나 쿼리 재설계.

// 6. 카디널리티(고유도) 낮은 조건
-- ❌ 인덱스가 있어도 사용 안 됨 (풀스캔이 더 효율적)
WHERE gender = 'M';     -- M/F 두 값뿐

// 전체 행 중 절반 이상을 읽어야 하면
// 인덱스를 타는 것보다 테이블 전체를 한 번에 읽는 게 더 빠름.

// 7. ORDER BY 방향, 순서 불일치
INDEX (created_at ASC, id ASC)
-- ❌ 정렬에 인덱스 사용 불가
ORDER BY created_at DESC, id ASC;
// 인덱스는 오름차순으로 정렬되어 있는데
// ORDER BY가 **혼합 방향(ASC/DESC 불일치)**이면
// 인덱스 순서 그대로 정렬을 활용할 수 없다

---

선택도(Selectivity)와 카디널리티(Cardinality)

• 카디널리티: 컬럼의 서로 다른 값(고유값) 개수 (NDV: number of distinct values)
  • 높은 카디널리티: 값이 거의 다 다름 → 인덱스 효율 높음
  • 낮은 카디널리티: 값이 반복 → 인덱스 효율 낮음
  • 옵티마이저는 통계에서 NDV와 값 분포를 보고 인덱스 사용 여부 결정
• 선택도(Selectivity): 전체 중 조건을 만족하는 비율 → 인덱스가 효율적이려면 선택도가 충분히 낮아야 함
  
  • 선택도 = 매칭 행 수 / 전체 행 수
  • 카디널리티가 높으면 선택도 낮아질 확률 ↑ (잘 걸러냄)
  • ex:
    • email (100만건 중 99만개가 서로 다름) → 높은 카디널리티 → 조건 검색 효율↑
    • gender (M/F) → 낮은 카디널리티 → 조건 검색 효율↓ (풀스캔이 나을 수 있음)
  • ex: gender='M' (50%) → 인덱스 효율 낮음
    email='abc@x.com' (0.0001%) → 효율 높음
• 통계 정보가 정확해야 옵티마이저가 올바른 계획을 선택
  • MySQL: ANALYZE TABLE

---

인덱스의 부정적 영향

인덱스는 “읽기”를 빠르게 해주는 대신 “쓰기”를 비싸게 만든다.

• INSERT: 각 인덱스 B+Tree에 노드 삽입/재균형 → 페이지 분할 가능
• UPDATE: 인덱스 키에 포함된 컬럼 변경 시 해당 인덱스 삭제+재삽입
• DELETE: 인덱스에도 삭제 마킹/청소 비용
• 로그 증가: Redo/Undo, 복제 트래픽, 체크포인트 압박
• 랜덤 키 삽입: 페이지 분할/단편화↑ (특히 UUIDv4)
• 인덱스 많을수록 모든 DML 비용이 선형 증가

그래서 쓰기가 많은 테이블은 최소로 필요한 인덱스만 유지하거나, 대량으로 적재해야할 때는 인덱스를 최소화하고, 적재 후에 인덱스 생성을 하는 편이 좋을 수 있다.

 

인덱스가 항상 좋은 것 만은 아닌 이유

• 낮은 선택도 조건(예: status IN ('A','B') 60% 매칭)은 풀스캔이 더 이득일 수 있음
• 작은 테이블: 인덱스 오버헤드가 이득을 상쇄
• 잘못된 순서/설계: 옵티마이저가 “있으니 써보려다” 오히려 느려지는 경우
• 통계 부정확: 잘못된 실행 계획 유도 → 성능 악화
• 메모리/스토리지 압박: 인덱스가 버퍼/디스크를 잡아먹음
• 유지보수 복잡성: 마이그레이션/릴리즈 때마다 부하·락 가능

읽기 패턴이 분명하고 자주 쓰이는 곳에 정확한 인덱스를 부여하는 것이 중요하다.