인덱스

인덱스(index)란?

인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다.

데이터베이스에서도 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 돕고 있다.

인덱스를 활용하면, 데이터를 조회하는 SELECT 외에도 UPDATE, DELETE의 성능이 함께 향상된다.

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

특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정력하여 별도의메모리 공간에 데이터의물리적 주소와 함께 저장된다. 이렇게 인덱스가 생성되면 앞으로 쿼리문에 “인덱스 생성 컬럼을 Where 조건으로 거는 등”의 작업을 하면 옵티마이저에서 판단하여 생성된 인덱스를 탈 수 있다.

만약 인덱스를 타게되면 아래 그림과 같이 인덱스를 타게 되고 인덱스에 저장되어 있는 데이터의 물리적 주소로 가서 데이터를 가져오는 식으로 동작하여 검색 속도의 향상을 가져올 수 있다.

인덱스에서 내가 원하는 데이터를 먼저 찾고 저장되어 있는 물리적 주소로 찾아간다. DB관련 작업을 할 때 대부분의 저하는 SELECT문 특히 Where절에서 발생하는데 가장 먼저 생각해 볼 수 있는 대안으로 index를 생각할 수 있기도하고 SQL튜닝에서도 Index관련된 해결책이 많다.

인덱스를 사용하는 이유

테이블에서 데이터들이 인덱스의 가장 큰 특징은 데이터들이 정렬되어있다는 점이다.

이 특징으로 인해 조건 검색이라는 영역에서 큰 장점이 된다.

• 조건 where 절의 효율성(인덱스 테이블은 데이터들이 정렬되어 저장되어 있어서 조건에 맞는 데이터들을 빠르게 찾을 수 있다.)
• 정렬 Order by 절의 효율성(Order by는 굉장히 부하가 많이 걸리는 작업니다. 정렬과 동시에 메모리에서 정렬이 이루어지고 메모리보다 큰 작업이 필요하다면 디스크I/O도 추가적으로 발생된다.)인덱스는 이미 정렬되어 있어서 자원의 소모를 하지 않아도 된다.
• MIN, MAX의 효율적인 처리가 가능하다.

Index의 관리

DBMS는 index를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다.

그러므로 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면 각각 다음과 같은 연산을 추가적으로 해주어야하며 그에 따른 오버헤드가 발생한다.

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

Index의 장점과 단점

장점

• 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
• 전반적인 시스템의 부하를 줄일 수 있다.

단점

• 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
• 인덱스를 관리하기 위해 추가 작업이 필요하다.
• CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과가 발생할 수 있다.(UPDATE, DELETE는 기존의 인덱스를 삭제하지 않고 ‘사용하지 않음’처리를 해준다. 이는 실제 데이터에 비해 인덱스가 많아질 수 있어 성능이 저하된다.)

Index를 사용하면 좋은 경우

• 규모가 작지 않은 테이블
• INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼
• JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼
• 데이터의 중복도가 낮은 컬럼
• 기타 등등

(사용하지 않는 인덱스는 바로 제거를 해줘야 한다.)

인덱스의 특징

인텍스 테이블

인덱스는 하나의 테이블을 생성해 값을 저장해놓고 사용한다. 그래서 다른 테이블에 의존적인 새로운 테이블이 하나 생성된다는 점에서 무분별한 인덱스 생성은 오히려 성능 저하를 초래할 수 있다.

정렬

인덱스 테이블은 이진트리 검색을 사용하기 때문에 기본적으로 정렬되어 있다. 만약 인덱스 테이블이 참조하는 테이블에서 삽입, 삭제 , 수정 이 자주 일어나게 된다면 인덱스 테이블에서는 데이터를 정렬하면서 삽입, 삭제 , 수정이 이루어지기 때문에 전체적인 성능 저하를 초래할 수 있다.

인덱스의 자료구조

인덱스를 구현하기 위해 대표적으로 해시 테이블과 B+Tree 자료구조를 사용한다.

해시 테이블(Hash Table)

해시 테이블은(Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 필요할 때 유용하다. 해시 테이블은 Key 값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조이다.

해시 테이블 기반의 DB인덱스는 (데이터 = 컬럼값, 데이터 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현한다.

해시 테이블의 시간복잡도는 O(1)이며 매우 빠른 검색을 지원한다.

단, DB인덱스에서 해시 테이블이 사용되는 경우는 제한적이다.( 해시 함수는 값이 하나라도 달라지면 완전히 다른 해시 값을 생성하므로 등호(=)연산에만 특화되어 있다.:(>,<)이 자주 사용되는 DB에서 해시테이블 부적합)

—>데이터베이스의 인덱스에서는 B+Tree 가 일반적으로 사용된다.

B+Tree

B+Tree는 DB의 인덱스를 위해 자식 노드가 두 개 이상인 B-Tree를 개선시킨 자료구조 이다.

B+Tree는 모든 노드에 데이터(Value)를 저장했던 B-Tree와 다른 특성을 가지고 있다.

• 리프노드(데이터 노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스 노드)들은 데이터를 위한 인덱스(key)만을 갖는다.
• 리프노드들은 LinkedList로 연결되어 있다.
• 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.

데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다.

따라서 B-Tree의 리프노드들은 LinkedList로 연결하여 순차검색을 용이하게 하는 등 B-Tree를 인덱스에 맞게 최적화 하였다.(물론 최적경우에 대해 리프노드까지 가지 않아도 탐색할 수 있는 B-Tree에 비해 무조건 리프노드까지 가야한다는 단점도 있다.)

이러한 이유로 비록 B+Tree는 O(log2n) 의 시간복잡도를 갖지만 해시테이블보다 인덱싱에 더욱 적합한 자료구조가 되었다.

위는 InnoDB에서 사용한 B+Tree구조이다.

InnoDB에서의 B+Tree는 일반적인 구조보다 더욱 복잡하게 구현되었다. 같은 레벨의 노드들끼리는 LinkedList가 아닌 Double Linked List로 연결되었으며, 자식 노드들은 Single Linked List로 연결되어있다.