[DB] 인덱스 진짜 이해하기

 

인덱스

인덱스는 데이터베이스 튜플의 검색 속도 향상을 위한 자료구조입니다.

인덱스는 우리 생활에서도 정말 많은 부분에서 사용됩니다. 만약 책의 원하는 부분을 찾기 위해 책의 첫 페이지부터 모든 페이지를 한 장씩 찾는다면 굉장히 오랜 시간이 소요됩니다. 하지만 책의 맨 앞에 있는 목차(인덱스)를 확인하면 원하는 부분을 쉽고 빠르게 찾을 수 있습니다.

 

 

인덱스를 사용하지 않는 컬럼으로 조회를 진행한다면 테이블 전체를 Full Scan 해야 하기 때문에 굉장히 오랜 시간이 소요됩니다. 하지만 인덱스를 사용하는 컬럼으로 조회를 한다면 테이블 전체를 Full Scan 하지 않고 인덱스라는 자료구조를 통해 조건에 맞는 데이터를 찾게 됩니다. 그 후 조건에 맞는 데이터를 찾았다면 해당 데이터의 주소값으로 바로 해당 튜플을 참조해서 값을 반환합니다.

 

인덱스 사용법

 

인덱스는 위와 같은 쿼리문으로 생성할 수도 있고 테이블을 생성하면서 한 번에 생성할 수도 있습니다. 인덱스를 생성하고 싶은 컬럼에 대해 인덱스를 생성할 수 있고 여러 컬럼을 하나의 인덱스로 생성할 수 있습니다. 인덱스를 생성하기 적절한 컬럼은 WHERE 조회 조건에 자주 포함되는 컬럼, 카디널리티(낮은 중복도)가 높은 컬럼일수록 좋습니다.

추가로 PK는 PRIMARY라는 이름으로 자동으로 인덱스 등록이 됩니다! 

 

인덱스의 장단점

장점

• 적절한 컬럼에 대해 인덱스를 생성하였다면 조회 성능이 크게 향상됩니다.
• Full Scan의 횟수가 줄어들기 때문에 시스템의 부하도 줄일 수 있습니다.

 

단점

• 인덱스를 생성하는 테이블 크기에 비례해서 인덱스 저장공간도 필요하기 때문에 필요 없는 컬럼까지 인덱스를 생성하는 것은 좋지 않습니다.
• 인덱스 자료구조는 일반적으로 B+tree 구조를 사용합니다. 이때 인덱스가 적용된 테이블에 CUD와 같은 튜플이 변경되는 작업이 일어난다면 해당 테이블의 인덱스 자료구조의 트리 구조 재조정이 발생하기 때문에 오버헤드가 발생할 수 있습니다.
• 인덱스를 잘못 사용한다면 오히려 성능이 저하되는 현상이 발생할 수 있습니다.

 

인덱스 자료구조

 

이런 인덱스를 구현하기 위해 다양한 자료구조를 사용할 수 있습니다. 대표적으로 해시 테이블 자료구조와 B+Tree 자료구조를 사용해서 구현합니다. Mysql의 InnoDB엔진은 B+Tree를 채택해서 구현되었습니다. 참고로 InnoDB는 Mysql에서 사용되는 스토리지 엔진이며 CRUD 작업에서 사용됩니다.

 

해시 테이블

해시 테이블 자료구조는 Key-Value 데이터를 저장하는 자료구조로 이상적인 조건에서는 시간복잡도가 O(1)로 아주 빠릅니다. 하지만 데이터베이스 인덱스에서 해시 테이블을 사용해서 구현하는 경우는 드뭅니다.

왜냐하면 해시 테이블 자료구조는 등호 연산에만 특화되어 있습니다. 그렇기 때문에 범위 검색이 자주 사용되는 테이블에는 적합하지 않고 카디널리티가 낮은 컬럼에 생성된 인덱스는 해시 충돌이 발생하여 성능이 저하될 여지가 있습니다.

 

B+Tree

B+Tree는 일반적으로 데이터베이스 인덱스를 구현하는 대표적인 자료구조입니다. BTree의 개선된 자료구조라고 생각할 수 있습니다. BTree는 왼쪽 자식노드는 부모노드의 값보다 작은 값, 오른쪽 자식노드는 부모노드보다 큰 값이 저장되는 자료구조인 이진트리의 특성에서 자식 노드를 2개 이상으로 가질 수 있는 자료구조입니다.

 

BTree를 개선시킨 B+Tree는 아래와 같은 특성을 가지고 있습니다.

• 리프노드에만 값을 가지고 있습니다. 나머지 브랜치 노드들은 리프노드 탐색을 위한 값을 갖습니다.
• 모든 리프노드들은 LinkedList로 연결되어 있습니다.

데이터베이스의 검색 조건에는 범위 연산이 많이 필요합니다. 이러한 이유 때문에 리프노드들은 LinkedList로 연결되어 특정 범위에 대한 데이터를 조회 시 성능을 최적화할 수 있습니다.

 

B+Tree는 O(log n) 정도의 시간복잡도를 가지며 언듯 보면 해시 테이블보다 성능이 떨어진다고 생각할 수 있지만 인덱스를 구현하는 자료구조에서는 B+Tree가 아주 적합합니다.

 

 

MySQL InnoDB 엔진에서는 위와 같은 B+Tree를 사용합니다. InnoDB에서는 같은 레벨의 노드들은 LinkedList가 아닌 Double LinkedList로 연결되어 있습니다.

 

B+Tree 탐색 방법

간단하게 B+Tree로 구현된 자료구조에서 특정 범위의 값을 찾는 방법을 알아보겠습니다.

 

