인덱스가 걸려있지 않을 경우 일반적인 SELECT-WHERE문을 실행하면 하나씩 순차적으로 탐색하게된다. 즉, 시간복잡도가 O(N)을 가지며 이를 full scan(table scan)이라고 부른다.
반면에 인덱스(B-tree based index)가 걸려있다면 시간복잡도는 O(logN)을 가지게되어 full scan보다 더 빠르게 찾을 수 있다.
이렇게 인덱스를 빠르게 조회하기 위해 사용할 수 있을 뿐만아니라 빠르게 정렬(order by)하거나 그룹화(group by)하기위해서도 사용할 수 있다.
인덱스 생성
CREATE INDEX {index_name} ON {table} ({attribute});두 개 이상의 attribute를 사용할 경우 다음과 같이 작성할 수 있다.
CREATE UNIQUE INDEX {index_name} ON {table} ({attr1, attr2});테이블 생성시에도 다음과 같이 인덱스를 추가해 줄 수 있다.
CREATE TABLE {table} (
id INT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
team_id INT,
number INT,
INDEX name_idx (name),
UNIQUE INDEX team_id_number_idx (team_id, number)
);이때 name_idx, team_id_number_idx를 생략해줄 수 있는데 생략하게되면 자동으로 인덱스 이름를 지정해준다. 또한 team_id, number과 같이 두 개 이상의 attribute로 구성된 인덱스를 multicolumn index 또는 composite index라고 부른다.
NOTE
PRIMARY KEY에는 인덱스가 자동 생성된다.
인덱스 조회
SHOW INDEX FROM {table};B-tree 기반의 인덱스 동작 방식
만약 attribute a에 대한 인덱스를 생성한다고 하면 다음과 같이 정렬된 상태로 생성된다.
| a | pointer |
|---|---|
| 1 | ... |
| 2 | ... |
| 3 | ... |
| 4 | ... |
| 5 | ... |
| 6 | ... |
실제로는 트리 구조로 저장되며 서브트리를 나누어 search하게된다. 그리고 attribute가 두 개 이상일 경우 다음과 같이 a를 기준으로 먼저 정렬한 후 b를 정렬하여 생성하게 된다.
| a | b | pointer |
|---|---|---|
| 1 | 78 | ... |
| 2 | 80 | ... |
| 3 | 80 | ... |
| 4 | 92 | ... |
| 5 | 95 | ... |
| 6 | 100 | ... |
쿼리가 사용하는 인덱스 확인
EXPLAIN SELECT * FROM {table} WHERE ...;NOTE
attribute {a, b}에 대한 인덱스와 {b}에 대한 인덱스가 있을 떄 어떤 인덱스를 사용할지는 optimizer라는 녀석이 알아서 선택해준다.
특정 인덱스 지정
optimizer가 인덱스를 잘못 지정하여 성능 이슈가 발생할 경우 다음과 같이 USE INDEX 또는 FORCE INDEX로 특정 인덱스를 지정할 수 있다.
SELECT * FROM {table} USE INDEX[FORCE INDEX] ({index}) WHERE ...;인덱스 생성시 주의 사항
- 테이블에 write를 할 때마다 인덱스도 변경이 발생한다.
- 추가적인 저장 공간을 차지한다.
- 불필요한 인덱스는 만들지 않도록 한다.
Covering Index
attribute {a ,b}에 대한 인덱스를 다음과 같이 생성했다고 해보자.
| a | b | pointer |
|---|---|---|
| 1 | 78 | ... |
| 2 | 80 | ... |
| 3 | 80 | ... |
| 4 | 92 | ... |
| 5 | 95 | ... |
| 6 | 100 | ... |
그리고 SELECT a, b FROM {table} WHERE a = 1; 을 수행할 때 조회하려는 attribute(a, b)가 모두 인덱스일 때 Covering Index라고 한다. 다시 말해 조회하는 attribute들을 인덱스가 모두 cover할 때의 경우를 의미한다. 따라서 조회 성능이 빠르다.
Hash Index
- Hash Table을 사용하여 인덱스를 구현한다.
- 시간복잡도 O(1)
- rehashing에 대한 부담이 있다.
- equality(==, !=) 비교만 가능하며 range는 비교가 불가능하다.
- multicolumn index의 경우 전체 attributes에 대한 조회만 가능하다. 예를 들어 {a, b}에 대한 인덱스에서 a 또는 b만으로는 조회가 불가능하다.
Full Scan이 더 좋은 경우
- 테이블에 데이터가 많지 않을 때
- 조회하려는 데이터가 테이블의 대부분을 차지할 때
NOTE
Full Scan을 할 지의 여부는 optimizer가 판단한다.