인덱스에 대해

이상훈·2024년 9월 15일

CS

목록 보기

1/27

MySQL의 InnoDB 기준

인덱스란?

인덱스는 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다. 인덱스는 책의 목차처럼 데이터와 데이터의 위치를 포함한 내용을 생성하여, 빠르게 찾고자 하는 데이터를 조회할 수 있다. 만약 인덱스가 없다면 찾고자 하는 데이터를 테이블 내에서 full scan으로 순차 탐색하게 된다.

인덱스의 자료구조

먼저 인덱스의 자료구조를 살펴보자. Hash Table 혹은 B-tree 계열이 사용된다.

1. Hash Table

Hash table 기반의 DB 인덱스는 (데이터=컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현한다.

장점

조회 시 시간복잡도가 O(1)로 굉장히 빠르다.

단점 :

equality 비교만 인덱싱할 수 있고 range 비교는 인덱싱할 수 없다.
rehashing이 부담된다.
multi column 인덱스의 경우 전체 attributes에 대한 조회만 가능하다.
- (a, b)로 인덱스를 구성할 경우, B-tree는 a만으로도 인덱싱이 적용되지만, hash table은 불가

Hash table은 위 단점들 때문에 잘 사용되지 않고 대신 B-tree 계열이 주로 사용된다.

2. B-tree

먼저 B-tree에 앞서 Binary Search Tree부터 살펴보자.

Binary Search Tree 줄여서 BST는 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가진다. 또한 자녀 노드는 최대 2개까지 가질 수 있다.

장점

조회 시 평균적으로 시간복잡도가 O(logN)이다.

단점

트리가 편향될 경우 시간복잡도가 O(N)이 될 수 있다.
노드에 데이터를 1개만 저장할 수 있어서 트리가 상대적으로 높다.

B-tree는 BST의 단점들을 보완하기 위해 등장한 자료구조다.

결과적으로 인덱스는 B-tree 계열을 활용해 구현한다. 그 이유는 B-tree는 전반적으로 BST와 유사하지만,

1. 균형 잡힌 트리로서 모든 리프 노드의 높이가 같아서 일관된 log(N)의 성능을 보장한다.
2. 또한 노드에 여러 key를 저장할 수 있어서 트리의 높이가 BST보다 낮아 탐색에 더 유리하다.

1. B-tree가 균형 잡힌 트리인 이유

B-tree의 삽입, 삭제 플로우에 대해 간단하게 알아보자.

핵심은 데이터 삽입, 삭제는 모두 리프 노드에서 발생하며 이는 B-tree가 모든 리프 노드의 높이가 같은, 즉 균형 잡힌 트리인 이유이다.

자세한 플로우는 쉬운코드 유튜브를 참고하면 좋다. 이 블로그에서는 최대한 간단하게 서술하겠다.

(1부) B tree의 개념과 특징, 데이터 삽입이 어떻게 동작하는지를 설명합니다!
(2부) B tree 데이터 삭제 동작 방식을 설명합니다 (DB 인덱스과 관련 있는 자료 구조)

1. 데이터 삽입
데이터를 삽입할 때는 아래 규칙을 따른다.

추가는 항상 리프 노드에 한다
노드가 넘치면 가운데 key를 기준으로 좌우 key들은 분할하고 가운데 key는 승진한다.

case 1.1 : 노드가 넘치지 않은 경우

5를 삽입하는 경우

1. before

2. after

case 1.2 : 노드가 넘치는 경우

30을 삽입하는 경우

1. before

2. after

2. 데이터 삭제
데이터를 삭제할 때는 아래 규칙을 따른다.

삭제도 항상 리프 노드에서 발생
삭제 후 최소 key 수보다 적어졌다면 재조정한다.
2.1 key 수가 여유 있는 형제의 지원을 받는다.
2.2 2.1번이 불가능하면 부모의 지원을 받고 형제와 합친다.
2.3 2.2번 후 부모에 문제가 있다면 거기서 다시 재조정한다.

case 2.1 : key 수가 부족하지 않은 경우

6을 삭제하는 경우

1. before

2. after

case 2.2 : key 수가 부족한 경우(형제 지원)

5를 삭제하는 경우

1. before

2. after

case 2.3 : key 수가 부족한 경우(부모 지원)

형제 노드가 지원할 수 없다면 부모 노드가 키를 지원해주고 형제끼리 합친다.

7를 삭제하는 경우

1. before

2. after

2. B-tree가 데이터 탐색에 더 유리한 이유

B-tree는 한 노드에 여러 key 값을 담을 수 있어서 데이터 탐색에 더 유리하다. 이는 2가지 측면에서 이점이 있다.

1. secondary storage 접근 횟수
데이터베이스는 기본적으로 secondary storage에 저장된다. 그리고 만약 외부에서 데이터 조회와 같은 요청이 들어올 때, 메인메모리에 해당 데이터가 없다면 secondary storage에서 데이터를 블록 단위로 가져와 메인메모리에 로드한 다음 데이터를 처리한다. 그러나 만약 메인메모리에 데이터가 이미 존재한다면 캐싱 처리된다.

따라서 DB를 사용할 때 secondary storage 접근을 최소화하는 것이 성능 측면에서 중요하다. 인덱스로 B-tree를 사용하면 BST를 사용할 때보다 secondary storage 접근 횟수를 줄일 수 있다.

B-tree와 BST 성능 비교하기 전 아래 사항들을 가정하자.

tree의 각 노드는 서로 다른 block에 존재.

초기에 root 노드를 제외한 모든 노드는 secondary storage에 존재.

초기에 데이터 자체도 모두 secondary storage에 존재.

case 1 : AVL tree(Balanced BST tree의 일종) 사용
데이터 5를 조회시 secondary storage에 4번 접근한다.
case 2 : B-tree(5차) 사용
데이터 5조회시 secondary storage에 2번 접근한다.

2. 블록 단위 저장
AVL 트리에서 각 노드는 1개의 데이터를 가질 수 있지만, 5차 B-Tree에서는 각 노드는 2에서 4개의 데이터를 가질 수 있다. Secondary storage에서는 데이터를 블록 단위로 읽기 때문에 AVL 트리에서 특정 데이터를 읽어올 경우 해당 노드를 포함한 전체 블록을 읽어와야 한다. 이로 인해 불필요한 데이터까지 읽어올 가능성이 있다. 그러나 5차 B-Tree에서는 하나의 노드에서 데이터 수를 더 많이 가질 수 있으므로 특정 노드를 읽어올 때 연관된 데이터, 즉 사용 가능성이 높은 데이터를 읽어올 수 있다. 이로 인해 B-Tree를 사용하면 블록 단위 저장 공간 활용도가 더 좋아진다.

3. B+ tree

지금까지 B-tree에 대해 자세히 알아봤지만 실제로 많은 데이터베이스는 인덱스를 B-tree가 아닌 이를 확장한 개념인 B+ tree로 구현한다.

B+ tree는 B- tree와 달리 오직 리프 노드에만 데이터를 저장하고 리프 노드가 아닌 노드에서는 자식 포인터만 저장한다. 리프 노드에만 데이터가 저장되기 때문에 찾아가기 위해 중간 노드의 key와 리프 노드의 data가 중복될 수 있다. 또한 리프 노드끼리는 연결 리스트로 연결되어있다.

B-tree 대신 B+ tree를 사용하면 아래와 같은 이점이 있다.

1. 리프 노드를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있다. 따라서 하나의 노드에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다.

2. Full scan을 하는 경우 B+Tree는 리프 노드에만 데이터가 저장되어 있고, 리프 노드끼리 linked list로 연결되어 있기 때문에 선형 시간이 소모된다. 반면 B-Tree는 모든 노드를 확인해야 한다.

인덱스의 종류

클러스터링 인덱스는 실제 데이터 자체가 정렬되며 리프 페이지가 데이터 페이지를 의미한다. 테이블 당 1개만 존재 가능하며 주로 기본키가 이에 해당한다.

primary key(1순위)
unique + not null(2순위)

논클러스터드 인덱스는 실제 데이터 페이지는 그대로이고 별도의 인덱스 페이지를 생성한다. 리프 페이지에 클러스터드 인덱스가 적용된 컬럼의 실제 값(주로 PK)을 담고 있다. 테이블 당 여러개 존재할 수 있다.

다중 컬럼 인덱스

2개 이상의 컬럼으로 구성된 인덱스를 다중 컬럼 인덱스라 한다. 아래 그림은 다중 컬럼 인덱스일 때 각 인덱스를 구성하는 컬럼의 값이 어떻게 정렬되어 저장되는지를 보여준다. 중요한 것은 인덱스의 두 번째 컬럼은 첫 번째 컬럼에 의존해서 정렬돼 있다는 점이다. 즉, 두 번째 컬럼의 정렬은 첫 번째 컬럼이 똑같은 레코드에서만 의미가 있다는 것이다. 따라서 다중 컬럼 인덱스에서는 인덱스 내에서 각 컬럼의 위치(순서)가 상당히 중요하며, 신중하게 결정해야한다.

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

B-tree 인덱스는 인덱스를 구성하는 1) 컬럼의 크기와 2) 선택도, 3) 레코드의 수 등이 성능에 영향을 끼친다.

