DB index와 B-tree

index?

조회하는 쿼리가 하나 있다. CUSTOMER 테이블의 튜플은 100만 개라고 해보자.

SELECT *
FROM customer
WHERE first_name = 'Minsoo';

• first_name에 index가 걸려있지 않다면?
  • full scan(= table scan)으로 찾아야 한다.
  • 복잡도: O(N)
• first_name에 index가 걸려있다면?
  • full scan보다 더 빨리 찾을 수 있다.
  • 복잡도: O(logN) (B-tree based index일 경우)

---

index를 사용하는 이유

: 조건을 만족하는 튜플(들)을 빠르게 조회하기 위해

: 빠르게 정렬(order by)하거나 그룹핑(group by)하기 위해

// 이런 쿼리문의 특정 조건을 만족하는 데이터들을 빠르게 탐색하기 위해
SELECT * FROM customer WHERE first_name = 'Minsoo';
DELETE FROM logs WHERE log_datetime < '2022-01-01';
UPDATE employee SET salary = salary * 1.5 WHERE dept_id = 1001;
SELECT * FROM employee E JOIN department D ON E.dept_id = D.id;

 

---

index 거는 법 (mysql 기준)

PLAYER table이 있다고 가정하자.

attribute는 (id, name, team_id, backnumber) 가 있다.

이 테이블을 조회하는 쿼리가 있다.

mysql> SELECT * FROM player WHERE name = 'Sonny';
mysql> SELECT * FROM player WHERE team_id = 105 and backnumber = 7;

이 때, index를 만들어 보자.

 

- 이미 테이블이 존재하고, 그 테이블에 인덱스를 추가하는 경우

// name은 중복 데이터가 있을 수 있으므로 (not unique) 그냥 인덱스
mysql> CREATE INDEX player_name_idx ON player (name);
			(인덱스 이름)	(테이블)  (어트리뷰트)
// 팀 내에서는 등번호가 같을 수 없으므로 team_id와 backnumber 두 개는 유니크한 식별자가 된다. 유니크 인덱스
mysql> CREATE UNIQUE INDEX team_id_backnumber_idx ON player (team_id, backnumber);

 

- 테이블을 생성할 때 인덱스를 같이 생성하는 경우

mysql> 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)와 같이 두 개의 attribute에 인덱스를 생성하는 것을
  multicolumn index 또는 composite index라 한다.
• 대부분의 RDBMS에서는, primary key에는 index가 자동 생성된다.

- 어떤 index가 걸려 있는지 확인하는 방법

mysql> SHOW INDEX FROM player;

 

---

index 동작 방식 (B-tree 기반)

 

 

 

 

 

 

 

index 사용 시 참고 사항