index가 왜 필요한가?

index 란?

도서의 색인이나 사전과 같이 데이터를 쉽고 빠르게 찾을 수 있도록 만든 데이터 구조

index를 사용하는 이유?

1. 검색 속도(조회 속도)를 향상시키위해서 사용한다.
2. 시스템의 부하를 줄여서 시스템 전체에 대한 성능에 긍정적인 영향을 준다.

index가 빠른 이유

1. 효율적인 자료구조 사용

 

index를 사용한다고 했을 때 주로 B-tree 자료구조를 사용한다. 트리 자료구조를 사용하기 때문에 특정 자료를 검색할 때 O(log N)의 시간 복잡도로 탐색이 가능하다. 반면에 테이블을 전체 조회 (풀 스캔)할 때는 O(N)의 시간 복잡도로 탐색을 해야한다. index가 빠른 이유는 효율적인 자료구조를 적용하였기 때문이다.

 

2. 캐시 버퍼의 효율적인 사용

테이블에서 데이터를 조회해서 조건을 검색할 때는 모든 속성을 읽고 비교를 해야한다. 때문에 하나의 레코드에 필요한 데이터의 수는 속성의 수와 그 크기에 비례해서 커진다. 반면에 인덱스를 사용하면 인덱싱된 속성만 사용된다. 때문에 하나의 레코드를 검색할 때 버퍼에 캐싱되는 데이터크기가 인덱스가 적다. 이는 동일한 캐시 버퍼에 더 많은 레코드를 저장할 수 있다는 의미이다. 상대적으로 디스크에서 데이터를 읽어오는 횟수가 적기 때문에 인덱스가 빠르다.

 

3. 정렬 작업의 오버헤드 제거

데이터를 정렬하기 위해서 추가적인 정렬 작업이 필요하다. 이를 위해서 임시 테이블을 사용해서 데이터를 정렬시키는 작업이 필요한데 만약 정렬 기준이 인덱스에서 사용한 속성이라면 이러한 과정이 필요가 없다. 정렬 작업에 따른 추가적인 연산과정이 필요없기 때문에 인덱스가 빠르다.

index의 단점?

1. 데이터 변경시 오버헤드로 인한 성능 저하
2. 인덱스는 조회시 성능 개선을 위해서 사용하는 기술이다. 그래서 조회시에는 많은 장점을 지니지만 변경 시 느리다는 단점을 가지고 있다. 인덱스가 없는 데이터를 변경할 때는 테이블에 원하는 대상만 변경하면 되지만 인덱스가 있는 데이터를 변경할 때는 인덱스의 정보 역시 갱신을 해주어야한다. 즉 해야할 작업이 늘어난다. 이로 인해서 데이터 변경 작업(update, insert, delete)을 처리할 때 느리다.

인덱스 종류

1. B-Tree index

트리를 이용한 가장 범용적인 인덱스이다. B-Tree는 Balanced tree 라고 할 수 있다. 즉 정렬된 트리라는 것이다.

• 특징
  • 리프노드의 깊이가 동일하다.
  • 리프노드는 인덱스의 정렬 기준에 따라서 정렬되어 있다.
  • 리프노드에서 인접한 다른 리프노드를 참조할 수 있다.

2. Hash index

해시를 이용한 인덱스이다. 동등 비교 연산에서 가장 최적화되어 있는 인덱스이지만 범위 검색에는 성능이 떨어진다. 주로 메모리 기반의 테이블에서 사용되고 디스크 기반의 대용량 테이블용으로 거의 사용되지 않는댜.

 

3. Fractal-Tree index

B-tree의 단점을 개선한 Fractal-Tree를 이용한 인덱스이다. 랜덤 I/O를 순차 I/O로 변환해서 처리할 수 있다는 장점을 가지고 있다.

 

4. R-tree

공간을 나타내는 데이터를 인덱싱하기 위해서 사용하는 특수한 트리이다. B-Tree 구조를 계승하지만 차이점은 인덱스를 구성하는 칼럼의 값이 스칼라값이 아니라 2차원의 공간 개념 값이라는 것이 차이다.

 

5. Full Text Search index

• Stopword

구분자를 이용해서 전문을 분할하여 키워드를 추출하고 이를 활용해서 인덱스를 생성하는 방식이다. 내부적으로 B-Tree을 이용한다.

• n-Gram

구분자를 추출하기 어려운 경우에 검색이 정확하게 이루어지지 않는다는 점을 극복한 방식으로 특정 n사이즈만큼 텍스트를 분할하여 저장하는 방식이다. n의 크기에 따라서 검색의 정확도가 판별되는 특징을 가진다. 구분자 방식에 비해 인덱싱 알고리즘이 복잡하고 인덱스의 크기가 상대적으로 크다.

 

6. clustered index

인덱스의 저장된 데이터의 순서가 실제 저장된 데이터 레코드의 순서와 같은 인덱스이다. Mysql에서는 PK를 순서대로 데이터를 저장하고 인덱스를 생성한다.

 

[reference]

https://joosjuliet.github.io/index_structure/

real mysql 위키북스