인덱스(index)
추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 높이기 위한 자료구조이다.
- 인덱스를 활용하면 데이터를 조회하는 SELECT 문 이외의 DELETE, UPDATE에서도 성능이 향상된다. 해당 연산을 수행하려면 해당 대상을 조회해야만 작업을 할 수 있기 때문이다.
- 만약 index를 사용하지 않은 컬럼을 조회해야 하는 상황에선 전체를 탐색하는 Full Scan을 사용해야 한다.
- 인덱스는 데이터들이 정렬되어 있다는 특징을 가진다.
인덱스 관리
DBMS는 인덱스를 항상 최신 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다. 하지만 INSERT, DELETE, UPDATE를 수행할 때 다음과 같은 연산을 추가적으로 해주기 때문에 오버헤드가 발생한다.
- INSERT: 새로운 데이터에 대한 인덱스 추가
- DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업 진행
- UPDATE: 기존의 인덱스를 사용하지 않음으로 처리하고, 갱신된 데이터에 대해 인덱스를 추가
인덱스 자료구조 장단점
장점
- 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
- 전반적인 시스템 부하를 낮출 수 있다.
단점
- 인덱스를 관리하기 위해 데이터베이스의 약 10%에 해당하는 저장공간이 필요하다.
- 인덱스를 관리하기 위해 추가 작업이 필요하다.
- 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.
CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해지기 때문에 오히려 성능이 저하될 수 있다.
인덱스를 사용하면 좋은 경우
- 규모가 작지 않은 테이블
- INSERT, DELETE, UPDATE가 자주 발생하지 않는 컬럼
- JOIN, WHERE, ORDER BY에 자주 사용되는 컬럼
- 데이터의 중복도가 낮은 컬럼
인덱스의 자료구조
해시 테이블(Hash Tabel)
해시 테이블은 (Key, Value) 구조로 빠른 데이터 검색이 필요할 때 유용하게 사용되는 자료구조이다. 해시테이블은 Key값을 이용해 고유한 index를 생성하고 그 index에서 값을 꺼내오는 구조이다.
해시테이블 기반의 DB 인덱스는 (데이터=컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현했다. 시간복잡도는 O(1)로 매우 빠른 검색을 가능하게 한다.
하지만 DB에서 해시테이블을 사용하는 경우는 드물다. 그 이유는 해시가 등호(=)연산에만 특화되어 있기 때문이다. 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시값을 생성한다. 이런 특성에 의해 부등호 연산(<,>)이 자주 사용되는 데이터베이스 검색을 위해서는 해시테이블이 적합하지 않다.
예를 들어 "나는"으로 시작하는 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 전혀 받지 못한다. 따라서 이런 경우 B+Tree 자료구조를 사용한다.
B+Tree
B+Tree는 DB의 인덱스를 위해 자식노드가 2개 이상인 B-Tree를 개선시킨 자료구조이다. B+Tree는 모든 노드에 데이터(Value)를 저장했던 B-Tree와 다른 특성을 가진다.
- 리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)는 데이터를 위한 인덱스(Key)만을 갖는다.
- 리프노드들은 LinkedList로 연결되어 있다.
- 데이터 노드의 크기는 인덱스 노드의 크기와 같지 않아도 된다.
💡 B+Tree는 오직 leaf node에만 데이터를 저장하고, leaf node가 아닌 node에는 자식 포인터만 저장한다. B+Tree에서는 반드시 leaf node에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아 가기 위해서 key가 중복될 수 있다.
장점
- leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있다. 따라서 하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다.
- Full Scan을 하는 경우 B+Tree의 경우 leaf node에만 데이터가 저장되어 있고, lead node끼리 LinkedList로 연결되어 있기 때문에 선형시간이 소모된다. 반면 B-Tree는 모든 node를 확인해야 한다.
