[DB/쉬운코드] 인덱스 (EXPLAIN/B 트리)

인덱스

SELECT * FROM customer WHERE name = 'Jennie';

customer 테이블에서 Jennie라는 이름을 가진 소비자를 찾는 상황을 가정해보자. `name`에 인덱스가 걸려있지 않다면 해당 쿼리는 customer 테이블을 풀 스캔하게 된다. O(n) 이는 모든 레코드를 하나 하나 확인하므로 성능 저하를 일으킨다.
하지만 인덱스를 사용하면 풀 스캔보다 더 빠르게 데이터를 조회할 수 있다. O(log n) 즉, 인덱스는 조건을 만족하는 레코드를 빠르게 조회하기 위해 사용한다.
 
인덱스는 쿼리 실행 속도를 향상시키지만 부작용도 존재한다.

• 테이블을 수정할 때마다 인덱스도 변경된다.
• 인덱스별로 추가적인 저장 공간이 필요하다.

💡 커버링 인덱스 : 인덱스만으로 조회하려는 속성들을 모두 커버할 수 있기 때문에 실제 데이터베이스에 접근하지 않아 조회 성능이 더 좋다.

⭐ 인덱스

• 데이터베이스의 조회 성능을 높이기 위해 사용하는 방법
• 항상 정렬된 상태를 유지한다.
• 데이터 변경 시 실행 속도가 느려진다.
• 추가적인 디스크 공간이 필요하다.

 

인덱스의 조회/생성

• 인덱스 조회

SHOW INDEX FROM table_name;

 

• 인덱스 생성

# after 테이블 생성
CREATE [UNIQUE] INDEX idx_name ON table_name (field_name[, ...]);

# when 테이블 생성
CREATE TABLE table_name (
  ...
  [UNIQUE] INDEX idx_name (field_name[, ...])
);

🚨 두 개 이상의 속성으로 이루어진 인덱스를 multicolumn index 또는 composite index라고 부른다.

🚨 대부분의 RDBMS는 primary key에 자동으로 인덱스를 생성한다. MySQL의 경우, foreign key에도 자동으로 인덱스를 생성하지만 그렇지 않은 DBMS도 있다. 

 

EXPLAIN

쿼리 앞에 `EXPLAIN` 키워드를 붙여주면 쿼리에서 사용하는 인덱스 등을 확인할 수 있다.

• `id` : 쿼리 실행 계획에서의 SELECT 문의 순서 (복잡한 쿼리의 경우 어떤 순서로 처리되는지 확인할 수 있다!)
• `select_type` : SELECT 문의 종류 (SIMPLE, SUBQUERY, DERIVED)
• `table` : 쿼리에서 참조하는 테이블
• `type` : 조회•조인 종류
  • `ALL` = 풀 스캔
  • `INDEX` = 인덱스 전체 스캔
  • `RANGE` = 인덱스 범위 스캔
• `possible_keys` : 해당 쿼리 실행 시 MySQL이 사용할 수 있는 인덱스
• `key` : 실제로 쿼리 실행에 사용된 인덱스 (= `possible keys` 중 최적의 것 선택)
• `rows` : 쿼리 실행 계획에 따라 읽어야 하는 대략적인 레코드의 수 (적을수록 좋다!)
• `filtered` :  쿼리 조건을 만족하는 레코드의 비율
• `extra` : 쿼리 실행에 대한 추가적인 정보
  • `Using index` = 데이터를 읽지 않고 인덱스만으로 데이터를 조회할 수 있다

🚨 쿼리에서 사용할 인덱스를 선택하지 않아도 optimizer가 자동으로 적절한 인덱스를 선택한다. 직접 인덱스를 선택하고 싶다면 `SELECT ... [USE/FORCE] INDEX(idx_name) ...`을 사용한다.

 

B 트리 기반  인덱스

members 테이블은 a, b, c를 속성으로 가지며 `a`에 인덱스가 걸려있다. B 트리 기반의 인덱스는 `a`에 대한 값들을 정렬된 상태로 유지하며 members 테이블의 레코드를 가리키는 포인터를 가진다. 정렬된 상태를 유지하기 때문에 binary search를 이용하여 빠르게 데이터를 탐색할 수 있다.

🚨 다른 속성에 대한 조건이 있는 경우, `a` 조건을 만족하는 레코드에 대해 풀 스캔 해야 한다.

🚨 `(a, b)` 인덱스를 생성하는 경우, `a`를 기준으로 정렬한 후에 `b`를 기준으로 정렬한다. 따라서 multicolumn index에서는 속성의 순서가 중요하다.

