Index

인덱스(Index)는 데이터베이스 테이블에 대한 검색 성능의 속도를 높여주는 자료구조이다. 특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저정된다.

우리가 책에서 어떠한 부분을 찾는다고 하면, 무작정 책을 넘겨보면서 찾는 것이 아니라 먼저 목차를 확인 할 것이다. 데이터베이스 내의 인덱스는 책의 목차와도 같다.

인덱스는 책에서의 목차 처럼, 인덱스에 저장되어 있는 데이터의 물리적 주소로 가서 데이터를 가져오는 식으로 동작을 하여 검색 속도의 향상을 가져올 수 있다.

인덱스를 활용하면 SELECT 이외에도 UPDATE나 DELETE의 성능또한 함께 향상된다.
왜냐하면 해당 연산을 수행하려면 해당 대상을 조회해야만 작업을 할 수 있기 때문이다.

만약 index를 사용하지 않은 컬럼을 조회해야 하는 상황이라면 전체를 탐색하는 Full Scan을 수행해야 한다. 하지만 Full Scan은 전체를 비교 탐색하기 때문에 처리 속도가 현저히 떨어진다.

Index의 장단점

장점

인덱스의 장점으로는 앞에서 말했듯이 테이블을 검색하는 속도와 성능이 향상된다. 또 그에 따라 시스템의 전반적인 부하를 줄일 수 있다.

핵심은 인덱스에 의해 데이터들이 정렬된 형태를 갖는다는 것이다. 기존엔 Where문으로 특정 조건의 데이터를 찾기 위해서 테이블의 전체를 조건과 비교해야 하는 Full Scan 작업이 필요 했는데, 인덱스를 이용하면 데이터들이 정렬되어 있기 때문에 조건에 맞는 데이터를 빠르게 찾을 수 있다.
또 ORDER BY 문이나 MIN/MAX 같은 경우도 이미 정렬이 되어 있기 때문에 빠르게 수행할 수 있다.

단점

DBMS는 Index를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다. 그렇기 때문에 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면 각각 다음과 같은 연산을 추가적으로 해주어야 하며 그에 따른 오버헤드가 발생한다.

• INSERT : 새로운 데이터에 대한 Index 추가.
• DELETE : 삭제하는 데이터의 Index를 사용하지 않는다는 작업을 진행.
• UPDATE : 기존의 Index를 사용하지 않음 처리하고 갱신된 데이터에 대해 Index를 추가.

이처럼 인덱스의 수정도 추가적으로 필요하기 때문에 데이터의 수정이 잦은 경우 성능이 낮아진다. 또 데이터의 인덱스를 제거하는 것이 아니라 '사용하지 않음'으로 처리하고 남겨두기 때문에 수정 작업이 많은 경우 실제 데이터에 비해 인덱스가 과도하게 커지는 문제점이 발생할 수 있다. 별도의 메모리 공간에 저장되기 때문에 추가 저장 공간이 많이 필요하게 된다.

또한 인덱스는 전체 데이터의 10 ~ 15% 이상의 데이터를 처리하거나, 데이터의 형식에 따라 오히려 성능이 낮아질 수 있다. 예를 들어 나이나 성별과 같이 값의 range가 적은 컬럼인 경우, 인덱스를 읽고 나서 다시 많은 데이터를 조회해야 하기 때문에 비효율적이다.

Index를 사용하면 좋은경우

• 규모가 작지 않은 테이블

• INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼

• JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼

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

  Index의 자료구조

  인덱스의 여러 자료구조를 이용해서 구현할 수 있는데, 대표적으로 해시 테이블(Hash Table)과 B+Tree가 있다.

  Hash Table

  해시 테이블은 key와 value를 한 쌍으로 데이터를 저장하는 자료구조이다. (key, value)로 쌍을 표현하며, key값을 이용해 대응되는 value값을 구하는 방식이다. 해시 충돌이라는 변수가 존재하지만 평균적으로 0(1)의 매우 빠른 시간만에 원하는 데이터를 탐색할 수 있는 구조이다ㅏ.

해시 테이블을 이용한다면 인덱스는 (key, value) = (컬럼의 값, 데이터의 위치)로 구현하는데, 해시 테이블은 실제로 인덱스에서 잘 사용되지 않는다.

그 이유는, 해시 테이블은 등호(=) 연산에 최적화 되어있기 때문이다. 데이터베이스에선 부등호 (<,>) 연산이 자주 사용되는데, 해시 테이블 내의 데이터들은 정렬되어 있지 않으므로 특정 기준보다 크거나 작은 값을 빠른 시간내에 찾을 수가 없다.

B+Tree

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

B+Tree는 오직 leaf node에만 데이터를 저장하고 leaf node가 아닌 node에서는 자식 포인터만 저장한다.
그리고 leaf node끼리는 Linked list로 연결되어있다.

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

(B-Tree)

(B+Tree)

이로인한 장점

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

2) Full Scan을 하는 경우 B+Tree는 leaf node에만 데이터가 저장되어 잇고, leaf node끼리 linked list로 연결되어 있기 때문에 선형 시간이 소모된다. 반면 B-Tree는 모든 node를 확인해야한다.