Index란 무엇인가.

 

Index란?

인덱스는 추가적인 저장공간을 활용하여 테이블의 데이터 검색 성능을 높여주는 자료구조이다.

이를 통해, 우리는 대규모 데이터를 가지고 있는 테이블에 대해 몇분이 걸리던 select 쿼리를 단 몇초만에 끝낼 수 있는 이점을 얻는다.

이런 인덱스가 없다면 우리는 테이블의 처음부터 끝까지 Full Scan을 통해 아주 힘겹게 해당 데이터를 찾아야한다.

 

책의 저자가 미리 작성해놓은 색인 페이지를 통해

우리는 "효율적으로 원하는 단어를 찾을 수 있게되는 것이다."

 

select 뿐만아니라, 인덱스를 사용하게되면 delete, update 연산 성능도 함께 향상된다.

그 이유는 삭제, 수정을 하게 위해서는 일단 조회 연산을 진행하기 때문이다.

 

하지만, 이런 인덱스는 장점만 가지고 있는 것은 아니다.

검색에는 뛰어난 성능 향상을 보여주지만, 테이블의 빈번한 insert, update, delete는 오히려 성능 측면에서 역효과가 발생할 수 있다.

 

그 이유에 대해서는 다음 구조와 동작 방식을 보며 알아보자.

 

Index는 어떻게 저장되고 관리될까?

인덱스를 구현하기 위해서는 다양한 자료구조를 사용할 수 있는데, 대표적으로 해시테이블과 B-Tree를 이용하여 구현한다.

 

[ 해시 테이블(Hash Table) ]

해시테이블은 (key,value)로 데이터를 저장하는 자료구조로,

key 값을 해시함수에 넣어 고유한 Index 값을 만들어내고, 해당 인덱스 주소에 value를 저장하는 방식으로 동작한다.

해시 테이블을 이용한 검색 시간 복잡도는 O(1)으로 매우 빠른 검색 속도를 가지고 있다.

 

하지만 이런 해시 테이블 방식은 DB 인덱스에는 제한적인 특징을 가지고 있는데, 해시 테이블 연산은 등호(=) 연산에만 특화되어 있기 때문이다. 1이라도 달라도 해시함수는 전혀 다른 해시값을 반환한다.

 

그에 반해 검색 쿼리에서는 부등호( >, <, >=, <= ) 연산을 통해 범위를 통한 검색을 하기 때문에 해시 테이블을 적용한 방식은 옳지 않다.

 

이러한 이유로 인덱스는 B-Tree 자료구조를 통해 구현된다.

 

 

[ B-Tree ]

 

 

B-Tree 는 최상위에 하나의 루트 노드가 존재하고 그 하위에 자식 노드가 붙어있는 형태이다.

 

트리 구조의 가장 하위에는 리프 노드라고 하고 트리구조에서 루트노드도 아니고 리프노드도 아닌 중간의 노드를 브랜치 노드라고 한다. 

 

이 인덱스의 최대 장점은 어떤 데이터를 조회하든지, 이에 사용하는 조회 과정의 길이 및 비용이 균등하다.

 

 

Index 타입의 종류

인덱스는 다음 두 가지 타입이 존재한다. 

 

1. 클러스터 인덱스

2. 보조 인덱스

 

먼저 두가지의 차이를 쉽게 비유하자면,

클러스터 인덱스는 책의 앞부분 목차 페이지, 보조 인덱스는 책의 뒷부분 색인 페이지 라고 할 수 있다.

 

그 이유는 동작과정을 보며 알아보자.

 

 

일단 테이블의 데이터는 mysql에서 페이지(page)라는 16kb 단위로 분할되어 저장된다. 

 

 

클러스터 인덱스

1. 어떤 컬럼값을 클러스터 인덱스로 만들게 되면, 루트 페이지가 만들어진다.

    루트 페이지는 각 데이터 페이지의 첫번째 데이터만 모은 페이지이다.

2. 그리고 각 데이터 페이지는 자동 정렬이 된다.

 

 

