[Database]MySQL 인덱스

INDEX란?

색인

(검색을 위해)임의의 규칙대로 부여된, 임의의 대상을 가리키는 무언가

기능으로써는 무언가를 빠르게 찾기위해 존재하는것이라고 생각하면 될 것 같습니다.

흔히들 개발자들이 알고 있는 Index는 배열,리스트의 인덱스입니다.

배열에서 인덱스의 역할은 실제 메모리상의 주소를 추론할 수 있어 O(1) 시간에 데이터에 접근 가능하게 합니다.

Index가 없다면 배열에서는 처음부터 끝까지 뒤져보며 O(n)시간을 소요하지만 O(1)로 접근할 수 있게 해주는 엄청난 효과를 주죠

Database에서 INDEX란?

데이터베이스의 인덱스도 똑같은 역할을 합니다. 

Full Scan하는 대신 더욱 효과적으로 조회(Select)를 하기위해 만들어진 것이죠.

인덱스는 지정한 컬럼들을 기준으로 메모리 영역에 일종의 목차를 생성하는 것입니다.

• 검색성능 향상을 위해 항상 최신상태를 유지하는 테이블
• 데이터베이스 크기의 약 10% 정도의 저장공간을 필요로 합니다.
• 조회성능 향상을 위해 INSERT, DELETE, UPDATE성능을 희생하는것
  

앞서 설명하였듯이 기존에 소요되는 시간보다 더욱 빠르게 조회를 가능하게 해주는것이 바로 Index입니다.

MySQL Index 자료구조

MySQL에서 인덱스는 B-Tree(Balance Tree), B+Tree 로 이루어져있습니다.

엔진별로 다르다고 알려져 있으며 많은 엔진들이 B-Tree 자료구조를 활용하고 InnoDB는 B+트리 자료구조라고 말하고있습니다.

상수 시간에 조회가 가능한 Hash Table을 쓰지않는이유는!?

정확히는 Hash Table도 사용한다고 합니다.

하지만 Index에 관해서 Hash Table이 아닌 B-Tree구조를 사용하는 이유는

바로 Hash Table은  = 연산자 즉, 동등연산자에 한해서만 상수시간에 접근이 가능하기 때문에

>, < 혹은 in연산자 까지 활용하기에는 매우 부적합하기 때문입니다.

B-Tree 자료구조

B-Tree(균형이진트리)란

위 사진과 같이 이진탐색트리의 경우 노드가 한쪽으로 치우칠 수 있어 O(n)의 시간복잡도를 가집니다.

위와같은 밸런스트리 구조를 가질려면 몇가지 조건이 있습니다.

1. 모든 리프 노드의 level은 같습니다.
2. 노드안에 여러개의 key(data) 가질 수 있습니다.
3. 노드안에 모든 데이터는 정렬되어있는 상태를 유지합니다.
4. 자식 노드의 데이터는 부모의 데이터 값에 따라 배치됩니다.

몇가지 조건이 더 있지만 트리의 높이가 같으며 모든 데이터들이 정렬되어있는 자료구조를 의미합니다.

이러한 자료구조를 위해 삭제, 삽입 연산시 특정상황에서는 재정렬하는 현상이 일어나게 됩니다.

Insert, Delete 보다는 Select 연산에 유리한 자료구조 입니다.

Index 삭제,수정 연산

위와 같은 재정렬을 피하기위해서인지 SQL INDEX의 삭제,수정연산은 아래와 같습니다.

• DELETE: 삭제하는 데이터의 인덱스를 사용하지 않음 처리를 합니다.
• UPDATE: 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가합니다.

결국 데이터를 삭제해도 Index는 삭제되지 않습니다.

Index적용 컬럼의 기준 Cardinality

cardinality는 요소의 갯수를 의미합니다.

Boolean타입의 컬럼은 요소의 갯수가 2개입니다.

Month라는 컬럼을 만들면 12개가 되겠죠

Index는 cardinality가 높은 컬럼에 적용해야 효과적입니다.

카디널리티가 높다 = 중복도가 낮다 = 요소의갯수가 많다

카디널리티가 낮다 = 중복도가 높다 = 요소의갯수가 적다

다시 돌아와서 Index는 어느곳에 사용해야할까?!

• 규모가 작지않은 테이블
• INSERT,UPDATE, DELETE가 자주 발생하지 않는 테이블
  - 삽입연산이 자주 일어나면 재정렬이 많이 일어나 성능의 저하가 발생되고
  - 수정,삭제 시에도 Index크기는 계속 늘어나기때문에 성능의 저하가 발생됩니다.
• JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼
  - 위의 3개의 조건이 포함되지않으면 Index는 사용되지 않습니다.
• Cardinality가 높은 컬럼

Mysql Index 조회, 삭제 쿼리

Index 조회

SHOW INDEX FROM '테이블명';

Index 삭제

ALTER TABLE '테이블명' DROP INDEX '인덱스명';

INDEX 생성

CREATE INDEX '인덱스명' ON '테이블명'('칼럼명');

ALTER TABLE '테이블명' DROP INDEX '인덱스명';

한번 더 생각 해보아야할 MySQL 자료구조

https://dba.stackexchange.com/questions/204561/does-mysql-use-b-tree-btree-or-both

Does mysql use B-tree,B+tree or both?

MySQL은 B+Tree를 사용한다고 말하고있습니다. 하지만... 실제로 Index를 조회하면

이렇게 BTree라고 나옵니다.