[혼공S] 5주차 - 인덱스

👨‍💻 개인 공부 기록용 블로그 입니다.
💡 틀린 내용이나 오타는 댓글, 메일로 제보해주시면 감사하겠습니다!! (__)

Introduction

2주간 정말 많은 일들이 있었다… 이건 차차 회고로 적어보기로 하고, 오늘의 주제는 인덱스(Index) 이다. 개인적으로 정말 PTSD오는 주제이다. 관련해서 면접에서 탈탈 털렸던 내용들이기 때문이다. 인덱스는 사용 경험도 중요하지만, 그 기저에 깔린 이론들을 정말 잘 알아야 하는 것 같다. 꼬리 질문 몇 개만 던져도 알고 쓰는지 모르고 쓰는지 면접자를 털기 정말 좋은 내용들이기 때문이다. 또한, 깊게 들어가면 면접자가 고급 자료구조에 대해 잘 이해하고 있는지를 판별할 수 있는 이정표가 될 수 있다고 생각한다. 사족이 좀 길었는데 바로 시작해보자.

인덱스의 종류

인덱스는 단어 뜻 그대로 색인, 무언가를 빨리 찾아보기 위해 만드는 낱말 표 같은 것이다. 데이터베이스에서는 데이터를 찾는 쿼리인 SELECT의 속도를 높이기 위해 사용된다. 이런 인덱스에도 2가지 종류가 있다. 바로 클러스터형 인덱스(Clustered Index) 와 보조 인덱스(Secondary Index) 이다. 단어만 들어서는 잘 매치가 되지 않는다. 클러스터형 인덱스는 기본키(PK)로 지정된 열에 자동으로 걸리는 인덱스이며 자동으로 정렬된다. 즉, 테이블 당 하나만 만들 수 있다. 반대로 보조 인덱스는 여러 개를 만들 수 있다. 고유 키로 지정하면 자동으로 생성되며, 자동으로 정렬되지는 않는다.

책에서는 클러스터형 인덱스를 사전에, 보조 인덱스를 책 맨 뒤에 있는 색인에 비유했는데, 어느정도 적절한 비유인 것 같다. 왜 이렇게 비유했는지는 이따 원리에 대해 알아보면서 자세히 살펴보자.

인덱스 사용법

인덱스를 만들기 위해서는 다음과 같은 쿼리문을 실행한다.

CREATE INDEX index_name ON table_name(column_name);

위 명령은 table_name 테이블의 column_name 열에 대해 index_name이라는 이름의 인덱스를 생성한다. 생성된 인덱스는 자동으로 적용되며, SELECT 쿼리가 던져질 때 데이터베이스 엔진이 인덱스를 사용할지 말지 결정하게 된다. 인덱스를 활용함으로써 더 빠른 처리가 가능한 경우에만 자동으로 사용하게 된다.

만약 인덱스를 잘못 생성했다면, 아래와 같은 쿼리문을 실행하여 삭제할 수 있다.

DROP INDEX index_name ON table_name;

어떻게 확인하지?

아래와 같은 쿼리의 결과를 캡쳐한 것이다. 이는 테이블에 이미 존재하는 인덱스를 확인하는 명령이다.

SHOW INDEX FROM member;

Index_type 란을 보면 B-Tree로 적혀있는 것을 볼 수 있다. 이는 해당 Column으로 인덱스가 생성되어 있다는 뜻이다. Key_name이 PRIMARY로 되어 있으니 클러스터형 인덱스 로 생성되어 있음을 유추할 수 있다.

언제 활용해야 좋을까?

SELECT 쿼리의 속도를 올려준다고 해서 막 갖다 쓰면 되는 것은 절대 아니다. 당연하게도 과유불급의 이치가 적용된다. 인덱스를 활용하기 좋은 상황 몇 가지를 알아보자.

1. WHERE 절에 자주 사용되는 Column

인덱스는 WHERE 절에 자주 사용되는 컬럼에 적용하면 매우 효과적이다. 예를 들어, 대규모 테이블에서 특정 조건에 맞는 데이터를 검색해야 하는 경우, 해당 조건에 맞는 열에 인덱스를 설정하면 검색 속도를 크게 향상시킬 수 있다.

1. 중복이 적고 선택도가 높은 Column

인덱스는 중복이 적고 선택도가 높은 컬럼에서 가장 큰 효과를 발휘한다. 선택도가 높다는 것은, 해당 컬럼에 서로 다른 값이 많이 존재한다는 것을 의미하며, 이는 인덱스의 효율성을 높이는 요인이 된다.

1. 조회가 자주 되면서 변경이 적은 Column

인덱스는 데이터의 검색 성능을 향상시키지만, 데이터가 수정, 추가, 삭제될 때마다 인덱스도 업데이트되어야 하므로 인덱스가 설정된 컬럼에 대해 변경이 잦은 경우 성능이 저하될 수 있다. 따라서, 조회 빈도가 높고 변경이 적은 컬럼에 인덱스를 설정하는 것이 이상적이다.

1. 정렬이 필요한 경우

데이터베이스가 데이터를 정렬된 상태로 유지할 수 있기 때문에, ORDER BY나 GROUP BY 구문에서 자주 사용되는 컬럼에 인덱스를 설정하면 정렬 작업이 훨씬 빨라진다. 다만, 모든 정렬 가능한 컬럼에 인덱스를 설정하는 것은 바람직하지 않으며, 벤치마크를 통해 실제로 성능 개선이 이뤄지는 경우에만 설정하는 것이 좋다.

1. 조인(Join)에 자주 사용되는 컬럼

