[SQL] 인덱스, B-tree

1. 인덱스

 

1) 왜 필요할까? 언제쓸까?

- 조건을 만족하는 값을 빠르게 찾기 위해(일반 조건문, join시 조건문)

- 조건문(where)을 만족하는 행을 찾을때, 운이 나쁘면 모든 행을 전부 확인해야 함(full scan)

- full scan의 경우 시간복잡도는 O(n)

 

2) 어떻게 쓸까?

- 미리 원래 열을 복사해서 정렬을 한 뒤, 쉽게 찾고, 조건문에 걸린 특정 행의 원래 행을 찾아 반환

- B-tree를 쓸 경우, 시간복잡도는 O(logN)

 

2. 인덱스 만들어보기

- 참고자료: 쉬운코드 https://youtu.be/IMDH4iAQ6zM?si=spZOmOpF88n2DC-M

- 예: PLAYER table (MySQL)

id	name	team_id	backnumber

 

1) 중복을 허용하는 인덱스 

- mysql > SELECT * FROM player WHERE name = 'Sonny';

SELECT * FROM player WHERE name = 'Sonny';

- 이때, 이름은 동명이인이 있을 수 있으므로, 중복을 허용하는 인덱스를 생성

> CREATE INDEX 인덱스명 ON 테이블명 (컬럼명)

CREATE INDEX player_name_idx ON player (name);

 

2) 2개의 열로 만드는(멀티컬럼 인덱스) 중복이 없는 인덱스

SELECT * FROM player WHERE team_id = 105 and backnumber = 7;
CREATE UNIQUE INDEX team_id_backnumber_idx ON player(team_id, backnumber);

 

3) 만약 테이블을 만들때, 인덱스를 걸어주고 싶다면,

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

 

- primary key의 경우에는, 대부분의 sql에서 자동으로 index 생성해줌

 

3. 테이블에 인덱스 뭐있는지 알고싶다면

SHOW INDEX FROM player;

Table	Non_unique	Key_name	Seq_in_index	Column_name	Null
테이블이름	True / False (1,0)	인덱스 이름	멀티컬럼인덱스 열순서	열 이름	Null 허용 여부

 

4. B-tree

- 참고자료 : 쉬운코드 https://youtu.be/bqkcoSm_rCs?si=aJRayk-FRiSHebOc

1) 이진 트리 (Binary Search Tree, BST)

- 자식 노드가 최대 2개인 트리

- 부모노드가 k일때, 왼쪽 자식 노드는 k보다 작고, 오른쪽 자식 노드는 k보다 크다

- 최악의 경우 트리가 한쪽으로 쏠릴 수 있음

 

2) B-tree (BST를 일반화한 Tree)

- 자식 노드가 2개보다 많이 갖고 싶다

- 자식 노드가 3개일때, 부모 노드는 2개

- 제일 왼쪽 자식 노드는 왼쪽 부모 노드보다 작고, 가운데 자식 노드는 왼쪽 부모 노드보다 크고 오른쪽 부모 노드보다 작다. 오른쪽 자식노드는 오른쪽 부모노드보다 크다 (3차 B tree)

- 자식 노드는 트리로 확장할 수 있다. 

- internal 노드의 key 수가 x개라면, 자녀 노드의 수는 언제나 x+1개다

- M차 B tree의 의미: 가질 수 있는 최대 자식 노드의 수 - M

- balanced tree로 항상 일정한 성능을 보임