[DataBase] 인덱스

인덱스

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

 

예로는 책의 마지막 장에 있는 찾아보기가 있다.

책의 본문 안에 찾고자 하는 항목을 찾아보기를 통해 빠르게 찾을 수 있다.

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

 

B-트리

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

B-트리는 루트 노드, 리프 노드, 브랜치 노드로 나뉜다.

 

출처 : 면접을 위한 CS 전공지식 노트(2022)

만약 E를 찾는다고 하면, 전체 테이블을 탐색하는 것이 아니다.

위 그림처럼 E는 D와 L 사이에 있으므로, 루트 노드에서 D로 들어가고 리프 노드에서 E를 찾을 수 있다.

 

자료 구조 없이 탐색한다면 다섯 번을 탐색해야 한다.

이렇게 노드로 나누면 두 번만에 값을 찾을 수 있다.

 

출처 : 면접을 위한 CS 전공지식 노트(2022)

트리 탐색은 루트 노드부터 일어난다.

그리고 브랜치 노드를 거쳐 리프 노드까지 내려온다.

57을 찾아라고 했을 때, '57보다 같거나 클 때까지'를 기반으로

처음 루트 노드에서는 39,83 이후 아래 노드로 내려와서

46,53,57 으로 내려오고 리프 노드에서 57을 찾을수 있다.

그리고 데이터 포인터를 통해 결괏값을 반환하게 된다.

 

인덱스가 효율적인 이유

인덱스가 효율적인 이유는 균형 잡힌 트리 구조와 트리 깊이의 대수확장성 때문이다.

 

대수확장성

트리 깊이가 리프 노드 수에 비해 매우 느리게 커지는 것.

 

출처 : 면접을 위한 CS 전공지식 노트(2022)

기본적으로 인덱스가 한 깊이씩 증가할 때마다 최대 인덱스 항목의 수는 4배씩 증가한다.

위 표에 따르면 트리 깊이가 열 개이면 약 100만 개의 레코드를 검색할 수 있다.

그렇기 때문에 많은 인덱스를 나눈 상태에서 탐색하는 것이 효율적이라 할 수 있다.

 

인덱스를 만드는 방법

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

 

MySQL

MySQL의 경우 클러스터형 인덱스와 세컨터리 인덱스가 있다.

*클러스터형 인덱스 : 인덱스 자체에 데이터가 저장되어 있다.

*세컨더리 인덱스 : 인덱스 자체에 데이터가 저장되지 않고 데이터의 주소가 저장되어 있다.

 

클러스터형 인덱스는 테이블당 하나를 설정할 수 있다.

primary key 옵션으로 기본키로 만들면 클러스터형 인덱스를 생성할 수 있다.

기본키로 만들지 않고 unique not null 옵션을 붙이면 클러스터형 인덱스를 만들 수 있다.

 

세컨더리 인덱스는 create index... 명령어를 기반으로 만들 수 있다.

하나의 인덱스만 생성한다면 클러스터형 인덱스를 생성하는 것이 성능이 더 좋다.

이 인덱스는 보조 인덱스로 여러 개의 필드 값을 기반으로 쿼리를 많이 보낼 때 생성해야 하는 인덱스이다.

예를 들어 age라는 하나의 필드로 쿼리를 보낸다면 클러스터형 인덱스가 낫다.

다만 age, name, email 등 여러 필드 기반으로 쿼리를 보낸다면 세컨더리 인덱스가 낫다.

 

MongoDB

도큐먼트를 만들면 자동으로 ObjectID가 생성되는데, 이 키가 기본키로 설정된다.

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

 

인덱스 최적화 기법

최적화 기법은 데이터베이스마다 다를 수 있다.

MongoDB를 기반으로 최적화 기법을 설명하면 다음과 같다.

 

1. 인덱스는 무조건 다 사용하는 것이 아니다.

인덱스는 두 번 탐색하도록 강요한다.

인덱스 리스트, 컬렉션 순으로 탐색하기 때문에 관련 읽기 비용이 들게 된다.

 

컬렉션이 수정되었을 때 인덱스도 수정되어야 한다.

이때 B-트리 높이를 균형 있게 조절하는 비용도 든다.

데이터를 효율적으로 조회할 수 있도록 분산시키는 비용도 들게 된다.

 

따라서 쿼리에 있는 필드에 인덱스를 무작정 설정하는 것은 답이 아니다.

특히 컬렉션에서 가져와야 하는 양이 많을수록 인덱스를 사용하는 것은 비효율적이다.

 

2. 항상 테스팅하며 시간을 최소화한다.

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

서비스에서 사용하는 객체의 깊이, 테이블의 양이 다르기 때문이다.

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

쿼리를 보낸 이후에 테스팅을 하며 걸리는 시간을 최소화해야 한다.

 

3. 복합 인덱스의 경우 같음, 정렬, 다중값, 카디널리티 순으로 생성한다.

복합 인덱스를 생성할 때는 순서가 있고 생성 순서에 따라 인덱스의 성능이 달라진다.

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

 

1. 어떠한 값과 같음을 비교하는 == 이나 equal 쿼리가 있으면 제일 먼저 인덱스로 설정한다.

2. 정렬에 쓰는 필드라면 그 다음 인덱스로 설정

3. 다중 값을 출력해야 하는 필드, 쿼리 자체가 > 이거나 < 등 많은 값을 출력해야 하는 쿼리에 쓰는 필드면 그 다음 인덱스로 설정한다.

4. 그 다음에는 카디널리티가 높은 순서를 고려해서 인덱스를 생성해야 한다. 예를 들어, age와 email이 있다면 email이 카디널리티가 높으므로 email 필드에 대한 인덱스를 age보다 먼저 설정해야 한다.

 

참조

• 주홍철, 면접을 위한 CS 전공지식 노트, 길벗(2022)