이렇게 구현되어 있는 B+Tree에서 5~8 범위의 값을 찾는다고 가정해 보겠습니다. B+Tree는 리프노드에만 값을 가지고 있고 나머지 브랜치 노드들은 리프노드의 값을 찾기 위한 정보를 가지고 있습니다.

 

먼저 5~8이라는 범위의 값을 찾기 위해 5부터 탐색해 보겠습니다. 루트 노드의 조건을 확인한 후 왼쪽 자식 노드로 내려갑니다. 해당 노드의 조건을 확인한 후 오른쪽 자식 노드로 내려갑니다.

 

조건에 해당하는 값을 찾았습니다. 이제 5부터 8까지의 범위에 값을 찾기 위해 리프노드끼리 연결되어 있는 리스트를 따라 오른쪽으로 이동하며 5~8이라는 값을 찾습니다.

 

이렇게 B+Tree를 사용한다면 BTree보다 범위 검색에 특화되어 있기 때문에 데이터베이스 인덱스를 구현하는 자료구조로 아주 적합합니다.

 

복합 인덱스 검색 방법, 커버링 인덱스

복합 인덱스

인덱스를 생성할 때 여러 컬럼을 하나의 인덱스로 만들 수 있습니다. 이것을 복합 인덱스라고 합니다. 복합 인덱스는 선언 순서가 굉장히 중요합니다.

 

CREATE INDEX multi_column_idx ON tb_student (class_id, std_id);

 

위의 쿼리를 날려 인덱스를 생성했다고 가정해 봅시다.

 

이렇게 복잡 인덱스가 생성되었는데요, 복합 인덱스를 생성할 때 먼저 왼쪽에 적어준 컬럼을 기준으로 정렬을 합니다. 왼쪽 컬럼에서 중복되는 부분이 있다면 해당 부분에서 오른쪽 컬럼을 기준으로 정렬을 진행합니다.

 

그렇기 때문에 복합 인덱스는 여러 컬럼을 모두 사용하는 조건(AND)이 있는 조회에서는 좋은 성능을 발휘합니다. 하지만 복합 인덱스를 사용했다고 해서 복합 인덱스에 포함된 각각의 컬럼에 대한 조회 성능이 모두 향상되는것은 아닙니다.

 

복합 인덱스를 생성하면 왼쪽 컬럼을 기준으로 정렬이 되기 때문에 왼쪽 컬럼에 대한 단일 조건 검색에서는 해당 복합 인덱스를 사용할 수 있습니다. 하지만 오른쪽 컬럼에 대한 단일 검색을 진행한다면 해당 복합 인덱스를 사용해도 성능상 이점을 얻을 수 없습니다. 그렇기 때문에 인덱스 설계시 복합 인덱스는 컬럼 순서를 주의해서 사용해야 합니다.

 

커버링 인덱스

인덱스를 사용하여 조회를 할 때 조회하려는 컬럼들이 인덱스에 모두 포함이 되어있는 인덱스를 커버링 인덱스라고 합니다.

 

어떤 데이터를 인덱스를 활용해서 조회하려 할 때 조회하려는 컬럼이 인덱스에 모두 포함이 되어있는 커버링 인덱스라면 굳이 테이블에 접근해서 튜플의 정보를 가져오지 않고 인덱스로 커버가 가능하기 때문에 조회 성능이 더 좋습니다.

 

인덱스를 잘 사용하는지 확인하기

특정 테이블의 컬럼에 인덱스를 생성하였는데 조회 쿼리를 할 때마다 데이터베이스에서 내가 설정한 인덱스를 잘 사용하고 있는지 궁금할 수 있습니다. 이때 조회 쿼리 앞에 EXPLAIN 키워드를 붙이면 옵티마이저가 쿼리를 어떻게 실행할지에 대한 실행계획을 볼 수 있습니다.

 

 

위의 사진에서의 실행계획을 확인해 보면 테이블(table) tb_member에서 해당 조회쿼리에 대해 사용할 수 있을만한 인덱스(possible_key)는 PRIMARY이고, 실제로 사용할 쿼리(key는 PRIMARY라는 것을 확인할 수 있습니다.

 

특정 인덱스를 사용하게 하고 싶다면

 

조회 시 특정 인덱스를 사용하게 하고 싶다면 USE INDEX (인덱스명) 키워드를 사용하면 됩니다. 하지만 해당 키워드는 옵티마이저가 이 인덱스 쓰면 Full Scan보다 안 좋을 것 같은데; 싶으면 다른 인덱스를 사용할 수도 있습니다.

 

하지만 그래도 꼭 특정 인덱스를 쓰게 하고 싶으면 FORCE INDEX (인덱스명) 키워드를 사용할 수 있습니다.

 

하지만 옵티마이저가 추천한 인덱스를 사용해서는 도저히 검색을 진행할 수 없을 때는 다른 인덱스를 사용할 수 있습니다.

 

마무리 총총

인덱스는 데이터베이스에서 조회 시 검색 속도를 향상해 주는 자료구조입니다. MySQL의 InnoDB에서는 BTree의 개선된 자료구조인 B+Tree 자료구조로 인덱스를 구현하고 있습니다.

또 인덱스를 무분별하게 생성한다면 저장공간을 많이 차지하고 데이터 변경 시마다 트리 재조정 비용 등 인덱스를 사용하는 것보다 성능이 떨어질 수 있습니다. 때문에 적절한 컬럼에 인덱스를 필요한 만큼만 생성해 사용하는 것이 인덱스의 장단점 특성의 트레이드오프를 맞춰 좋은 성능의 애플리케이션을 개발하는 첫 단추가 될 수 있을 것입니다.