인덱스는 데이터베이스에서 특정 데이터를 빠르게 조회하기 위해 사용하는 Key-Value 타입의 자료구조이다. 영어사전의 알파벳순 정렬을 예로 들 수 있다. 특정 영단어를 영어전전에서 찾으려 할 때 이미 알파벳 순으로 정렬되어 있기에 특정 영단어의 첫 알파벳 페이지로 가면, 영어사전의 처음부터 뒤지는 것보다 빠르게 찾을 수 있다.
물론 인덱스가 없는 데이터베이스에서도 데이터를 조회할 수 있지만, 데이터베이스의 크기가 크면 클수록 인덱스가 필요해진다. 인덱스는 데이터베이스의 크기가 커져도 빠르게 데이터를 조회할 수 있도록 도와준다.
그럼 모든 컬럼에 인덱스를 걸면 좋을까? 아니다. 인덱스를 효율적으로 사용한다면 매우 빠른 데이터 조회가 가능하고, 쿼리의 부하가 줄어들어 데이터베이스의 성능을 향상시킬 수 있지만, 인덱스 역시 하나의 데이터 덩어리이기 때문에 적절한 인덱스를 사용하지 않으면 오히려 데이터베이스의 성능을 저하시킬 수 있다.
그럼 어떤 기준으로 인덱스를 설정해야할까? 검색 조건에 주로 사용되고 카디널리티가 높은 컬럼을 인덱스로 설정하면 좋다. 카디널리티는 인덱스에 해당하는 컬럼 기준으로 테이블에서 유일한 레코드 개수를 의미한다. 카디널리티가 높을 컬럼에 인덱스를 걸면 그만큼 검색 대상이 줄어들기 때문에 빠르게 레코드에 접근할 수 있다.
때문에 인덱스를 효율적으로 사용하기 위해서는 인덱스의 동작 방식과 어떤 기준으로 인덱스를 설정해야하는지 알아야한다.
인덱스 알고리즘
인덱스 알고리즘은 B-Tree와 Hash Index으로 분류하여 구분할 수 있다. 이 중에서도 B-Tree 알고리즘은 Balanced Tree 알고리즘으로, 데이터베이스에서 가장 많이 사용되는 인덱스 알고리즘이다. 인덱스는 이러한 B-Tree 알고리즘을 사용하며 데이터가 정렬된 상태를 유지한다. 때문에 어떤 값에 대해서도 같은 시간복잡도로 데이터를 조회할 수 있다.
트리의 높이가 다른 경우 차이가 발생할 수 있지만, 일반적으로 B-Tree는 O(logN)의 시간복잡도를 가진다.
B-Tree
MySQL에서 사용하는 인덱스 알고리즘으로, 별다른 데이터의 변형을 가하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘이다. B-Tree는 최상위에 하나의 루트 노드가 있고, 그 아래에 여러 개의 브랜치 노드가 있으며, 가장 하위에는 리프 노드가 있는 형태이다.
해당 알고리즘의 장점은 어떤 값에 대해서도 같은 시간복잡도로 데이터를 조회할 수 있다는 것이다. 하지만 어떤 데이터를 조회를 하더라도 루트 노드부터 리프 노드까지 탐색해야하기 때문에, 데이터가 적은 테이블의 경우에는 인덱스를 사용하지 않는 것이 더 빠를 수 있다.
B+Tree
B+Tree는 B-Tree의 변형 알고리즘으로, B-Tree와 달리 리프 노드가 연결 리스트로 연결되어 있다. 또한 리프 노드에만 데이터가 저장되어 있고, 브랜치 노드에는 데이터가 저장되어 있지 않다. 이러한 구조로 인해 범위 검색에 특화되어 있으며, 데이터베이스에서 범위 검색이 많은 경우에 사용된다.
해당 알고리즘의 장점으로는 범위 검색에 특화되어 있어, 범위 검색이 많은 데이터베이스에서 빠른 검색 속도를 가진다. 또한 리프 노드가 연결 리스트로 연결되어 있기 때문에 범위 검색을 할 때, 리프 노드를 순회하면 되기 때문에 빠른 검색 속도를 가진다. 그러나 B-Tree에 비해 높이가 더 높아져서, B-Tree보다 더 많은 블록을 읽어야 한다. 또한, 리프 노드가 연결 리스트로 연결되어 있기 때문에, 범위 검색이 아닌 동등 비교 검색에는 B-Tree보다 느릴 수 있다.
Hash Index
Hash Index 알고리즘은 데이터를 해시 함수를 통해 해시값으로 변환하고, 이 해시값을 인덱스로 사용하는 알고리즘이으로, 특히 동등 비교 검색에 특화되어 있다. 하지만 값을 해시값으로 변환하기 때문에 범위 검색이나 정렬된 데이터를 조회하는데는 적합하지 않다. 주로 인메모리 데이터베이스에서 사용되는 인덱스 알고리즘이다.
인메모리 데이터베이스는 데이터를 메모리에 저장하고, 디스크에 저장하지 않는 데이터베이스이다. 예를 들어 Redis가 있다.
이러한 해시 인덱스의 장점으로는 실제 키 값과는 관계없이 해시값을 통해 데이터를 저장하기 때문에 데이터의 길이에 상관없이 일정한 시간복잡도를 가진다. 그래서 타 인덱싱 알고리즘에 비해 빠른 검색 속도를 가진다. 그러나 해시 인덱스는 각 해쉬값에 주소값을 지정하는 인덱스의 특성상, 범위로 조회하는 쿼리에는 적합하지 않다. 또한 데이터베이스의 크기가 커질수록 충돌이 발생할 확률이 높아지기 때문에, 충돌을 해결하는 방법이 필요하다.
인덱스 타입
인덱스의 타입은 크게 클러스터 인덱스와 세컨더리 인덱스로 나눌 수 있다. 클러스터 인덱스는 처음부터 정렬된 상태로 데이터가 저장되는 인덱스이며, 세컨더리 인덱스는 정렬되지 않은 상태로 데이터가 저장되는 인덱스이다. 영어사전을 예로 들면, 영어사전의 알파벳 순으로 정렬된 상태를 클러스터 인덱스라고 할 수 있고, 영어사전의 단어가 추가되는 순서대로 저장된 상태를 세컨더리 인덱스라고 할 수 있다.
각 인덱스의 특징에 따라 사용하는 경우가 다르다.
클러스터 인덱스
MySQL의 InnoDB 엔진은 기본적으로 클러스터 인덱스로 저장되는데, 클러스터 인덱스는 기본키가 비슷한 레코드끼리 묶어서 인접한 물리적 위치에 저장하는 것을 뜻한다. 그래서 클러스터형 인덱스 생성 시에는 데이터 페이지 전체가 다시 정렬되어 저장되기 때문에, 기본키 기반 검색이 매우 빠르다. 하지만, 이러한 정렬 방식 때문에 이미 대용량의 데이터가 저장된 상태라면 인덱스 생성은 시스템 부하를 일으킬 수 있다.
클러스터 인덱스는 한 개의 테이블에 하나만 생성할 수 있으며, 기본키에 대해서만 생성할 수 있다.
MySQL에서는 Primary Key가 있다면 Primary Key를 Clustered INDEX로, 없다면 UNIQUE 하면서 NOT NULL인 컬럼을, 그것도 없으면 임의로 보이지않는 컬럼을 만들어 Clustered Index로 지정한다.
세컨더리 인덱스
세컨더리 인덱스는 논 클러스터 인덱스(Non-Clustered Index)라고도 불린다. 클러스터 인덱스와는 다르게 후보키 기반으로 생성되는 인덱스로, 기본키와는 별개로 생성된다. 세컨더리 인덱스 생성 시에는 데이터 페이지는 정렬되지 않은 상태에서 별도의 인덱스 페이지에 인덱스가 생성된다. 별도의 인덱스 페이지에 인덱스가 생성하여 구성하기 때문에 클러스터와는 달리 자동 정렬을 하지 않는다. 때문에 클러스터형 보다 느리게 검색되지만, 데이터 삽입, 수정, 삭제에 대한 부하가 적다.
세컨더리 인덱스는 여러 개 생성할 수 있으나, 이를 남용할 경우 오히려 성능이 저하될 수 있다.
클러스터 + 세컨더리 인덱스
클러스터 인덱스와 세컨더리 인덱스를 함께 사용하는 방법도 있다. 클러스터 인덱스는 기본키 기반 검색에 특화되어 있고, 세컨더리 인덱스는 범위 검색에 특화되어 있기 때문에, 클러스터 인덱스와 세컨더리 인덱스를 함께 사용하면 더 빠른 검색 속도를 가질 수 있다.
클러스터 인덱스와 세컨더리 인덱스를 함께 사용할 경우, 세컨더리 인덱스는 클러스터 인덱스를 참조하는 형태로 사용된다.