🤔 시간 복잡도가 O(1)인 해시 인덱스 대신 B 트리를 사용하는 이유

• 해시 인덱스는 인덱스를 배열로 관리하기 때문에 배열의 크기를 늘려야 하는 rehashing에 대한 부담이 있다.
• 해시 인덱스는 equality는 비교할 수 있지만, range 비교가 불가능하다.
• multicolumn index `(a, b)`의 경우, B 트리는 `a`만 조회할 때도 해당 인덱스를 사용할 수 있지만 해시 인덱스는 불가능하다. (= 부분 검색 불가)

 

B 트리

이진 탐색 트리 (BST) 는 다음 특징들을 갖는다.

• 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고, 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가진다.
• 자식 노드는 최대 두 개까지 가질 수 있다.

B 트리는 BST를 확장해서 만든 트리로, 자식 노드의 최대 개수를 늘리기 위해 부모 노드에 하나 이상의 key를 저장한다. 이때, 부모의 key들은 오름차순으로 정렬된 상태를 유지한다.

B 트리

	BST	B 트리
부모 노드 key 개수	1	1~
자식 노드 최대 개수	2	2~

최대 M개의 자식 노드를 가질 수 있는 B 트리를 "M차 B 트리"라고 부른다. M차 B 트리에서는 최대 M-1개의 key를 가질 수 있다.
 
B 트리에 데이터를 삽입하는 경우, 항상 리프 노드에 추가한다. 만약 노드가 넘치면 가운데 key를 기준으로 좌우 key를 분할하고 가운데 key를 위로 올린다. 

2를 추가하여 노드가 넘쳤다.	가운데 key인 2를 승진시킨다.

B 트리의 모든 리프 노드는 같은 레벨에 존재한다. (= balanced tree) BST는 balanced tree가 아니기 때문에 최악의 경우 시간 복잡도가 O(n)이 된다. 하지만 B 트리는 balanced tree이므로 최악의 경우에도 O(log n)의 시간 복잡도를 갖는다. 즉, 항상 일정한 성능을 낸다.

📝 B 트리

• BST를 일반화한 트리
• 부모 노드는 자식 노드를 두 개 이상 가질 수 있다.
• 노드가 자식 노드를 x개 가진다면, key는 x-1개를 갖는다.
• 노드 내의 key들은 오름차순으로 저장된다.
• 모든 리프 노드는 같은 레벨에 있다.

🚨 BST에도 항상 O(log n)의 시간 복잡도를 갖는 AVL 트리, Red-Black 트리가 있다. (self-balancing BST) 하지만 BST는 자식 노드를 최대 2개까지만 가질 수 있기 때문에 루트 노드에서 리프 노드까지의 거리가 길다.
반면, B 트리는 자식 노드를 2개 이상 가질 수 있으므로 데이터까지의 거리가 짧다.

 
데이터 삽입과 마찬가지로 데이터의 삭제도 항상 리프 노드에서 발생한다. 만약 삭제 후 최소 key 수를 만족하지 못한다면 트리를 재조정*한다.

1. key의 수에 여유가 있는 형제의 지원을 받는다.
2. 1번이 불가능하면 부모의 도움을 받는다.
3. 2번에 의해 부모의 key가 부족해지면 과정을 반복한다.

데이터를 삭제하여 최소 key 수를 만족하지 못한다.	key 수에 여유가 있는 OO의 지원을 받는다.
	왼쪽 형제의 도움을 받는다
	오른쪽 형제의 도움을 받는다
	(왼쪽 형제와 합친 후) 부모의 도움을 받는다

🚨 internal 노드를 삭제해야 하는 경우, 리프 노드와 위치를 바꾼 후 삭제한다. (predecessor*나 successor*)

*predecessor : 나보다 작은 데이터들 중 가장 큰 데이터
*successor : 나보다 큰 데이터들 중 가장 작은 데이터

---

참고자료

• https://www.youtube.com/watch?v=IMDH4iAQ6zM&list=PLcXyemr8ZeoREWGhhZi5FZs6cvymjIBVe&index=25
• https://www.youtube.com/watch?v=bqkcoSm_rCs&list=PLcXyemr8ZeoREWGhhZi5FZs6cvymjIBVe&index=26
• https://www.youtube.com/watch?v=H_u28u0usjA&list=PLcXyemr8ZeoREWGhhZi5FZs6cvymjIBVe&index=27
• https://www.youtube.com/watch?v=liPSnc6Wzfk&list=PLcXyemr8ZeoREWGhhZi5FZs6cvymjIBVe&index=28