1. 인덱스 키 값의 크기

앞서 B-tree는 하나의 노드에 여러 key를 담을 수 있다고 했다. 그렇다면 MySQL에서 B-tree의 각 노드는 자식 노드를 몇 개까지 가질 수 있을까?

답은 인덱스의 페이지 크기와 키 값의 크기에 따라 결정된다. 참고로 InnoDB 스토리지 엔진은 페이지 또는 블록 단위로 디스크로부터 데이터를 읽고 쓸 수 있다. 인덱스도 마찬가지로 페이지 또는 블록 단위로 관리된다.

case 1) 만약 페이지 크기 = 16KB, 인덱스 키의 크기 = 16B, 자식 노드 주소의 크기 = 12B이면??

(16*1024/(16+12)) = 585개 키 저장 가능
case 2) 만약 인덱스 키의 크기를 32B로 늘리면??

(16*1024/(32+12)) = 372개 키 저장 가능

만약 실행한 select 쿼리가 500개의 레코드를 읽어야 할 때, case 1)은 하나의 인덱스 페이지만 조회하면 되지만, case 2)는 2개의 인덱스 페이지를 조회해야 해서 2번 이상 디스크에 접근해야 한다.

즉, 인덱스 키 값의 크기가 커지면 커질수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수가 적어지고, 그 때문에 같은 레코드 건수라 하더라도 더 많은 디스크 접근이 필요하게 된다.

