[데이터베이스] Index

장점
- 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.
- 전반적인 시스템의 부하를 줄일 수 있다.
단점
- 인덱스를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요하다.
- 인덱스를 관리하기 위해 추가 작업이 필요하다
- 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있다.

만약 CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면
인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과가 발생할 수 있다.

그러한 이유 중 하나는 DELETE와 UPDATE 연산 때문이다.

UPDATE와 DELETE는 기존의 인덱스를 삭제하지 않고 '사용하지 않음' 처리를 해준다고 했다.

만약 어떤 테이블에서 UPDATE와 DELETE가 빈번하게 발생하게 된다면 실제 데이터는 10만건이지만 인덱스는 100만 건이 넘어가게 되어, SQL문 처리 시 비대해진 인덱스에 의해 오히려 성능이 떨어지게 될 것이다.

인덱스를 사용하는 것 만큼이나 생성된 인덱스를 관리해주는 것도 중요하다. 그러므로 사용되지 않는 인덱스는 바로 제거를 해주어야 한다.

인덱스(Index)의 자료구조

인덱스를 구현하기 위해서는 다양한 자료구조를 사용할 수 있는데,
가장 대표적인 해시 테이블과 B+Tree에 대해서 알아보자.

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로
빠른 데이터 검색이 필요할 때 유용하다.

해시 테이블은 Key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조다.

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

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

하지만 DB인덱스에서 해시 테이블이 사용되는 경우는 제한적인데 그 이유는 해시가 등호(=)연산에만 특화되었기 때문이다.

해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이러한 특성에 의해
부등호 연산(>, <)이 자주 사용되는 DB 검색을 위해서는 해시 테이블이 적합하지 않다.

B+Tree는 DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조다.
B+Tree는 모든 노드에 데이터(Value)를 저장했던 BTree와 다른 특성을 가지고 있다.

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

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

이러한 이유로 BTree의 리프노드들은 LinkedList로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화 하였다.

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

안녕하세요