인덱스를 통해 DB내부의 데이터에 빠르게 접근할 수 있다.
B-트리
인덱스는 B-트리라는 자료 구조로 이뤄져있다.
B-트리는 루트 노드``브랜치 노드``리프 노드로 구성된다.
B-트리는 이진 트리와는 다르게 1개의 노드에 여러 정보를 갖고있을 수 있다.
최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 한다.
- M차 B트리의 노드는 M/2~M개의 자식을 가질 수 있다.
- 노드에는 (M/2)-1 ~ M-1개의 키가 포함될 수 있다.
- 노드의 키가 x개면 자식의 수는 x+1이다.
- 최소 차수는 자식수의 하한값이며, 최소 차수가 t면 M=2t-1이다.
B트리에서 탐색은 '있을법한 리프 노드를 탐색'하는 방법이다.
루트노드와 리프노드로 구성되어있다고 가정하면
루트노드 : [A,D,L]
리프노드 : [A,B,C],[D,E,F],[L,M,N]
이 있고, E를 찾기 위해선 루트 노드 -> 2번 리프 노드 . 총 2회만에 E를 찾을 수 있다.
위의 과정을 그대로 루트노드, 브랜치노드, 리프노드로 구성된 트리에 적용하면
루트노드 : [29,83,97]
브랜치 노드 : [1,20,22,29] ,[35,40,68,83] , [89,90,95,97]
리프 노드 : [36,37,40]...[50,57,68]...
57를 찾기 위해서 루트 - 2번 브랜치 - n번 리프로 총 3번을 거쳐 결과를 찾을 수 있다.
인덱스가 효율적인 이유는 효율적인 단계와, 모든 요소에 접근 가능한 균형 잡인 트리 구조와 트리 깊이의 대수확장성 때문이다.
대수확장성 : 트리 깊이가 리프 노드 수에 비해 느리게 성장
기본적으로 깊이 1레벨 증가시 최대 인텍스는 4배씩 증가한다. 이렇게 되면 트리 깊이 10 레벨로 100만개의 레코드 검색이 가능하다.
인덱스 만들기
mysql의 경우 클러스터형 인덱스, 서컨더리 인덱스가 있다.
클러스터형의 경우 테이블당 하나 설정이 가능하고, primary key 옵션으로 기본키로 만들면 클러스터형 인덱스 생성이 가능하고, 기본키가 아닌 unique not null 옵션을 붙이면 클러스터형 인덱스로 만들 수 있다.
create index 명령어를 기반으로 한다면 세컨더리 인덱스 생성이 가능하다.
세컨더리 인덱스는 보조 인덱스로 여러 개의 필드 값을 기반으로 쿼리를 많이 보낼 때 생성해야 한다.
단일 인덱스 기준으로 클러스터형 인덱스가 성능이 더 좋다. 만약 age라는 필드로 쿼리를 보낸다면 클러스터형 인덱스를, age,name,email등 여러 필드를 쿼리로 보낸다면 세컨더리 인덱스를 사용하면 된다.
인덱스 최적화
인덱스 최적화는 DB마다 다르지만 기법은 대부분 유사하다.
1. 인덱스는 비용이다.
인덱스는 인덱스 리스트 -> 컬렉션 순으로 탐색하므로 두 번 탐색한다. 또한 컬렉션 수정시 인덱스도 수정되기 때문에 (논문 내용 수정시 앞 목차 수정하듯) B-트리 높이 조절 비용, 데이터 분산 비용도 든다.
그렇기 때문에 쿼리에 있는 필드에 인덱스를 전부 설정하면 리소스가 많이 사용되기 때문에 비효율일 수 있다.
2. 항상 테스팅하라
인덱스 최적화 기법은 서비스 특징에 따라 다르다. 서비스에서 사용하는 객체의 깊이, 테이블 양 등이 다르기 때문에 테스팅을 항상 해야한다.
explain()함수를 이용해 인덱스를 만들고 쿼리를 보낸 이후에 테스팅을 하며 걸리는 시간을 최소화 해야한다.
3. 복합 인덱스는 같음, 정렬, 다중 값, 카디널리티 순이다.
보통 여러 필드를 기반으로 조회시 복합 인덱스를 생성한다. 이 인덱스를 생성할 때는 순서가 있고, 생성 순서에 따라 인덱스의 성능이 좌우된다.
그렇기 대문에 같음, 정렬, 다중 값, 카디널리티 순으로 생성하는 것이 성능이 가장 좋다.
- 같음 : --, equal이라는 쿼리가 있다면 가장 먼저 인덱스로
- 정렬 : 정렬에 쓰는 필드라면 다음 인덱스로
- 다중 값 : 쿼리 자체가 >,< 등 범위 출력이라면 3번 인덱스로
- 카디널리티 : 유니크한 값의 정도를 카디널리티라고 하는데, 이게 높은 순서대로 인덱스를 생성해야한다. age, email을 예로 들면 email의 카디널리티가 더 높기 때문에 email이라는 필드에 대한 인덱스를 먼저 생성해야 한다.