2. 카디널리티

인덱스에서 카디널리티란 모든 인덱스 키 값 가운데 유니크한 값의 개수를 의미한다. 카디널리티가 낮다는 것은 중복된 값이 많다는 것을 의미하며 이는 검색 대상이 많아져서 인덱스의 효율성이 줄어들게 된다.

country라는 컬럼과 city라는 컬럼이 포함된 tb_test 테이블을 예로 들겠다. tb_test 테이블의 전체 레코드 건수는 1만 건이며, country 컬럼으로만 인덱스가 생성된 상태에서 아래의 두 케이스를 살펴보자.

select * from tb_test where country = "KOREA" and city = "SEOUL";

case 1) country 컬럼의 유니크한 값의 개수가 10개

case 2) country 컬럼의 유니크한 값의 개수가 1000개

case 1)은 평균 1000건, case 2)는 평균 10건이 조회될 수 있다. 만약 case 1,2 모두 실제 모든 조건을 만족하는 레코드가 단 1건이라면, case 1)은 1건의 레코드를 위해 쓸모없는 999개의 레코드를 더 읽은 것이지만, case 2)는 9건만 더 읽은 것이다. 따라서 case 1)은 비효율적일 수 있다.

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

테이블의 레코드가 100만 건 있을 때 50만 건을 읽어야 하는 쿼리가 있다면, 이 작업은 전체 테이블을 모두 읽어서 필요 없는 50만 건을 버리는 것이 효율적일지, 인덱스를 통해 50만 건만 읽어오는 것이 효율적일지 판단해야 한다.

보통은 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블의 25% 정도를 넘어서면 인덱스를 사용하지 않고 모두 직접 읽어서 필요한 레코드만 가려내는(필터링) 방식으로 처리하는 것이 효율적이다.

인덱스 스캔 방식

Index Range Scan

인덱스 레인지 스캔은 인덱스의 접근 방법 가운데 가장 대표적인 접근 방식으로, 밑에서 설명할 나머지 방식보다 빠르다. 인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다.

select * from employees where first_name between "Ebbe" and "Gad";

먼저 루프 노드에서부터 브랜치 노드를 거쳐 최종적으로 리프 노드까지 찾아 들어가 필요한 레코드의 시작점을 찾는다. 시작점을 찾으면 그때부터는 마지막 지점까지 리프 노드의 레코드만 차례대로 쭉 읽으면 된다. 그리고 동시에, 스캔하면서 얻은 인덱스 키와 레코드 주소를 이용해 데이터 파일(디스크)에서 해당 레코드가 저장된 페이지를 가져오는 방식이다.

