[DB] INDEX란? (with. 클러스터링 & 논-클러스터링)

인덱스를 사용하는 이유 

SELECT * FROM customer WHERE first_name = 'Minsoo';

• first_name이 Minsoo인 튜플을 찾기 위해 full Scan이 진행된다.

사용 이유

1. 조건을 만족하는 튜플을 빠르게 조회
2. 빠르게 정렬(order by)하거나 그룹핑(group by)하기 위해

인덱스를 거는 방법

SELECT * FROM player WHERE name = 'Sonny'
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);

• 이름은 동명이인이 있을 수 있으므로 중복을 허용한다.
• 반대로 팀ID와 백넘버의 경우, 중복을 허용하지 않기 위해 UNIQUE INDEX 를 이용하자.

추가로 테이블 생성 시에도 인덱스를 만들어 줄 수 있다.

 

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)
);

두 개의 어트리뷰트에 대한 인덱스를 multicolumn index 혹은 composite index 라고 한다.

 

테이블에 걸린 인덱스 확인하기

SHOW INDEX FROM player;​

• Key_name은 인덱스 이름을 의미한다. 여기서 같은 이름을 가진 두 칼럼은 milticolumn index 임을 의미
• seq_in_index를 통해 적용된 순서를 알 수 있다.

B트리 기반 인덱스 동작 방식

• 인덱스 테이블는 테이블의 선택된 칼럼들과 ptr로 구성되어 있다.
• 테이블의 선택된 칼럼들은 오름차순으로 정렬되어 있다.
• 정렬되어 있기 때문에 탐색 시, 이분탐색을 통해 탐색이 이루어 진다.
• ptr 은 원본 테이블의 각 튜플의 위치가 저장되어 있다.

인덱스 칼럼이 한 개인 경우

만약 WHERE a = 9 를 탐색해보자

중간 튜플을 탐색하고 9와 비교를 하고, 9보다 작으면 윗 부분은 더이상 탐색하지 않는다.

이 경우에는 5보다 크므로 아래부분을 탐색한다.

그 이후로 동일한 방식으로 탐색을 진행한다.

인덱스 칼럼이 두 개인 경우

위 인덱스를 통해 WHERE a = 7 AND b = 95; 인 경우를 탐색해보자

이분탐색을 통해 a가 7인 경우를 찾았다고 해보자

이 경우에 수 많은 a가 7인 튜플가 있을 수 있고, 각 경우에 대해 b가 95인지 모두 확인하는 절차 필요하다. 그러므로 b 탐색에 대해 full scan이 발생하게 된다.

이런 full scan을 해결하기 위해 a와 b에 대한 multicolumn index를 만들어 보자

이 경우 이분탐색을 통해 a=7이고 b=95인 경우를 찾았다고 해보자

이 경우, 선택된 칼럼에 대해 윗부분을 탐색하게 된다. 7, 80에 대한 튜플은 b=95라는 조건이 성립되지 않는다.

또한 7,80 튜플 위쪽으로는 b가 80보다 작다는 것이 보장되었으므로 탐색을 더이상 진행하지 않고 종료된다.

인덱스 칼럼의 순서의 중요성

이전에 사용한 multicolumn index를 이용하여 WHERE b = 95 인 경우를 탐색해보자.

이 경우, b 어트리뷰트에 대한 정렬이 보장되지 않으므로 이분탐색을 진행할 수 없다.

어떤 인덱스가 사용하지?

사용된 인덱스 확인하기

EXPLAIN SELECT * FROM player WHERE backnumber = 7;​

• 인덱스는 Optimizer가 알아서 적절한 인덱스를 선택한다.

 

특정 인덱스 사용하도록 하기

이런 인덱스를 사용하면 좋다 (권유)

SELECT * FROM player USE INDEX (backnumber_idx) WHERE backnumber = 7;​

무조건 이런 인덱스를 사용해라

SELECT * FROM player FORCE INDEX (backnumber_idx) WHERE backnumber = 7;

• 지정한 인덱스 사용 시, 비효율적인 경우 다른 인덱스를 선택하긴 한다.

 

인덱스 사용 시 고려해볼 점

인덱스를 막 사용하면?

1. table에 write할 때마다 index도 변경될 수 있다.
2. 추가적인 저장 공간을 차지

 

Full Scan이 더 좋은 경우

1. table에 데이터가 조금 있는 경우
2. 조회하려는 데이터가 테이블의 상당부분을 차지할 경우

• 위 경우, 테이블에 조회할 정보가 모두 있기 때문에 Full Scan이 더 유리 할 수 있다.

 

추가

Covering Index

SELECT team_id, backnumber FROM player WHERE team_id = 5;

• 위 쿼리를 검색 시, INDEX 테이블에서 찾은 결과를 바탕으로 ptr을 통해 PLAYER 테이블로 돌아와서 정보를 조회할 필요가 없다.
• 왜냐하면 INDEX 테이블에 team_id와 backnumber를 가지고 있기 때문

이런 경우를 Covering Index 라고 한다.

 

Hash Index

• hash table을 이용한 index
• 시간복잡도: O(1)
• 해시테이블 크기를 재조정하는 리해싱 에 대한 부담
• equality 비교만 가능하고, range 비교는 불가능
• multicolumn index의 경우, 전체 어트리부트에 대한 조회만 가능

---

인덱스 종류

클러스터링: 실제 데이터와 같은 무리의 인덱스

논-클러스터링: 실제 데이터와 다른 무리의 별도의 인덱스

 

논-클러스터링의 예: 책의 찾아보기 페이지

 

클러스터링 인덱스

적용방법

#1
ALTER TABLE member ADD CONSTRAINT pk_id PRIMARY KEY (id);

#2
ALTER TABLE member MODIFY COLUMN id int NOT NULL;
ALTER TABLE member ADD CONSTRAINT nuq_id int UNIQUE(id);​

구조

• B트리 구조로 이루어져 있다.
• 리프 페이지에는 실제 데이터가 저장되어 있다.

특징

1. 실제 데이터 자체가 정렬되어 있다.
2. 테이블 당 1개만 존재할 수 있다.
3. 리프 페이지가 데이터 페이지
4. primary key - unique, notnull 사용 시 자동 생성되고, 순서대로 우선순위를 가짐.

논-클러스터링 인덱스

적용방법

#1
ALTER TABLE member ADD CONSTRAINT unq_name UNIQUE(name);
#2
CREATE UNIQUE INDEX unq_idx_name ON member (name);
#3
CREATE INDEX idx_name ON member(name);​

구조

특징

1. 실제 데이터 페이즈는 그대로 사용
2. 별도의 인덱스 페이지를 생성 → 추가 공간이 필요
3. 테이블당 여러개 존재 가능
4. 리프 페이지에 실제 데이터 페이지 주소를 담음
5. unique 제약조건 적용 시 자동 생성
6. 직접 index 생성 시, 논-클러스터링 인덱스 생성

논-클러스터링 실제 구조

기존 구조의 문제점

• 페이지 테이블 중간에 데이터를 삽입할 경우, 데이터의 이동이 필요하게 된다.
• 따라서, 논-클러스터링에는 페이지 테이블의 주소 대신 인덱스가 저장되어 있다.

참고

https://www.youtube.com/watch?v=edpYzFgHbqs

https://www.youtube.com/watch?v=IMDH4iAQ6zM