4.5 인덱스

참고한 책: 면접을 위한 CS 전공지식 노트 (http://www.yes24.com/Product/Goods/108887922)

4. 데이터베이스

    4.5. 인덱스

        4.5.1. 인덱스의 필요성

        4.5.2. B-트리

        4.5.3. 인덱스 만드는 방법

        4.5.4. 인덱스 최적화 기법

 

p. 217

4.5.1 인덱스의 필요성

인덱스는 데이터를 빠르게 찾을 수 있는 하나의 장치

인덱스를 설정하면 케이블 안에 찾고자 하는 데이터를 빠르게 찾을 수 있음.

 

p. 218

4.5.2 B-트리

인덱스는 보통 B-트리라는 자료 구조로 이루어져 있음.

루트 노드, 리프 노드, 루트 노드와 리프 노드 사이에 있는 브랜치 노드로 나뉨.

 

B-Tree는 탐색 성능을 높이기 위해 균형 있게 높이를 유지하는 Balanced Tree의 일종이다. 모든 leaf node가 같은 level로 유지되도록 자동으로 밸런스를 맞춰준다. 자식 node의 개수가 2개 이상이며, node 내의 key가 1개 이상일 수 있다.
node의 자식 수 중 최댓값을 K라고 하면, 해당 B-Tree를 K차 B-Tree라고도 한다. 

 

일반적인 트리인 경우 탐색하는데 평균적인 시간 복잡도로 O(logN)을 갖지만, 트리가 편향된 경우 최악의 시간복잡도로 O(N)을 갖게 된다.

트리가 편향되지 않고 균형있게 유지된다면 최악의 경우에도 시간복잡도는 O(logN)을 유지한다.

(출처: https://fomaios.tistory.com/entry/Data-Structure-B-Tree%EB%9E%80 )

 

B-트리 규칙

1. 노드 안에 k개의 데이터가 있다면 자식 노드 수는 k+1개여야 한다.
2. 노드 안에 데이터는 정렬되어 있어야 한다.
3. 자식 노드의 데이터는 부모의 데이터 값에 따라 배치된다.
4. 루트 노드가 리프 노드가 아닌 경우 항상 2개 이상의 자식을 갖는다.
5. M차 B-Tree라면 루트 노드와 리프 노드를 제외하고 최소 M/2개 이상의 데이터를 가지고 있어야 한다.
6. 모든 리프 노드의 높이는 같아야 한다.
7. 리프 노드의 데이터 수는 M-1 이하여야 한다.

(출처: https://fomaios.tistory.com/entry/Data-Structure-B-Tree%EB%9E%80 )

 

인덱스가 효율적인 이유와 대수확장성

인덱스가 효율적인 이유는 효율적인 단계를 거쳐 모든 요소에 접근할 수 있는 균형잡힌 트리 구조와 트리 깊이의 대수확장성 때문.

 

대수확장성: 트리 깊이가 리프 노드 수에 비해 매우 느리게 성장하는 것. 예를 들어 트리 깊이는 열 개짜리로 100만개의 레코드를 검색할 수 있는 것.

 

p. 220

4.5.3 인덱스 만드는 방법

데이터베이스마다 인덱스 만드는 방법이 다름.

 

MySQL

클러스터형 인덱스와 세컨더리 인덱스가 있음.

	클러스터형 인덱스	세컨더리 인덱스
옵션 생성 방법	기본키 만들 때 primary key	기본키로 만들지 않고 unique not null create index.. 명령어 기반
성능이 좋을 때(사용해야 할 때)	하나의 인덱스만 생성할 때 하나의 필드로 쿼리를 보낼 때	보조 인덱스로 여러 개의 필드 값을 기반으로 쿼리를 많이 보낼 때. 다양한 필드 기반으로 쿼리를 보낼 때

MongoDB

도큐먼트를 만들면 자동으로 ObjectID가 형성되며, 해당 키가 기본키로 설정됨.

세컨더리키도 부가적으로 설정해서 기본키와 세컨더리키를 같이 쓰는 복합 인덱스를 설정할 수 있음.

 

p. 221

4.5.4 인덱스 최적화 기법

데이터베이스마다 조금씩 다르지만 기본적인 골조는 똑같음. 여기서는 MongoDB 기반.

 

1. 인덱스는 비용이다

인덳스는 두 번 탐색하도록 강요함.

인덱스 리스트를 탐색하고 컬렉션을 탐색하기 때문이며, 관련 읽기 비용이 들게 됨.

컬렉션이 수정되었을 때 인덱스도 수정되어야 하는데, B-트리의 높이를 균형있게 조절해야 하고, 데이터를 효율적으로 조회활 수 있도록 분산시켜야 함.

쿼리에 있는 필드에 인덱스를 무작정 다 설정하는 것은 답이 아니며, 컬렉션에서 가져와야 하는 양이 많을수록 인덱스를 사용하는 것은 비효율적.

 

2. 항상 테스팅하라

인덱스 최적화 기법은 서비스 특징에 따라 달라짐.

따라서 항상 테스팅하는 것이 중요함.

explain() 함수를 통해 인덱스를 만들고 쿼리를 보낸 이후에 테스팅을 하며 걸리는 시간을 최소화해야 함.

//MySQL 테스팅 코드 예
EXPLAIN
SELECT * FROM t1
JOIN t2 ON t1.c1 = t2.c1

3. 복합 인덱스는 같음, 정렬, 다중 값, 카디널리티 순이다.

인덱스를생성할 때는 순서가 있고 생성 순서에 따라 성능이 달라짐.

같음, 정렬, 다중 값, 카디널리티 순으로 생성해야 함.

1. 어떠한 값과 같음을 비교하는 ==이나 equal이라는 쿼리가 있다면 제일 먼저 인덱스로 설정
2. 정렬에 쓰는 필드라면 그 다음 인덱스로 설정
3. 다중 값을 출력해야 하는 필드, 즉 쿼리 자체가 > 이거나 < 등 많은 값을 출력해야 하는 쿼리에 쓰는 필드라면 나중에 인덱스를 설정.
4. 카디널리티가 높은 순서를 기반으로 인덱스를생성해야 함.

카디널리티: 유니크한 값의 정도. 전체 행에 대한 특정 컬럼의 중복 수치를 나타내는 지표. 중복도가 낮으면 카디널리티가 높다고 말함. 중복도가 높으면 카디널리티가 낮다고 말함.

(출처: https://itholic.github.io/database-cardinality/ )