(MySQL) Index 개념과 종류

훈수/저작권 관련 지적 환영합니다 - 댓글 또는 audgnssweet@naver.com

 

인덱스

---

인덱스

인덱스는 데이터베이스 분야에 있어서 테이블에 대한 동작의 속도를 높여주는 자료 구조를 일컫는다. 인덱스는 테이블 내의 1개의 컬럼, 혹은 여러 개의 컬럼을 이용하여 생성될 수 있다. 고속의 검색 동작뿐만 아니라 레코드 접근과 관련 효율적인 순서 매김 동작에 대한 기초를 제공한다. -위키백과-

인덱스를 사용하는 이유는 빠른 검색을 보장하기 위함입니다.

 

인덱스를 설정하지 않고 그냥 검색을 한다면 매번 테이블 전체를 풀 스캔 하여 조건에 맞는 데이터를 검색합니다.

몇만 건, 몇십만 건 정도면 크게 문제가 되지 않을 수도 있지만 데이터가 수백수천만 건이 되고 요청 트랜잭션 수도 많아진다면 성능 면에서 큰 저하가 있을 것입니다.

 

인덱스를 통한 데이터로의 빠른 접근이 속도가 생명인 IT 애플리케이션에서 매우 중요한 것이라고 할 수 있습니다.

---

MySQL이 지원하는 index

MySQL에서 지원하는 인덱스는 B+Tree와 Hash가 있습니다.

---

B+tree

MySQL에서 사용하는 B+tree에 대해서 이해하려면, 먼저 B-tree에 대해서 알아야 합니다.

왜냐하면 B+tree는 B-tree에서 한 단계 발전한 버전이기 때문입니다.

B-tree는 이름에서도 알 수 있듯이 자료구조 중 tree구조로 이루어져 있습니다.

Binary search를 떠올려보면 검색 속도가 O(logN)으로 매우 빨랐던 것을 떠올릴 수 있습니다.

어떻게 이게 가능한가? 하면 ‘이미 데이터가 정렬되었기 때문’입니다

아래 그림을 보겠습니다.

위 그림이 B-Tree의 구조입니다. 기존의 BST와 연관하여 생각하면 구조를 빠르게 파악할 수 있습니다.

여기서 핵심은 트리 구조로 이미 데이터를 정렬해두었기 때문에 검색 속도가 빨라진다는 것입니다.

 

본격적으로 B+Tree에 대해 알아보겠습니다. 먼저 아래 그림을 보겠습니다.

B+tree는 B-tree에서 한 노드에 키를 여러 개 담을 수 있어 트리의 높이가 낮아지고,

리프 노드끼리 이중 연결 리스트를 통해 연결되어 있어

연결 리스트를 통한 선형 탐색으로 연속된 데이터 탐색에서의 단점까지도 극복한 자료구조입니다.

 

B+tree의 핵심은 ‘트리 구조로 이미 정렬된 데이터’를 ‘최대한 높이를 낮추어 탐색 시간을 줄이고’ ‘리프 노드끼리 연결 리스트로 연결하여 순차적 탐색까지 빠르게 한’ 자료구조라고 할 수 있습니다.

물론 데이터가 index node에 직접 들어있는 것은 아니고 바로 참조할 수 있도록 참조값이 들어있습니다.

 

B+tree에 대해서 알아보았습니다.

---

Hash

hash에 대해 간략하게 알아보겠습니다.

Hash table은 위 구조처럼 생겼습니다.

내부적으로 hash함수를 이용하여 데이터를 해싱, 겹치기 쉽지 않은 특정한 값을 도출해내어

다음번에 해당 데이터에 접근하려고 할 때 조건값을 동일한 함수로 hashing 하여 일치되는 bucket으로

‘단 한번’에 찾아가는 자료구조입니다.

 

hashing이 단 한 번에 찾아간다는 점에서는 B+tree보다 검색 속도가 조금 더 빠를 수는 있지만,

hash table의 크기 문제라던가, 데이터가 많아졌을 때 동일한 hash값이 나오는 경우 등을 생각했을 때

문제점이 없지 않은 구조입니다.

---

Storage engine별 index

 

hash index는 = equal 검색을 매우 빠르게 할 수 있습니다 (위에서 설명한 것처럼 hash값으로 한 번에 찾아가기 때문에) 그러나 hash값의 특성상 대소 비교나, 정렬 등에서는 사용이 불가능합니다.

 

btree는 hash보다 equal로 찾아가는 연산은 다소 느릴 수 있지만 대소 비교 및 정렬에서도 인덱스를 활용할 수 있다는 점이 매우 큰 장점입니다. 제 생각에는 대소 비교 및 정렬에서도 인덱스를 활용할 수 있다는 점이 MySQL에서 hash 말고를 중점적으로 사용하는 가장 큰 이유인 것 같습니다.

 

또한 memory나 heap 등의 비교적 크기가 작은 DB를 활용할 때 hash가 쓰이는 경우가 있는 것 같습니다.

---

최근 InnoDB의 index

최근에 MySQL에서 default로 제공하는 storage engine이 InnoDB입니다.

InnoDB는 기존의 MyISAM등과 비교해서 많은 장점들이 있기에 널리 사용되고 있습니다.

MySQL에서 가장 많이 사용되는 InnoDB에서는 Index를 어떤 식으로 활용하고 있는지 알아보겠습니다.

 

InnoDB에서는 btree만 쓰는 것이 아니라 btree에 hash를 적절히 섞은 형태 (InnoDB Adaptive Hash Index)를 활용한다고 합니다.

 

기본적으로 index를 다는 column에 대해서는 Btree로 구성하고, 자주 사용되는 데이터만(모든 데이터 X)을 내부 알고리즘으로 판단하고 해시값을 생성하여 index로 만들고 활용한다고 합니다.

 

자주 사용되는 데이터를 hashing으로 한 번에 접근할 수 있도록 하면 성능을 많이 올릴 수 있기 때문인 것 같습니다.

---

MySQL에서 Index 종류에 대해서 알아보았습니다.

 

참고 출처

http://jason-heo.github.io/mysql/2014/03/05/char13-index-types.html

https://zorba91.tistory.com/293

https://ju-hy.tistory.com/107

https://tech.kakao.com/2016/04/07/innodb-adaptive-hash-index/