[데이터베이스] 인덱스

인덱스

책 『면접을 위한 CS 전공지식 노트』를 바탕으로 스터디를 진행하면서 공부한 내용을 정리했다.

 

~ 목차 ~

1. 인덱스의 필요성
2. 인덱스의 효율성
    2.1 트리 구조
    2.2 대수확장성
3. 인덱스 만드는 방법
    3.1 MySQL
    3.2 MongoDB
4. 인덱스 최적화 기법

 

 

1. 인덱스의 필요성

- 인덱스(index)는 데이터베이스에서 테이블의 데이터를 빠르게 검색하기 위해 사용하는 데이터 구조이다.

- 아래 그림과 같은 책의 '찾아보기'섹션에 비유할 수 있다.

  '찾아보기'를 통해 내가 찾고자 하는 항목이 본문의 어느 위치에 있는지 빠르게 확인할 수 있다.

 

 

2. 인덱스의 효율성

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

 

  2.1 트리 구조

  - 데이터베이스의 인덱스는 주로 B-트리와 같은 균형 이진 트리 구조를 사용한다.

 

  - 장점: 각 노드에 여러 키를 저장할 수 있어서 데이터 증가해도 노드 수가 효율적으로 많아진다.

 

  - 책에서는 2개의 예시로 트리 구조의 효율성에 대해서 설명한다. 

 

    - 1번째 예시는 루트노드와 리프노드로 구성된 B-트리이다. 

      이러한 자료구조에서는 E를 찾을 때 E가 있을 법한 리프노드로 들어가서 E를 탐색한다. 이렇게 하면 2번만에 E를 찾을 수 있다.

 

 

      - 2번째 예시는 루트노드, 브랜치노드, 리프노드로 구성된 B-트리이다.

        이러한 자료구조에서는 57을 찾을 때 루트노드부터 브랜치노드, 리프노드로 내려오면서 <= 를 활용해서 탐색을 한다.

 

 

  2.2. 대수확장성

  - 대수확장성이란, 트리 깊이가 리프 노드수에 비해 매우 느리게 성장하는 것을 뜻한다.

    데이터의 양이 많아지더라도 트리의 깊이는 데이터 양에 대해서 로그 크기만큼만 증가한다. 

 

  - 즉, 총 데이터 수가 N개이고 트리의 한 노드에 m개의 키를 저장할 수 있을 때 트리의 최대 깊이 d는 $d = log_{m}N$가 된다.

     e.g. m=100인 B-트리에서

         i) N = 10,000: $d=log_{100}10,000=2$

         ii) N = 1,000,000: $d=log_{100}1,000,000=3$

         → 데이터가 100배로 늘어나도 트리 깊이는 1밖에 늘어나지 않는다.

 

  - 장점: 검색의 시간복잡도가 $O(log⁡_{m}N)$으로, 대규모 데이터에서도 일정 수준의 속도를 유지할 수 있다.

 

 

3. 인덱스 만드는 방법

- 인덱스를 만드는 법은 데이터베이스마다 다르다. 책에서는 MySQL과 MongoDB를 기준으로 설명한다.

 

  3.1 MySQL

  - MySQL에는 클러스터형 인덱스와 세컨더리 인덱스가 있다.

 

    ① 클러스터형 인덱스

      - 테이블당 하나만 생성할 수 있다.

      - Primary Key로 설정하면 자동으로 클러스터형 인덱스가 생성된다.

         Unique와 Not Null 조건을 조합해 클러스터형 인덱스를 수동으로 생성할 수도 있다.

      - 단일 필드(e.g. age)를 기반으로 쿼리하면 클러스터형 인덱스로 충분하다.

 

    ② 세컨더리 인덱스

      - 여러 개의 세컨더리 인덱스를 만들 수 있다.

      - CREATE INDEX 명령을 통해 생성한다.

      - 여러 필드(e.g. age, name, email)를 조합한 복잡한 쿼리가 많다면 세컨더리 인덱스를 생성하는 것이 좋다.

 

 

  3.2 MongoDB

  - MongoDB에서는 기본적으로 _id 필드가 기본키 역할을 하고, 추가로 세컨더리 인덱스를 설정할 수 있다.

   

    ① 기본키

      - 도큐먼트를 생성하면 자동으로 기본키 역할을 하는 _id 필드를 생성한다.

      - _id는 각 도큐먼트에서 고유하고, 기본적으로 ObjectID로 설정된다.

 

    ② 세컨더리 인덱스

      - 기본키 외에도 추가로 세컨더리 인덱스를 설정할 수 있다.

      - 세컨더리 인덱스는 쿼리 성능 최적화가 필요한 필드에 생성한다.

      - 복합 인덱스

        - 여러 필드를 결합해서 복합 인덱스를 생성할 수 있다.

        - 특정 필드 조합에 대한 검색, 정렬, 필터링 성능을 최적화하는 데 유용하다.

 

 

4. 인덱스 최적화 기법

- 인덱스 최적화 기법은 데이터베이스들끼리 대체로 비슷하다. 최적화 할 때 고려해야 할 사항은 크게 3가지가 있다.

 

  - 인덱스는 비용이다

    - 쿼리의 모든 필드에 무작정 인덱스를 설정하면 오히려 성능이 저하될 수 있다.

      인덱스를 설정할 때는 추가적인 저장 공간과 연산 비용이 발생하기 때문이다.

                                           ↳ 인덱스를 탐색한 후에는 실제 데이터 위치를 참조해야 함 → 추가 디스크 I/O 발생

                                               컬렉션이 수정될 때 인덱스도 함께 갱신 → 쓰기 작업 비용 증가

 

 

  - 항상 테스팅하라

    - 인덱스 최적화를 위해서는 항상 테스팅을 해야한다.

      데이터와 쿼리에 따라서 인덱스의 효율이 달라지기도 하고, 잘못된 인덱스가 전체적인 성능을 저하시킬 수도 있기 때문이다.

 

    - 아래와 같은 MySQL 쿼리처럼 explain() 함수를 통해 테스팅을 하면서 걸리는 시간을 최소화 할 수 있다.

 

 

  - 복합 인덱스는 같음, 정렬, 다중값, 카디널리티 순서대로 생성해야 한다

      - 복합 인덱스는 아래와 같은 순서대로 생성해야 한다. 생성 순서에 따라서 인덱스의 성능이 달라지기 때문이다.

        ① 같음을 비교하는 쿼리 (e.g. ==, equal)

        ② 정렬에 쓰는 필드

        ③ 다중값을 출력해야 하는 필드 (e.g. >,<)

        ④ 카디널리티 높은 필드 (e.g. age와 email 중에서는 email 필드의 인덱스를 먼저 생성)

 

 

 

참고문헌

[1] 주홍철, 면접을 위한 CS 전공지식 노트, 서울: 길벗, 2022.