디스크에 접근해서 데이터를 조회해오는 과정은 성능상 부담이 된다. 경우에 따라서는 디스크에 접근하지 않고 인덱스 페이지에 있는 컬럼만으로 조회 연산 처리가 가능한 경우가 있는데 이를 커버링 인덱스라한다.

Index Full Scan

인덱스 레인지 스캔과 마찬가지로 인덱스를 사용하지만, 인덱스 레인지 스캔과는 달리 인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라 한다. 인덱스 풀 스캔은 인덱스 레인지 스캔보다는 느리지만, 테이블 풀 스캔보다는 빠르다. 인덱스 풀 스캔은 아래 조건이 만족되었을 때 주로 사용된다.

쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우
ex) 인덱스는 (A, B, C) 컬럼의 순서로 만들어져 있지만 쿼리의 조건절은 B 컬럼이나 C 컬럼으로 검색하는 경우
쿼리가 인덱스에 명시된 컬럼만으로 조건을 처리할 수 있는 경우
-> 커버링 인덱스

만약 인덱스뿐만 아니라 데이터 레코드까지 모두 읽어야 한다면 테이블 풀 스캔을 따른다.

일반적으로 인덱스 풀 스캔 방식으로 인덱스를 사용하는 경우 인덱스를 효율적으로 사용하지 못했다는 것을 의미한다.

Loose Index Scan

루스 인덱스 스캔은 말 그대로 느슨하게 또는 듬성듬성하게 인덱스를 읽는 것을 의미한다. 루스 인덱스 스캔은 인덱스 레인지 스캔과 비슷하게 작동하지만, 중간에 필요치 않은 인덱스 키 값은 무시하고 다음으로 넘어가는 형태로 처리한다. 일반적으로 GROUP BY 또는 집합 함수 가운데 MAX() 또는 MIN() 함수에 대해 최적화하는 경우에 사용된다.

	select dept_no, MIN(emp_no)
	from dept_emp
    where dep_no between "d002" and "d004"
    group by dept_no;

이 쿼리에서 사용된 dept_emp 테이블은 dept_no와 emp_no라는 두 개의 컬럼으로 인덱스가 생성돼 있다. 또한 이 인덱스는 (dept_no, emp_no) 조합으로 정렬까지 돼 있어서 아래 그림과 같이 dept_no 그룹별로 첫 번째 레코드의 emp_no 값만 읽으면 된다. 즉 인덱스에서 where 조건을 만족하는 범위 전체를 다 스캔할 필요가 없다는 것을 옵티마이저는 알고 있기 때문에 조건에 만족하지 않는 레코드는 무시하고 다음 레코드로 이동한다. 아래 그림을 보면 인덱스 리프 노드를 스캔하면서 불필요한 부분은 그냥 무시하고 필요한 부분만 읽었음을 알 수 있다.

Index Skip Scan

인덱스 스킵 스캔은 MySQL 8.0 버전에 추가된 최적화 기능으로 조건절에 첫 번째 인덱스가 없어도 두 번째 인덱스만으로 인덱스를 검색할 수 있게 해주는 기능이다.

(gender, birth_date) 구성된 인덱스가 있다고 가정하고 아래 조회 쿼리를 보자.

select gender, birth_date from employees where birth_date >= "1965-02-01";

만약 인덱스 스킵 스캔이 없다면(MySQL 8.0 이전) 위 쿼리는 인덱스 풀 스캔을 탔을 것이다.

그러면 MySQL 8.0은 인덱스 스킵 스캔으로 어떻게 최적화했을까?

MySQL 옵티마이저는 우선 gender 컬럼에서 유니크한 값을 모두 조회해서 주어진 쿼리에 gender 컬럼의 조건을 추가해서 쿼리를 다시 실행하는 형태로 처리한다. 즉 옵티마이저는 내부적으로 아래 2개의 쿼리를 실행하는 것과 비슷한 형태의 최적화를 실행하게 된다.

select gender, birth_date from employees where gender='M' and birth_date>="1965-02-01";
select gender, birth_date from employees where gender='F' and birth_date>="1965-02-01";

하지만 인덱스 스킵 스캔은 아래와 같은 제약 사항들이 있다.

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

이상훈

Problem Solving과 기술적 의사결정을 중요시합니다.

다음 포스트