[DB] 인덱스란 무엇이고, 왜 쓰는걸까?

💡 이 글의 내용은 MySQL 8.0 이상 + InnoDB 스토리지 엔진 환경을 기준으로 작성되었습니다.

인덱스란?

DB에서 인덱스란, 쓰기 성능과 저장 공간을 희생하는 대신 DB의 읽기 속도를 향상시키는 데이터 구조이다.

인덱스를 왜 써야할까?

SELECT * FROM player WHERE name = 'Minsoo';

데이터가 100만건 있는 player 테이블에서 name='Minsoo'인 를 찾는 쿼리를 실행한다 해보자.

만약, name에 인덱스가 걸려있지 않을 경우 100만건의 데이터를 전부 찾아보는 테이블 풀 스캔을 하게 되고, 이때 시간 복잡도는 O(N)이 된다.

하지만, name에 B-Tree 기반 인덱스가 걸려있을 경우 시간 복잡도는 O(logN)이 된다.

→ 인덱스는 조건을 만족하는 튜플들을 빠르게 조회, 정렬(order by), 그룹핑(group by)하기 위해 사용한다.

B-Tree 인덱스

B-Tree는 DB에서 가장 일반적으로 사용되는 인덱스 알고리즘이다.

B-Tree는 트리 구조의 최상위에 하나의 루트 노드, 가장 하위에 있는 리프 노드, 루트 노드도 리프 노드도 아닌 중간 노드인 브랜치 노드로 구성된다.

B-Tree 인덱스 동작 방식

위 그림을 기반으로 B-Tree 기반 인덱스를 이용하여 name='Fabrizio'인 레코드를 찾는 과정을 설명하겠다.

해당 테이블에는 100만 건의 데이터가 있다고 가정한다.

우선 디스크에 들어있는 데이터 레코드들은 정렬이 되어있지 않지만, 인덱스의 키들은 정렬이 되어있다.

루트 노드부터 탐색을 시작하면 'Aamer'<'Fabrizio'<'Jaana'이므로 브랜치 노드의 페이지 2로 가서 탐색을 진행한다.

페이지 2에서는 'Ebbe'<'Fabrizio'<'Gad'이므로 리프 노드의 페이지 5로 가서 탐색을 진행한다.

리프 노드에는 인덱스 키에 해당하는 레코드의 주소가 있고, 디스크에서 데이터를 읽어와서 결과를 가져온다.

B-Tree 인덱스 키 추가, 삭제, 변경

테이블에 레코드를 추가하는 작업의 비용이 1이라면, 인덱스에 키를 추가하는 비용은 대략 1.5이다.

InnoDB에선 필요한 경우 인덱스 키 추가 작업을 지연시킬 수 있다.

하지만 PK나 유니크 인덱스의 경우는 중복 체크가 필요하므로 지연 처리가 불가능하다.

인덱스 키 변경은 키 값에 따라 저장될 위치가 결정되므로 삭제한 뒤 새로운 값을 추가하는 형태로 처리한다.

B-Tree 인덱스 검색 시 주의점

• 100% 일치, 앞 부분만 일치, 부등호 비교 조건에서는 인덱스를 활용할 수 있지만, 인덱스를 구성하는 키 값의 뒷부분만 검색하는 용도로는 인덱스를 사용할 수 없다.
• 인덱스를 이용한 검색 시 인덱스의 키 값에 변형이 가해진 후 비교되는 경우는 사용할 수 없다.
• InnoDB에선 데이터를 읽어오며 해당 레코드의 잠금을 획득하는데, 인덱스가 설정되어 있지 않아서 테이블 풀 스캔을 하게 되면 많은 레코드와 갭이 잠기게되어 성능 문제나 데드락이 발생할 수 있다.

→ 인덱스 설계가 매우 중요하다.

B-Tree 인덱스 사용에 영향을 미치는 요소

1. 인덱스 키 값의 크기

   키 값이 커지면 가질 수 있는 자식 노드의 수가 줄어들기 때문에 디스크 I/O가 늘어나고, 속도가 느려진다.

   또한 인덱스 키 값의 크기가 커지면 전체 인덱스 크기도 커져서 메모리에 캐시할 수 있는 레코드가 줄어든다.

   → 인덱스 키의 크기가 크면 성능이 저하될 수 있다.

