Index란?
원본 테이블로부터 특정 컬럼을 복사하여
정렬된 구조로 관리하는 보조 자료구조이다.
개념적으로는 “검색을 빠르게 하기 위해 만들어진 정렬된 참조 구조”이며,
DB는 이를 통해 전체 테이블을 순차 탐색하지 않고도 원하는 데이터를 찾을 수 있다.
Index가 필요한 이유
위와 같은 테이블에서 row 수가 매우 많을 경우,
WHERE age = 25Index가 필요한 이유
조건을 만족하는 row를 찾기 위해
모든 row를 순차적으로 조회해야 하는 경우를 Full Scan이라 한다.
이 방식은 데이터가 적을 때는 문제가 없지만,
row 수가 많아질수록 탐색 시간이 급격히 증가한다.
Index는 특정 컬럼(예: age)을 기준으로
별도의 구조를 생성하고 값을 정렬해 둠으로써
age = 25와 같은 조건을 빠르게 찾을 수 있도록 한다.
Index가 빠른 이유
정렬된 데이터 구조에서는 이진 탐색이 가능하다.
- 값의 크고 작음을 기준으로 탐색
- 탐색 범위를 매 단계마다 절반씩 축소
결과적으로 시간 복잡도는 다음과 같다.
- Full Scan:
O(N) - Index 탐색:
O(log N)
실제 DB에서의 데이터 구조
DB는 데이터를 단순히 배열 형태로 정렬 저장하지 않는다.
- 삽입, 삭제, 수정이 빈번함
- 물리적으로 데이터를 재정렬하는 비용이 매우 큼
따라서 DB는 트리(Tree) 구조를 사용하여
데이터의 대소관계만 유지하는 방식으로 관리한다.
B-Tree
- 하나의 노드에 여러 개의 key 저장
- 한 단계에서 여러 범위를 동시에 제거 가능
- 단순 이진 트리보다 트리 높이가 낮음
이를 통해 탐색 시
1/2이 아닌 더 큰 비율로 탐색 대상을 줄일 수 있음
B+Tree
- 실제 데이터는 Leaf Node에만 저장
- 내부 노드는 탐색을 위한 가이드 역할
- Leaf Node들이 Linked List로 연결
장점:
- 탐색 효율 증가
- 범위 검색(Range Query)에 매우 유리
Index 사용 순서
- Index(B+Tree)에서 조건에 맞는 key 탐색
- 해당 key가 가리키는 원본 테이블의 row 위치 조회
- 실제 row 데이터 반환
Index의 단점
- 저장 공간 증가
원본 테이블 외에 인덱스 구조를 추가로 저장해야 함 - 쓰기 성능 저하
INSERT / UPDATE / DELETE 시
원본 테이블과 인덱스를 모두 갱신해야 함
PK와 Index
Primary Key
- 자동으로 Index 생성
- 대부분의 DB(InnoDB 기준)에서 Clustered Index
PK를 기반으로 테이블 자체가 정렬된 구조가 되므로
추가적인 정렬 작업이 필요하지 않다.
Clustered Index란?
- 테이블의 실제 행(row)이 인덱스 키 순서대로 저장되는 인덱스
- 인덱스 자체가 데이터
- 테이블당 하나만 존재
- 일반적으로 PK가 Clustered Index 역할을 수행