클러스터 인덱스를 이용한 "단일 조회"

클러스터 인덱스를 활용한다면, 루트 페이지를 통해 원하는 데이터가 존재하는 페이지 정보를 얻게 되어
빠르게 해당 데이터를 찾을 수 있다는 이점이 있다.

 

 

클러스터 인덱스를 이용한 "범위 조회"

범위를 통한 검색 조차도, 단건 조회와 같이 범위에 해당하는 페이지를 루트 페이지를 통해 찾을 수 있게되고 

빠른 시간복잡도 안에 해당 데이터들을 찾을 수 있게 된다.

 

이것은 모두 클러스터 인덱스를 통해 데이터들이 정렬이 되어 페이지들에 저장이 되어 있기 때문에 가능한 일이다.

 

 

클러스터 인덱스를 이용한 "데이터 삽입"

클러스터 인덱스를 통해 데이터들을 저장하다가, 특정 페이지의 공간이 가득차게 되면 "페이지 분할"이라는 작업이 일어나게 된다.

 

이런 페이지 분할이 발생하게 되면 새로운 페이지를 만들고, 데이터들을 분배하여 넣고 다시 정렬하는 과정을 거쳐야한다.

이 부분이 계속해서 빈번하게 발생하면 성능이 나빠지는 역효과가 발생한다.

 

 

보조 인덱스

1. 보조 인덱스 역시 루트 페이지가 만들어진다.

  하지만 루트 페이지를 바로 데이터가 들어있는 페이지로 연결시키지 않고, 따로 리프 페이지를 만들어서 정렬 시킨다.

2. 그리고 데이터가 실제로 들어있는 데이터 페이지는 정렬을 하지않고, 그대로 둔다.

3. 즉, 데이터들의 주소를 담고 있는 인덱스 페이지를 따로 만들어서 그것들을 정렬하며 관리하고,

   실제 데이터 페이지는 정렬하지 않고 그대로 담아서 보관하는 방식이다.

 

 

보조 인덱스를 이용한 "단건 조회"

단건 조회는 인덱스 페이지를 한번 더 거쳐야하므로 클러스터 인덱스에 비해서는 느리다.

 

 

보조 인덱스를 이용한 "범위 조회"

범위 검색을 진행하면, 정렬되어 있는 인덱스 페이지를 통해 해당하는 데이터들을 찾을 수 있게 된다.

 

 

보조 인덱스를 이용한 데이터 삽입

데이터 삽입 부분에서 클러스터 인덱스와 다른 양상을 보이는데,

보조 인덱스는 데이터 삽입 시 데이터 페이지의 빈 영역에 그냥 넣기만 하면 되고

따로 페이지 분할을 통해 재정렬을 할 필요가 없다. 그냥 리프 페이지에 해당 데이터의 주소만 기입하기만 하면 된다.

 

물론 리프 페이지에서도 페이지 분할이 일어나긴 하지만,

실제 데이터를 모두 가지고 분할/분배/정렬을 하는 것이 아니기 때문에

클러스터 인덱스의 페이지 분할보다 훨씬 더 가벼운 작업이다.

 

효율적인 인덱스 설계

1. SELECT, WHERE 절에 조건으로 자주 사용되는 컬럼

 

2. JOIN절에 자주 사용되는 컬럼에 효율적이다.

 

3. ORDER BY 절에 사용되는 컬럼은 인덱스에 의해 이미 정렬되어 있기 때문에 효율적 

 

비효율적인 인덱스 설계

1. 대용량 데이터가 자주 입력되는 경우

- 빈번한 페이지 분할이 일어나기 때문에 부하가 생기게 된다.

- 이럴때는 클러스터 인덱스보다는 보조 인덱스로 설정

 

2. 중복된 값이 많은 컬럼

- 대부분 같은 값이라, 인덱스로 정렬해서 보유하고 있을 필요가 없다.

   왜냐면 굳이 대부분 같은 값을 정리해놔봤자 효율적인 검색에는 도움이 안되기 때문이다.