DB에서 인덱스를 사용하는 이유

인덱스(Index)
데이터베이스 테이블에 대한 검색 속도를 높여주는 자료구조이다.
특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 (key, value)의 한 쌍으로 저장된다.
인덱스는 색인이라고 생각하면 된다. 테이블에서 원하는 데이터를 찾기 위해 인덱스를 이용하면 빠르게 찾을 수 있다.
기존엔 WHERE문으로 특정 조건의 데이터를 찾기 위해서는 테이블 전체를 조건과 비교해야 하는 'Full Table Scan' 작업이 필요했지만, 인덱스를 이용하면 데이터가 정렬되어 있기 때문에 조건에 맞는 데이터를 빠르게 찾을 수 있다.
또, ORDER BY나 MIN/MAX의 경우에도 이미 정렬이 되어있기 때문에 빠르게 수행할 수 있다.

장점

테이블을 검색하는 속도와 성능이 향상되어 시스템의 전반적인 부하를 줄일 수 있다.

 

인덱스를 사용하면 좋은 경우

1. 규모가 큰 테이블

2. INSERT, UPDATE, DELETE 작업이 자주 발생하지 않는 컬럼

3. WHERE, ORDER BY, JOIN 등이 자주 사용되는 컬럼

4. 데이터의 중복도가 낮은 컬럼

 

단점

1. 인덱스를 관리하기 위한 추가 작업이 필요하다.

INSERT(새로운 데이터에 대한 인덱스를 추가), DELETE(삭제하는 데이터의 인덱스를 사용하지 않는다는 작업 수행), UPDATE(기존의 인덱스를 사용하지 않고, 갱신된 데이터에 대한 인덱스를 추가)

2. 데이터의 수정이 잦은 경우, 성능이 낮아진다.

3. 추가적인 저장 공간이 필요하다.

인덱스를 제거하지 않고 사용하지 않는다는 처리를 하기 때문에 수정/삭제 작업이 많은 경우, 실제 데이터에 비해 인덱스가 과도하게 커지는 문제가 발생할 수 있다.

4. 잘못 사용하는 경우, 오히려 검색 성능이 저하된다.

데이터의 형식에 따라 오히려 성능이 저하될 수 있다. 예를 나이나 성별같이 값의 범위가 작은 컬럼의 경우, 인덱스를 읽고 다시 많은 데이터를 조회하기 때문에 비효율적이다.

 

인덱스의 자료구조

인덱스는 여러 자료구조를 이용하여 구현할 수 있다. (ex. 해시테이블(Hash Table), B+Tree)

 

1. Hash Table

(key, value) 한 쌍으로 데이터를 저장하는 자료구조.

평균적으로 O(1)의 매우 빠른 시간안에 데이터를 탐색할 수 있는 구조이지만, 실제로 인덱스에서는 잘 사용하지 않는다.

데이터베이스에서는 부등호(<, >) 연산이 자주 사용되지만, Hash Table은 등호(=) 연산에 최적화되어있고, 데이터가 정렬되어 있지 않기때문에 부등호 연산 시 빠른 탐색이 불가능하기 때문이다.

 

2. B+Tree

기존의 B-Tree는 어느 한 데이터의 검색을 효율적이지만, 모든 데이터를 한번 순회하는데 트리의 모든 노드를 방문해야 하므로 비효율적이다. 이러한 단점을 개선시킨 것이 B+Tree이다.

B-Tree

B-Tree의 경우 최상의 경우에서 특정 key를 root node에서 찾을 수 있다.

B+Tree

B+Tree에서는 반드시 leaf node에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아가기 위해 key가 중복될 수 있다.

 

장점

1. leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있다. 따라서 하나의 node에 더 많은 포인터를 가지기 때문에 Tree의 높이가 낮아져 검색 속도를 높일 수 있다.

2. Full Scan을 하는 경우 leaf node에만 데이터가 저장되어 있고, leaf node끼리 linked list로 연결되어 있어, 선형 시간이 소요되어 모든 node를 확인해야하는 B-node 보다 빠르다.

3. linked list를 이용해 부등호를 이용한 순차 검색을 효율적으로 할 수 있다.

 

단점

특정 key에 접근하기 위해서 반드시 leaf node까지 가야한다.