인덱스란?
인덱스는 특정 컬럼값을 기준으로 row(데이터)를 빠르게 탐색할 수 있는 자료구조로 insert, update, delete의 성능을 희생하고 select의 성능을 높이는 데 이용합니다. 인덱스의 가장 큰 특징은 인덱스를 설정한 컬럼 기준으로 데이터를 정렬해 관리한다는 것입니다. 여기서 데이터의 정렬이 왜 빠른 조회에 도움이 되는지 궁금하실 것 같습니다. (저도 인덱스를 학습할 때 궁금해 했었습니다)
이를 간단하게 예시를 통해서 살펴보겠습니다.
숫자 1부터 10까지가 랜덤으로 섞인 리스트와 숫자 1부터 10까지가 오름차순으로 정렬된 리스트가 있다고 하겠습니다. 여기서 우리가 7을 찾는다고 할 때 랜덤으로 섞인 리스트의 경우에는 처음부터 탐색할 수밖에 없습니다. 운이 좋으면 원하는 데이터를 한번에 찾을 수 있겠지만 가장 마지막에 있게 된다면 최대 10번의 탐색이 필요할 것입니다. 반대로 정렬된 리스트에서는 중앙값을 통해 찾으려는 범위를 줄여 나가면서 탐색 횟수를 줄여나가 두 번만에 7을 찾을 수 있습니다.
이를 DB에 반영해 보면 데이터가 랜덤으로 저장되어 있다면 원하는 데이터를 찾을 때 테이블의 처음부터 끝까지 탐색해야 하지만 인덱스와 같이 데이터가 정렬되어 있다면 탐색범위를 줄이고 데이터를 찾을 수 있어 조회 성능을 높일 수 있습니다. 그래서 조회 성능을 높이는 데 인덱스를 이용합니다.
하지만 인덱스도 결국에는 데이터 파일(MySQL에서는 page 단위로 관리)이기에 새로운 데이터가 추가, 변경, 삭제 시에 관리해야 할 포인트가 늘어나는 것입니다. 특히 인덱스는 데이터를 정렬해 둔 상태를 유지해야 하기에 데이터 쓰기 작업의 경우 데이터만 추가되는 것이 아닌 정렬과정이 매번 발생하는 오버헤드가 존재합니다.
인덱스는 어떻게 구현되어 있는가?
인덱스의 데이터는 다양한 자료구조를 기반으로 관리될 수 있으며 일반적으로 hash 및 B-Tree 자료구조 기반으로 관리됩니다. MySQL의 innoDB의 경우 hash와 B-tree 기반의 인덱스를 모두 이용하며 대부분의 인덱스 데이터는 B-tree 자료구조를 기반으로 합니다. hash 인덱스와 B-tree 인덱스에 대해 각각 알아보겠습니다.
위의 그림과 취미 정보를 담는 Member table을 활용하여 각각의 인덱스에 데이터가 어떻게 저장되고 관리되는지 알아보겠습니다.
hash기반 인덱스
인덱스의 핵심은 정렬이라고 했지만 hash 인덱스의 경우 데이터를 정렬해서 관리하는 것이 아닌 key-value 형태로 데이터를 관리합니다. key에는 사용자가 지정한 컬럼의 해시의 값(현재 그림에서는 이름 컬럼)을 저장되고 value에는 실제 데이터가 있는 disk 주소값을 가지고 있습니다.
SELECT 이름, 주민등록번호,취미 FROM Member WHERE 이름 = '김철수';위의 쿼리와 같이 이름 컬럼 기반으로 동등 검색을 하는 경우 ‘김철수’ 값을 해시 함수로 변환하고 이를 인덱스 테이블 내 key 값과 비교해 일치하면 레코드 주소를 활용해 실제 데이터를 불러옵니다. 이를 통해 Disk 내 모든 데이터에 접근할 필요없이 hash key 값을 이용하여 데이터에 접근하여 Disk i/o를 줄일 수 있습니다. 다만 인덱스를 생성하는 과정에서 해시 충돌이 발생한다면 데이터를 조회하는 과정에서 Disk i/o가 늘어날 수 있습니다.
앞선 조회 과정에서 보았듯이 hash 인덱스는 동등 비교(==)에서는 빠른 조회시간을 가집니다. 반면 다른 인덱스와 다르게 정렬된 데이터를 관리하는 것이 아니기에 범위 조회(<, >)와 데이터 정렬 과정에서는 Optimizer가 해당 인덱스를 활용하지 않습니다.
B-Tree기반 인덱스
B-Tree기반 인덱스에 대해서 알아보기에 앞서서 먼저 B-Tree 자료구조에 대해서 간단하게 알아보겠습니다.
B-Tree는 이진 트리를 확장한 자료구조로 이진트리와 다르게 하나의 노드가 2개의 자식노드를 가지는 것이 아니라 여러개를 가질 수 있습니다. 같은 량의 데이터에 대하여 자식 노드의 수가 늘어남에 따라 트리의 전체 높이가 낮아져 빠른 탐색 속도를 가질 수 있다는 특징이 있습니다.
B-Tree 기반의 인덱스는 root → branch → leaf 페이지로 관리가 됩니다. root 페이지와 branch 페이지에는 인덱스 키와 자식 노드의 정보를 가지고 있고 leaf 페이지의 경우 인덱스의 종류에 따라 가지고 있는 값이 다릅니다. 클러스터링 인덱스(PK 기반 인덱스)에 경우에는 실제 데이터를 가지고 있지만 세컨더리 인덱스의 경우에는 PK 정보를 가지고 있습니다.
B-tree 인덱스는 hash 인덱스와 다르게 데이터를 정렬해서 관리합니다. 그렇기에 B-Tree 인덱스의 경우 동등 비교(=)와 범위 조회(<, ≤, >, ≥, between)에 이용되며 빠른 성능을 가집니다. 그렇다고 해서 모든 조회에서 인덱스가 활용되는 것은 아닙니다. 다음의 예시를 보겠습니다.
SELECT 이름, 주민등록번호, 취미 FROM Member WHERE 이름 LIKE '%민%'; 해당 쿼리는 이름 내 “민”이 포함된 데이터를 불러오는 것입니다. “민”으로 시작하는 데이터는 인덱스를 찾을 수 있겠지만 중간 혹은 마지막에 “민”이 포함된 정보를 찾기 위해서는 결국 모든 데이터를 확인해야 하기에 인덱스를 활용하지 못합니다.그렇기에 첫글자가 아닌 중간 혹은 마지막 글자로 찾은 요청의 성능 향상시키고자 해당 컬럼에 인덱스를 추가하여도 개선이 되지 않으니 성능 개선 시 유의해야합니다.
이 두 인덱스를 정리해보면 hash 인덱스는 b-tree 인덱스에 비해 동등비교에서는 빠른 성능을 내지만 범위 연산에 활용하지 못하는 방면 b-tree 인덱스는 범위 연산에서도 빠른 조회를 능력을 가지고 있습니다. 그렇기에 실제 MySQL의 innoDB에서는 두 방식의 인덱스를 모두 활용하고 있습니다. b-tree 인덱스는 사용자 요청에 따른 필요한 데이터를 빠르게 찾는데 활용되고 hash 인덱스의 경우는 데이터를 찾는데 자주 활용되는 인덱스를 관리해 조회 성능을 높입니다.
마무리
- 인덱스는 데이터를 정렬해서 관리해 조회 성능을 높이는 자료구조 입니다.
- 인덱스 내 데이터는 hash, b-tree 자료구조를 통해 관리됩니다.
- hash 인덱스는 동등 비교는 가능하지만 범위 비교를 불가
- b-tree 인덱스는 동등 비교 및 범위 비교가 가능하지만 중간 글자나 마지막 글자를 통한 검색 불가능
- MySQL의 innodb에서는 어느 한 방식의 인덱스만 활용하는 것이 아닌 두 방식의 인덱스를 활용
그 동안 인덱스를 이용하면 성능이 개선된다는 것을 직접 경험해보면서 알고 있었지만 내부 구조가 어떻게 되어있고 어떤 동작원리를 가지고 있는지 이번 기회에 글로 정리해보면서 더 이해가 잘 된 것 같습니다. 더불어 자주 사용하는 MySQL의 내부 동작 과정도 알 수 있어서 의미있는 시간이었습니다.
다음에는 MySQL을 통해서 실제 인덱스를 활용해보면서 인덱스 사용시 유의점에 대해서 정리해보고자 합니다.
