23.12.08 인덱스

1. 인덱스

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

    - 테이블 안에 내가 찾고자 하는 데이터를 빠르게 찾을 수 있다

    - 예) 책의 마지막 장에 있는 찾아보기와 같은 것

 

2. B 트리

    - B 트리라는 자료구조로 이루어짐

    - 루트 노드, 리프 노드, 루트 노드 와 리프 노드 사이의 브랜치 노드로 나뉨

  1) 루트 노드와 리프 노드 예제

       - E를 찾는 다고 하면 전체 테이블을 탐색하는 것이 아니라 있을 법한 리프 노드로 들어가서 E를 탐색

       - 이 자료구조 없이 E를 탐색하고자 하면 A, B, C, D, E 다섯번을 탐색해야 함

       - 노드들로 나누면 두번만에 리프 노드에서 찾을 수 있다

 

  2) 루트 노드와 리프 노드, 브랜치 노드 예제

       - 트리 탐색은 맨 위 루트 노드부터 탐색이 일어남

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

       - 57보다 같거나 클 때까지 <= 를 기반으로 처음 루트 노드에서는 39, 83 이후 아래 노드로 내려와 46, 53 57 등

         정렬된 값을 기반으로 탐색

       - 루트 노드부터 시작해 마지막 리프 노드에 도달해서 57이 가리키는 데이터 포인터르를 통해 결과값 반환

 

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

       - 인덱스가 효율적인 이유는 효율적인 단계를 거쳐 모든 요소에 접근할 수 있는 균형 잡힌 트리구조와

          트리 깊이의 대수확장성 때문

       - 대수확장성이란 트리 깊이가 노드 수에 비해 느리게 성장하는 것을 의미

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

       - 아래 포는 트리의 대수확장성으로 트리 깊이는 열개 짜리로, 100마나 개의 레코드를 검색 할 수 있다는 의미

       - 인덱스는 이보다 훨씬 더 효율적이며 그렇기 때문에 인덱스가 효율적이다

트리 깊이	인덱스 항목의 수
3	64
4	256
5	1,024
6	4,096
7	16,384
8	65,536
9	262,144
10	1,048,576

 

3. 인덱스 만드는 법

  1) MySQL

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

     (1) 클러스터형 인덱스

           - primary key 옵션으로 기본키를 만들면 생성 가능

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

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

           - 예) age 라는 하나의 필드만으로 쿼리를 보내는 경우

     (2) 세컨더리 인덱스

           - create index... 명령어를 기반으로 만들면 생성 가능

           - 보조 인덱스로 여려개의 필드 값을 기반으로 쿼리를 많이 보낼 때 생성

           - 예) age, name, email 등 다양한 필드를 기반으로 쿼리를 보낸 경우

 

  2) MongoDB

       - 도큐먼트를 만들면 자동으로 ObjectId가 형성됨

       - 해당 키가 기본키로 설정됨

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

 

4. 인덱스 최적화 기법 (MongoDB 기준)

  1) 인덱스는 비용이다

       - 인덱스는 두번 탐색하도록 강요함

       - 인덱스 리스트, 그다음 컬렉션 순으로 탐색하기 때문이며 관련 읽기 비용이 들게됨

       - 컬렉션 수정시 인덱스도 수정되어야 함 마치 책의 본문이 수정되었을 때 목차나 찾아보기도 수정해야하듯

       - B-트리의 높이를 균형있게 조절하는 비용도 들고 데이터를 효율적으로 조회할 수 있도록 분산시키는 비용도 들어감

       - 그렇기에 쿼리에 있는 필드에 인덱스를 무작정 다 설정하는 것이 답이 아니다

       - 또한, 컬렉션에서 가져와야 하는 양이 많을수록 인덱스를 사용하는 것은 비효율적

  2) 항상 테스팅

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

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

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

       - 아래는 MySQL 에서 테스팅을 수행하는 코드

EXPLAIN
SELECT * FROM t1
JON t2 ON t1.c1 = t2.c1

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

       - 보통 여러 필드를 기반으로 조회 할 때 복합인덱스 생성

       - 복합 인덱스 생성시에는 순서가 있고 생성 순서에 따라 인덱스 성능이 달라짐 

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

       A) 어떠한 값고 같음을 비교하는 == 이나 equal 이라는 쿼리가 있다면 제일 먼저 인덱스로 설정

       B) 정렬에 쓰이는 필드라면 그 다음 인덱스로 설정

       C) 다중 값을 출력해야 하는 필드, 즉 쿼리 자체가 > 이거나 < 등 많은 값을 출력해야 하는 쿼리에 쓰는

            필드라면 나중에 인덱스를 설정

       D) 유니크한 값의 정도를 카니널리티라고함

            카디널리티가 높은 순서를 기반으로 인덱스를 생성해야함

            예) age 와 email 이있다고 할 때 email 이 더 높다 즉, emial 이라는 필드에 대한 인덱스를 먼저 생성해야 함