[TIL] Database Index

Database(DB) Index

1. 개요

Index란 우리말로 색인으로, 사전적 의미는 본문의 중요한 것을 뽑아 이들의 소재를 기재한 것이다.
쉽게 생각하면 원하는 정보를 찾기 위한 구분 가능한 지표이다.
DB의 Index 또한 자료의 위치를 나타내기 위한 지표이다.

2. 성능

Index가 존재하면 DB에서 데이터를 검색하는 과정을 빠르게 만들 수 있다.
특정 자료를 찾을 때, Index가 없다면 모든 자료를 스캔하며 조건에 맞는 자료를 찾아야한다.
Index를 사용하면 자료와 방식에 따라 탐색 시간을 의미있게 줄일 수 있다.
탐색에 드는 소요값 자체를 줄이면 디스크에서 불필요한 입출력 또한 줄어든다.
이를 통해 시스템의 전반적인 성능 향상을 기대할 수 있다.

Index에 고유 키, 외래 키 등의 조건을 적용하여 데이터의 일관성도 향상시킬 수 있다.
이 밖에도 Index를 사용하면 데이터를 정렬 및 그룹화 하는 과정을 쉽게 할 수 있다.
일반적으로 Index는 DB의 성능을 향상시키지만, Index를 생성하고 유지하는 것 자체로
리소스의 요구를 추가적으로 발생시킨다는 것을 고려해야 한다.

우선 Index를 사용할 때 추가 저장 공간을 필요로 한다.
대규모의 DB의 경우 추가 저장 공간이 문제가 될 수 있다.
테이블의 데이터가 자주 업데이트 되는 경우 Index가 조각화되어 효율성이 떨어질 수 있다.
이러한 조각화를 방지하는 등 Index의 성능을 최적화 하기 위해
주기적으로 관리하는 과정에서 시스템에 발생하는 오버헤드 또한 문제가 될 수 있다.

3. Index

Index에 주로 사용되는 기법은 hash table과 균형 트리 등을 사용한다.
Hash table은 연결리스트나 이진 검색 트리를 사용하며 크기를 동적으로 조정하여
평균적으로 O(1)에 가까운 속도를 보이지만, hash 함수의 성능이 중요하다.
Hash 충돌이 자주 일어나는 함수는 최악의 경우 O(N)에 수렴한다.
또한 Hash함수는 key 값이 다른 경우 완전히 다른 value를 반환하기 때문에
등호 연산을 제외하면 탐색에 부적합하다.

또한 주로 사용되는 균형 트리인 B+tree는 균형을 유지하며 삽입 삭제가 이루어진다.
이를 통해 조회, 삽입, 삭제에 항상 O(log N)의 시간 복잡도를 가지는 장점이 있다.
그러나 균형을 맞추는 데 O(log N)의 시간 비용이 추가로 발생할 수 있다.
또한 B+tree는 모든 데이터를 리프노드에만 저장하여 메모리 소모가 크다.