1. B+Tree
MySQL의 대표적인 스토리지 엔진인 InnoDB의 기본 인덱스 타입으로, 직선으로의 탐색이 아닌 트리의 탐색으로 평균적으로 log(N)의 시간안에 참조가 가능하다는 장점이 있다.
하지만 트리이기 때문에 연속적인 값을 검색하는 range search를 위해서는 double linked list를 활용하는 등 추가적인 자료구조 및 연산이 필요하고 skew가 발생하면 효율이 떨어진다는 단점이 존재한다.
트리의 모든 노드가 레코드인 B Tree와는 다르게, 모든 레코드가 맨 하단 노드에 정렬되어 있고, 키들만이 내부 블록에 저장되는 형태로, 블록 지향적인 검색을 효율적으로 할 수 있다.
2. Hash Index
Memory Engine의 기본 인덱스 타입으로, 해쉬 테이블을 이용하여 O(1)이라는 빠른 시간에 데이터를 읽을 수 있고, 인덱스의 크기가 작다는 장점이 있지만 정렬과 그룹화가 안된다는 단점 또한 존재한다. 해쉬를 이용하기 때문에 충돌이 일어날 수 있으며, 이 충돌이 검색 효율을 저하하는 원인이 된다. 그렇기 때문에 해쉬 함수의 결과 범위를 높여 충돌을 방지하는 방법 등으로 시스템 리소스와의 교환으로 극복이 가능하다.
또한 InnoDB의 해쉬 인덱스의 활용으로는 Adaptive hash index기능이 있는데 이 기능은 인덱스에서 값이 자주 사용된다면 새로운 해쉬 인덱스를 생성하여 참조를 지원해주는 기능으로 빠른 검색이 가능해진다.
3. full-text index
MyISAM와 InnoDB(5.6.4 이후부터)에서 지원하는 인덱스이다. 이 인덱스는 문자열을 직접 비교하지 않고 키워드를 찾음으로써 더 빠른 검색이 가능하고, 이러한 특징을 바탕으로 inverted index에 사용된다.
4. Spatial Data Index(R-Tree)
MyISAM이 지원하는 Spatial Data Index(R-Tree)는 공간 데이터를 다루는데 활용될 수 있는 인덱스이다.
이와 같이 각 인덱스는 고유의 특성을 갖고 있고, 이에 따라 장단점이 분명하게 존재한다. 또한 지원 가능한 스토리지 엔진 및 MySQL버전이 제한되어 있다. 그렇기 때문에 구현하고자 하는 시스템의 특성을 이해하고 자신의 MySQL의 버전과 테이블의 스토리지 엔진을 고려하여 인덱스를 모델링 하는 것과 것이 중요하다.
References
https://www.programmersought.com/article/55381027255/ ( ProgrammerSought / MySQL index )
https://mariadb.com/kb/en/storage-engine-index-types/ ( MariaDB / Storage Engine Index Types )
https://ko.wikipedia.org/wiki/B%2B_%ED%8A%B8%EB%A6%AC ( 위키백과 / B+ 트리 )
https://hoing.io/archives/12610 ( Hoing / MySQL Hash Index)
https://tech.kakao.com/2016/04/07/innodb-adaptive-hash-index/ ( KakaoTech / MySQL InnoDB의 Adaptive Hash Index 활용)
숭실대학교 소프트웨어학부 : Database (2150013203) / 7강