2. 카디널리티

   카디널리티는 데이터의 중복도를 말하며, 높을 수록 중복된 값이 적다.

   인덱스는 카디널리티가 높을수록 검색 대상이 줄어들기 때문에 더 빠르게 처리된다.

   → 카디널리티가 높을 수록 읽어오는 데이터가 줄어들며 인덱스의 효율이 상승한다.

3. 읽어야 하는 레코드의 건수

   인덱스를 통해 레코드를 읽는 것은 바로 테이블의 레코드를 읽는 것 보다 비용이 높다. (약 4~5배)

   • 인덱스를 통해 레코드를 읽는 경우는 랜덤 디스크 I/O을 하기 때문에 느리다.

   만약, 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블 풀 스캔 후 필요한 레코드만 걸러내는 것이 더 효율적이다.

   → 읽어야 하는 레코드의 건수가 많을 수록 인덱스 사용이 비효율적이다.

B-Tree 인덱스를 통한 데이터 읽기

1. 인덱스 레인지 스캔

   인덱스의 접근 방법 중 가장 대표적이고, 뒤에 나오는 다른 방식보다 빠르다.

   과정은 아래와 같다.

   1. 인덱스에서 조건이 만족하는 값이 저장된 위치를 찾는다. (인덱스 탐색)
   2. 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 읽는다. (인덱스 스캔)
      • 해당 인덱스를 구성하는 컬럼의 정순 or 역순으로 정렬된 상태로 레코드를 가져온다.
   3. 읽어온 인덱스 키와 레코드 주소를 이용해 레코드를 읽는다.
      • 이때 레코드 한 건 마다 랜덤 I/O가 일어난다.
      • 만약 필요한 데이터가 전부 인덱스에 있다면 이 과정을 생략한다. (커버링 인덱스)

2. 인덱스 풀 스캔

   인덱스를 사용하지만 인덱스의 처음부터 끝까지 모두 읽는 방식이다.

   인덱스 크기가 테이블의 크기보다 작으므로 인덱스만으로 조건을 처리할 수 있을 때 테이블 전체를 읽는 것 보다 인덱스를 읽는 것이 더 효율적이고, 그럴 때 인덱스 풀 스캔 방식이 사용된다.

3. 루스 인덱스 스캔

   인덱스 레인지 스캔과 비슷하지만, 중간에 필요치 않은 인덱스 키 값은 무시하고 넘어가는 형태로 처리한다.

   일반적으로 GROUP BY or 집합 함수 중 MIN(), MAX() 함수에 대해 최적화를 하는 경우에 사용한다.

4. 인덱스 스킵 스캔

   인덱스 스킵 스캔이 없다면 new_idx(A,B)가 있을 때 아래 쿼리는 인덱스를 효율적으로 사용할 수 없다.

   SELECT * FROM employees WHERE B >= '2000-11-05';

   하지만, 인덱스 스킵 스캔은 아래와 같은 방식으로 처리하여 인덱스를 활용할 수 있다.

   // A 컬럼이 'type1', 'type2' 두 종류의 값만 가지고 있음
   SELECT * FROM employees WHERE A = 'type1' AND B >= '2000-11-05';
   SELECT * FROM employees WHERE A = 'type2' AND B >= '2000-11-05';

   위와 같은 처리 방식 때문에 인덱스 스킵 스캔을 사용하기 위해선 아래와 같은 조건이 필요하다.

   1. WHERE 조건절에 조건이 없는 인덱스의 선행 컬럼(위에선 A 컬럼)의 유니크한 값의 개수가 적어야한다.
   2. 쿼리가 인덱스에 존재하는 컬럼만으로 처리 가능해야 한다. (커버링 인덱스)

인덱스는 무조건 만들어야 할까?

테이블에 쓰기연산을 실행할 때 마다 인덱스도 변경되므로 인덱스를 적용하게 되면 쓰기 성능이 저하될 수 있다.

또한, 포인터와 인덱스의 키를 저장하기 때문에 추가적인 저장 공간을 차지한다.

또한, 아래의 경우는 인덱스를 생성하는 것 보다 테이블 풀 스캔이 더 좋을 수 있다.

