인덱스란
어느 특정 테이블에 조건을 걸어 데이터를 조회하는 경우 모든 로우에 조건을 대입하는 full scan(=table scan)방식으로 찾아야 하고, 이러한 경우에 시간복잡도는 O(N)이다.
하미만 그 조건 컬럼에 인덱스가 걸려있고, 그 인덱스가 B-tree 기반의 인덱스라면 시간복잡도는 O(log N)이 된다.
인덱스를 쓰는 이유
- 특정 조건을 만족하는 튜플을 빠르게 조회할 수 있다.
- 튜플을 빠르게 정렬하거나 그룹핑할 수 있다.
인덱스를 적용 및 확인
생성되어 있는 테이블에 적용
| id | name | team_id | backnumber |
|---|---|---|---|
| - | - | - | - |
SELECT * FROM PLAYER WHERE name = 'Tom';
SELECT * FROM PLAYER WHERE team_id = 105 and backnumber = 7;
//인덱스 값이 중복 가능
CREATE INDEX player_name_idx ON PLAYER (name);
//인덱스 값이 중복 불가능
CREATE UNIQUE INDEX team_id_backnumber_idx ON PLAYER (team_id, backnumber);생성하는 테이블에 적용
CREATE TABLE PLAYER(
id INT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
team_id INT,
backnumber INT,
//인덱스 값이 중복 가능
INDEX player_name_idx (name),
UNIQUE INDEX team_id_backnumber_idx (team_id, backnumber)
);- 인덱스 생성에서 team_id, backnumber 처럼 두 개 이상의 에트리뷰트로 구성되어지는 인덱스를 multicolumn(composite) index 라고 말한다.
- PRIMARY KEY는 기본적으로 인덱스가 생성되어져 있다.
- 생성 단계에서는 Alias 생략이 가능하다.(player_name_idx, team_id_backnumber_idx)
테이블에 적용되어져 있는 인덱스 확인
SHOW INDEX FROM TABLE| Table | Non_unique | Key_name | Seq_in_index | Column_name | Null |
|---|---|---|---|---|---|
| player | 0 | PRIMARY | 1 | id | - |
| player | 0 | team_id_backnumber_idx | 1 | team_id | YES |
| player | 0 | team_id_backnumber_idx | 2 | backnumber | YES |
| player | 1 | player_name_idx | 1 | name | - |
- multicolumn index의 경우 중복된 Key_name의 값이 에트리뷰트의 개수 만큼 있으면 Seq_in_index 값으로 구별이 가능하다.
인덱스 동작 방식
A 테이블
| id | value |
|---|---|
| - | 1 |
| - | 3 |
| - | 2 |
| - | 2 |
| - | 4 |
| - | 0 |
INDEX(A) - B-tree 기반
| value | ptr |
|---|---|
| 0 | - |
| 1 | - |
| 2 | - |
| 2 | - |
| 3 | - |
| 4 | - |
- 특정 에트리뷰트에 인덱스를 생성하게 되면 인덱스를 관리하는 테이블이 생성된다. 테이블은 특정 에트리뷰트에 해당하는 값과 포인트값으로 이루어져 있다. 에트리뷰트에 해당하는 값은 정렬이 되어있는 상태이며 포인트 값은 실제 A테이블의 튜플을 가리키는 주소값을 가지고 있다.
- 인덱스를 관리하는 테이블을 이진 탐색으로 조회할 때 결과값이 복수일 경우가 있으므로 조건에 매칭하는 데이터를 찾고 그 데이터를 기준으로 위 아래로 탐색을 시작한다.
- 인덱스가 생성되어있는 에트리뷰트를 조건으로 조회를 하게 되면 인덱스를 관리하는 테이블을 이진 탐색으로 데이터를 찾는다.
- 인덱스가 생성되어있는 에트리뷰트와 일반 에트리뷰트 두 개의 조건으로 조회를 하게 되면 인덱스를 관리하는 테이블을 이진 탐색으로 데이터를 찾고 주소값에 적혀있는 튜플을 찾아 일반 애트리뷰트의 조건을 확인한다. 그러므로 일반 에트리뷰트의 조건을 찾을 때는 full scan 방식으로 조회한다.
- 위 사항을 방지하기 위해 multicolumn 인덱스로 생성한다.
/// 인덱스가 되는 에트리뷰트는 왼쪽부터 우선 순위가 된다.
CREATE INDEX player_name_idx ON PLAYER (first, second);- 하나의 에트리뷰트가 단일 인덱스를 생성하였고 다른 에트리뷰트와 함께 multicolumn 인덱스를 생성했을 때 실제 쿼리가 동작할 때 어떤 인덱스를 사용했는지 확인하기 위한 키워드로는 EXPLAIN이 있다. 선택하는 기준은 DBMS의 옵티마이저가 적절하게 인덱스를 선택 해준다.
EXPLAIN
SELECT * FROM PLAYER WHERE backnumber = 7;쿼리 결과
| table | possible_keys | key |
|---|---|---|
| player | backnumber_idx | backnumber_idx |
- 단 특정 인덱스를 사용하고 싶을 경우에는
// 사용 권장
SELECT * FROM PLAYER USE INDEX(backnumber_idx) WHERE backnumber = 7;
// 사용해
SELECT * FROM PLAYER FORCE INDEX(backnumber_idx) WHERE backnumber = 7;
// 사용하지마
SELECT * FROM PLAYER IGNORE INDEX(backnumber_idx) WHERE backnumber = 7;인덱스 생성 주의사항
- 인덱스를 적절히 사용한다면 조회 성능이 높아지지만, 무분별한 인덱스 생성은 추가적인 저장공간을 차지하고 테이블에 데이터가 추가/삭제/생성될 때 마다 인덱스를 관리하는 테이블에도 반영이 되어야 하는 점을 주의해야 한다.
참고 문서 및 링크
Covering 인덱스
- 테이블을 조회 할 때 모든 에트리뷰트의 데이터를 가져오는 것이 아닌 특정 에트리뷰트 값만 가져오고 이에 매칭하는 인덱스가 있을 경우에는 실제 테이블을 참조하지 않고 인덱스를 관리하는 테이블에서 데이터를 바로 가져올 수 있으며 조회 성능이 훨씬 빠르다.
Hash 인덱스
- hash table을 사용하여 인덱스를 구현한다.
- 시간복잡도 O(1)의 성능을 보여준다.
- rehashing에 대한 부담이 크다.(rehashing이란 hash 테이블에 데이터를 저장하다 보면 저장공간이 꽉 차거나 부족한 경우가 생기는데 이 때 hash 테이블에 용량을 늘려주는(재정의) 작업을 의미한다.)
- 동일 비교는 가능하지만 범위 비교는 불가능하다.
- multicolumn 인덱스인 경우 B-tree 기반에서는 최우선순위 기준 에트리뷰트 조건으로만 조회가 가능했지만 hash 기반에서는 multicolumn 인덱스의 모든 값이 조건 에트리뷰트와 일치해야만 조회가 가능하다.
full scan이 더 좋은 경우
- 테이블에 데이터가 적은 경우
- 조회하려는 데이터가 테이블의 상당 부분을 차지하는 경우
참고 문서 및 링크
