Index

Index란

정의

• 데이터의 조회 속도를 향상시키기 위해 사용하는 자료구조

• 특정 컬럼에 대해 정렬된 순서로 원본에 대한 참조를 가지는 별도의 데이터를 생성

  • 왜? 순서가 정렬되었음이 보장될 때, Binary Search와 같은 알고리즘을 통해 원하는 데이터를 더 빠르게 효율적으로 찾을 수 있기 때문!

Index의 자료구조

B+ Tree

• 최근에는 대부분 DB에서 B+ Tree를 채택

• B+ Tree란, Leaf가 아닌 Node들은 모두 값이 아니라 left/right child 분기의 기준이 되는 범위에 대한 정보를 가지고 오직 Leaf만이 실제 데이터를 갖는 자료구조

• log 시간복잡도로 원하는 데이터를 찾을 수 있음

• 또한, Leaf Node 간에 연결이 존재해 범위 내 데이터의 조회 연산에 효율적

장점

• 카디널리티(Cardinality)가 높은 컬럼에 잘 사용하면 조회 속도를 O(N)에서 O(logN)까지 개선할 수 있음

  • 카디널리티가 높다는 것은, 데이터의 중복도가 낮다는 것을 의미

  • 중복되는 데이터가 적으면 범위 연산이 효율적으로 작동하기 때문

• 정렬(ORDER BY), 조건부(WHERE) 연산 등에 효율적

단점

• 데이터를 생성/수정/삭제할 때마다 인덱스에 이를 반영해야 하기 때문에 추가적인 연산 시간 및 저장 공간을 사용함

• 즉, 공간 복잡도 면에서는 비효율적이고, 데이터를 조작하는 연산의 속도는 저하됨

그럼 언제 사용?

• 데이터의 카디널리티가 높고, 데이터의 생성/수정/삭제보다 조회 빈도가 훨씬 높은 컬럼에 사용하는 것이 좋음

• 대표적인 예시가 Primary Key이고, 때문에 PK에는 자동으로 index가 생성됨

• unique constraint가 부여된 컬럼도 카디널리티가 가장 높기 때문에 자동으로 index가 생성됨

세부 사용 사례

단일 인덱스와 복합 인덱스

• 여러 컬럼으로 인덱스를 구성할 수도 있으며, 이를 복합 인덱스라고 함

• 복합 인덱스는 순서가 중요하며 순서에 따라 B+ 트리가 구성됨

• 가장 처음에 명시한 트리부터 순서대로 정렬되기 때문에, 첫 번째 컬럼이 조건에 포함되지 않으면 해당 복합 인덱스는 사용되지 않음

  • 반대로 말하자면, 첫 번째 컬럼이 포함되는 경우 일부 컬럼이 누락되어도 100% 효율은 아닐지라도 해당 복합 인덱스가 사용되어 더 효율적 조회를 할 수도 있음

• 또한, 복합 인덱스를 구성할 때에는 카디널리티가 높은(중복이 적은) 컬럼부터 구성하는 것이 더 효율적

인덱스 조회시 주의 사항

• 복합 인덱스여도 첫 컬럼이 between, like, <, >와 같은 범위 조회 조건의 대상인 경우 이후 컬럼의 인덱스가 사용되지 않음

  • 어차피 첫 컬럼의 범위 조회로 조회 결과를 결정지을 수 있기 때문

• =, in과 같이 정확히 매칭되는 컬럼을 찾는 경우에는 첫 컬럼 이후 컬럼의 인덱스도 사용됨

• 인덱스로 사용된 컬럼값을 변형(형변환, 산술 연산 등을 적용)하는 경우 인덱스가 사용되지 않음

• null 값은 is null 조건으로 인덱스 스캔이 가능

가장 중요한 것은 실행계획을 직접 확인해보는 것

• explain을 통해 옵티마이저가 작성한 실행 계획을 확인하여 실제로 의도한 인덱스가 사용되는지를 꼭 확인해봐야 함

• DBMS에 따라, 데이터 구성에 따라 실행계획이 달라질 수 있기 때문

참고 자료

창천향로 - 인덱스 정리 및 팁