1. 테이블에 데이터가 조금 있는 경우 (몇 십, 몇 백건 정도)
2. 조회하려는 데이터가 테이블의 상당 부분을 차지하는 경우
   • 인덱스를 통해 레코드를 읽는 것은 바로 테이블의 레코드를 읽는 것 보다 비용이 높다. (약 4~5배) 인덱스를 통해 레코드를 읽는 경우는 랜덤 디스크 접근을 하기 때문에 → 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블 풀 스캔 후 필요한 레코드만 걸러내는 방식으로 처리하는 것이 효율적이다.
     
3. 데이터가 너무 많아서 인덱스의 크기가 너무 큰 경우

그러므로 무작정 인덱스를 만들기 보다는 상황을 고려하여 신중히 만들어야 한다.

인덱스의 정렬 및 스캔 방향

인덱스 역순 스캔은 아래의 이유들 때문에 정순 스캔에 비해 28.9% 정도 시간이 더 걸린다.

1. 페이지 잠금이 인덱스 정순 스캔에 적합한 구조이다.
2. 페이지 내에서 인덱스 레코드가 단방향으로만 연결된 구조이다.

→ 자주 사용되는 정렬 순서로 인덱스를 생성하는 것이 효율적이다.

복합 인덱스란?

복합 인덱스란 여러 컬럼을 포함하는 인덱스를 말한다.

복합 인덱스는 선행 컬럼을 기준으로 정렬하고, 같은 값 끼리는 뒤에 있는 컬럼을 기준으로 정렬한다.

복합 인덱스 생성 시 주의할 점

1. 선행 컬럼의 카디널리티가 낮으면 더 많은 데이터를 확인해야 하므로 비효율적이다.

   SELECT id FROM hotel WHERE region_id=3 AND category_id=2

   위 쿼리를 아래 두 가지 인덱스를 사용하여 실행했을 때를 비교해보자.

   • category_region_idx(category_id, region_id)

     category_id	region_id	PK
     1	1	3
     1	2	2
     2	1	5
     2	3	1
     2	4	4

   • region_category_idx(region_id, category_id)

     region_id	category_id	PK
     1	1	3
     1	2	5
     2	1	2
     3	2	1
     4	2	4

   category_region_idx를 사용하는 경우는 category_id=2를 만족하는 3개의 레코드 중 region_id=3인 레코드를 찾아야 한다.

   하지만, region_category_idx는 region_id=3를 만족하는 1개의 레코드 중 category_id=2인 레코드를 찾으면 되므로 탐색 횟수가 줄어든다.

2. 선행 컬럼이 없는 조건의 경우에는 인덱스를 사용하기 어렵다.

   복합 인덱스는 선행 컬럼을 기준으로 정렬되어 있어서 선행 컬럼이 없으면 효율적인 인덱스 사용이 어렵다.

   그러므로 자주 사용하는 컬럼을 선행컬럼으로 하는 것이 좋다.

클러스터링 인덱스란?

클러스터링은 테이블의 레코드를 클러스터링 인덱스가 비슷한 것들 끼리 물리적으로 묶어 저장하는 것을 말한다.

InnoDB에서는 PK를 생성할 때 자동으로 PK를 기반으로 클러스터링 인덱스를 생성한다.

만약 PK가 없다면 아래와 같은 로직으로 클러스터링 인덱스를 생성할 컬럼을 선택한다.

1. NOT NULL 옵션의 유니크 인덱스 중 첫 번째 인덱스를 클러스터링 키로 선택한다.

2. 자동으로 유니크한 값을 가지도록 증가되는 컬럼을 내부적으로 추가한 후 클러스터링 키로 선택한다.

   → 위와 같이 생성된 경우는 명시적으로 나타나지 않으며 사용자가 SQL문에 사용할 수 없다.

클러스터링 인덱스의 장단점

• 장점

  • 클러스터링 인덱스를 이용한 검색 시 성능이 매우 좋다.
  • 모든 세컨더리 인덱스가 클러스터링 인덱스를 가지고 있어서 쿼리가 인덱스만으로 처리되는 경우가 많다.