데이터베이스에서 여러 테이블을 조인할 때, 조인 조건에 사용되는 컬럼에 인덱스를 설정하면 성능을 크게 개선할 수 있다. 조인 조건에 인덱스가 걸려 있으면, 데이터베이스는 각 테이블에서 필요한 데이터를 더 빠르게 찾아 결합할 수 있다.

인덱스 동작 원리

SELECT 쿼리를 처리하기 위하여 특정 테이블에서 조건에 맞는 데이터를 가지고 오려면, 어떻게 해야 효율적일까? 표 형태로 그대로 저장된 상태라면 아마 처음부터 하나하나 조건에 맞는지 확인해봐야 할 것이다. 하지만 이런 풀 스캔은 너무 비효율적이다. 데이터가 10억개 있다면 조회 자체를 10억번 해봐야 하기 때문이다.

업다운 게임을 아는가? 그 게임처럼 이진탐색을 활용하면, 데이터가 10억개더라도 약 21번의 조회로 원하는 데이터를 찾을 수 있다. 이진탐색의 원리를 잘 활용할 수 있는 이진 탐색 트리(Binary Search Tree)를 사용하면 이 과정을 자료구조로써 추상화하여 사용할 수 있다. 그렇다면 데이터베이스도 이런 방식을 차용해서 사용하고 있을까? 결론부터 이야기하자면 아니다.

이진 탐색 트리는 치명적인 단점이 있다. 트리가 불균형해지면 풀 스캔이나 다를 바 없어진다. 이를 해결하기 위하여 균형 이진트리를 활용하기도 하지만, (실제로 C++의 STL은 set과 map 같은 구조를 균형 이진트리의 한 종류인 레드블랙트리로 구현한다.) 트리 높이까지 줄일 수 있는 더 효율적인 방법이 존재한다. 트리 높이를 줄이는 것이 생각 이상으로 중요하다. 컴퓨터의 여러 I/O를 살펴보면 디스크 I/O가 가장 느리고 비효율적인데, 데이터베이스는 이 디스크에다가 데이터를 읽고 쓴다. 즉, 디스크 I/O 횟수는 트리 높이에 비례하게 되며, 트리 높이가 작을수록 데이터베이스를 더 효율적으로 사용할 수 있는 것이다.

B-트리에서는 한 노드에 여러 데이터를 담을 수 있기 때문에, 이진 탐색 트리보다 높이가 낮을 수 밖에 없다. 하지만 탐색 과정 자체는 이진 탐색 트리와 비슷하면서도 더 효율적이기 때문에 데이터베이스의 인덱스에 사용된다. B-트리에 대한 자세한 내용은 따로 작성하겠다.

정리하면 데이터베이스의 인덱스는 SELECT 쿼리의 효율성을 위해 사용하는 것이고, 이는 B-트리 라는 균형 트리로 구성된다. 하나의 노드에 여러 데이터가 있을 수 있기 때문에 이진 탐색 트리는 아니다. 이 구조는 데이터를 탐색하는 데에는 탁월한 성능을 보여주지만, 수정/삭제/추가 시에는 트리의 재편성이 일어날 수 있기에 다소 비효율적이다.

“인덱스”를 만든다는 것

앞에서 클러스터형 인덱스와 보조 인덱스로 나뉜다고 설명을 했는데, 두 인덱스는 같은 구조를 활용하지만 실제로 동작하는 방식은 다르다. 클러스터형 인덱스는 데이터를 “실제로” 정렬한다. 보조 인덱스는 데이터로의 “참조”를 정렬한다. 즉, 데이터를 직접 정렬하는 것이 아니라 페이지 번호 + #위치를 통해 실제 데이터에 접근할 수 있도록 참조를 만들어 놓고, 그 참조들을 정렬한다. 따라서 보조 인덱스는 추가적인 공간 수요가 있다.

MySQL의 스토리지 엔진인 InnoDB를 기준으로 보면, 데이터를 페이지(Page) 단위로 관리한다. 즉, 트리의 노드를 한 페이지로 본다면, 데이터의 삽입이나 삭제로 인하여 페이지 수에 변화가 생길 때 추가 분할/병합 작업이 필요하다. 이것이 인덱스를 무분별하게 사용했을 때 오히려 비효율적인 이유이다.

사실은 B+트리로 동작한다.

어떻게 확인하지? 파트에서 인덱스는 B-트리로 만들어진다는 것을 확인했다. 하지만 실제로는 좀 더 개선된 B+트리 라는 구조를 사용한다. B+트리도 B-트리와 마찬가지로 따로 글을 써도 될 정도이니, 나중에 다시 한 번 정리해보려고 한다. 지금은 간단하게만 정리해보자.

B+트리는 B-트리의 변형된 형태로, 두 자료구조는 유사해 보이지만, 결정적인 차이점이 존재한다. B-트리는 각 노드가 키와 데이터 쌍을 포함하고 있으며, 모든 노드(리프 노드 포함)에 데이터가 저장될 수 있다. 반면에 B+트리는 데이터는 오직 리프 노드에만 저장되며, 내부 노드는 키만을 가지고 트리 구조를 유지한다. 이로 인해 B+트리는 더 많은 키를 내부 노드에 저장할 수 있어 트리의 높이를 줄일 수 있다.

리프 노드에만 데이터가 존재하게 함으로써, 데이터끼리 연결시켜 놓을 수 있기 때문에 범위 검색에서 매우 효율적이다. B-트리는 범위 검색을 위해 매번 루트부터 조건에 맞는 노드들을 찾아야하지만, B+트리는 맨 처음 노드만 찾고 데이터끼리 이어진 링크를 따라가다 보면 범위 내 모든 데이터를 찾을 수 있다.