Index

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

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

Index의 관리

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

Index의 장점과 단점

장점

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

단점

• 인덱스를 관리하기 위해 DB의 10%에 해당하는 저장공간이 필요
• 인덱스를 관리하기 위해 추가 작업이 필요
• 인덱스를 잘못 사용할 경우 오히려 성능이 저하되는 역효과 발생

  CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 사용하게 되면 인덱스의 크기가 비대해져서 성능이 오히려 저하되는 역효과가 발생할 수 있음
  UPDATE와 DELETE는 기존의 인덱스를 삭제하지 않고 사용하지 않음 처리를 해주어 어떤 테이블에 UPDATE와 DELETE가 빈번하게 발생된다면 실제 데이터는 10만건 이지만 인덱스는 100만건이 넘어가게 되어, SQL문 처리 시 비대해진 인덱스에 의해 오히려 성능이 떨어지게 될 것이다.

Index를 사용하면 좋은 경우

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

Index의 자료구조

Hash Table(해시 테이블)

빠른 데이터 검색이 필요할 때 유용한 데이터를 저장하는 자료구조
Key값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조

• 해시 테이블 기반의 DB 인ㄷ덱스는 (데이터 = 컬럼의 값, 데이터의 위치)를 (Key, Value)로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현
• 해시 테이블의 시간 복잡도 => O(1)
• 등호(=)연산에만 특화되어 해시 함수의 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하는데, 이런 특성에 의해 부등오(>,<) 연산이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않다.

B+Tree

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

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

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

데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다.
이러한 이유로 BTree의 리프노드들을 Linked List로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화하였다.
B+Tree의 시간 복잡도는 O(log2 n)이지만 해시 테이블보다 인덱싱에 더욱 적합한 자료구조가 되었다.

참고한 블로그 링크