• 단점

  • 테이블의 모든 세컨더리 인덱스가 클러스터링 키를 갖기 때문에 클러스터링 키 값의 크기가 클 경우 전체적인 인덱스의 크기가 커진다.

  • 세컨더리 인덱스를 통해 검색할 때 클러스터링 인덱스로 한번 더 검색해야 하므로 성능이 느리다.

    • InnoDB 스토리지 엔진에서는 클러스터링 인덱스만이 물리적인 주소를 가지고, 세컨더리 인덱스는 모두 클러스터링 인덱스 키 값을 가지고 있어서 이를 이용하여 데이터 레코드를 찾는다.

      

      그러므로 세컨더리 인덱스로 데이터를 찾기 위해서는 위와 같이 두 번의 B-Tree 탐색이 필요하다.
      

  • INSERT할 때 PK에 의해 저장 위치가 결정되므로 처리 성능이 느리다.

  • PK를 변경할 때 레코드를 DELETE하고 INSERT하는 작업이 필요하기 때문에 처리 성능이 느리다.

커버링 인덱스

커버링 인덱스란, 실제 테이블 접근 없이 인덱스에 있는 데이터만으로 쿼리를 처리할 수 있는 경우를 말한다.

이 경우 실제 테이블 접근 없이 인덱스 테이블 만으로 쿼리를 처리하므로 쿼리의 성능이 향상된다.

// category_region_idx(category_id, region_id)
SELECT id, name FROM hotel WHERE category_id=1 AND region_id=1;

위 쿼리와 같이 조건에 사용되는 컬럼과 조회하는 컬럼이 모두 인덱스에 포함되어 있으면 커버링 인덱스가 된다.

id	table	key	Extra
1	hotel	category_region_idx	Using index

이 경우, 위와 같이 EXPLAIN의 Extra 컬럼에 Using index 라는 메시지가 나온다.

참고로 세컨더리 인덱스인 category_region_idx에는 클러스터링 인덱스인 id도 포함된다.

유니크 인덱스

유니크 인덱스는 같은 값이 2개 이상 저장될 수 없는 인덱스를 말한다.

유니크 VS 일반 인덱스

• 인덱스 읽기
  • 유니크 인덱스는 데이터가 고유하므로 일치하는 레코드를 하나 찾으면 검색이 끝나지만, 일반 인덱스는 인덱스 키 값이 같은 레코드가 여러개일 수 있어서 어떤 것이 만족하는 레코드인지 찾는 연산이 필요하다.
  • 하지만 이는 디스크 접근이 아닌 메모리 상에서 이뤄지는 작업이므로 성능에 영향이 거의 없다.
  • 그러므로 유니크 인덱스와 일반 인덱스는 같은 수의 레코드를 읽을 때 성능 차이가 거의 없다.
    • 물론 일반 인덱스는 중복된 데이터 때문에 더 많은 데이터를 읽을 수 있다.
• 인덱스 쓰기
  • 유니크 인덱스의 키 값을 쓸 때는 중복 체크 과정이 필요해서 일반 인덱스 보다 느리다.
  • MySQL에선 중복 체크 시 읽기 잠금을, 쓰기 시 쓰기 잠금을 사용하므로 데드락이 자주 발생한다.
  • 유니크 인덱스는 저장 및 변경 시 중복 체크를 해야하므로 작업을 버퍼링하지 못한다.

→ 유일성을 꼭 보장해야 하는 컬럼에는 유니크 인덱스를 생성하고, 그렇지 않다면 일반 인덱스 생성을 고려하자.

해시 인덱스

해시 테이블을 사용하여 구현한 인덱스를 말한다.

• 장점
  • 시간 복잡도가 O(1)이다.
• 단점
  • rehashing에 대한 부담이 있다.
    • 해시 테이블은 배열로 저장해서 데이터가 쌓이다 보면 더 큰 사이즈로 바꿔줘야하는데 이를 rehashing이라고 한다.
  • 동일한지 동일하지 않은지에 대한 비교만 가능, 범위를 통한 비교나 정렬을 할 때는 사용이 불가능 하다.
  • 복합 인덱스의 경우 인덱스의 전체 컬럼에 대한 조회만 가능하다.
    • Index(a,b)면 a에 대한 조회에는 사용할 수 없고, 모든 컬럼에 대한 조회에만 사용 가능하다.