인덱스(Index)

인덱스 란?

• 인덱스란, 추가적인 쓰기 작업과 저장 공간을 활용해 DB 테이블의 검색 속도를 향상시키기 위한 자료구조
• 책의 색인과 같은 존재
• Select의 성능 향상 가능
• 이를 설정하지 않으면 Full Scan이 적용됨
• 단, 인덱스 관리를 위해 DB의 약 10%에 해당하는 저장공간 필요하며 또한, 관리를 위한 추가 작업 필요
• 제대로 관리하지 않고 인덱스가 비대해지면 성능 저하가 발생할 수 있음

인덱스 설정 기준

• Insert, Update, Delete가 자주 발생하지 않는 컬럼
• Join, Where, Order By에 자주 사용되는 컬럼
• 카디널리티(Cardinality)가 높은 컬럼(데이터 중복도가 낮은 컬럼)
• 선택도(Selectivity) 가 낮은 컬럼

인덱스의 자료구조

• Hash Table

  • Key, Value로 데이터를 저장하는 자료구조로 빠른 데이터 검색이 필요할 때 유용
  • Key값을 이용해 고유 index를 생성해 그 index에 저장된 값을 꺼내오는 구조
  • 해시테이블의 시간복잡도는 O(1)로 빠른 검색 지원
  • 단, 등호연산에 특화되어 있으며, 부등호 연산이 자주 일어나는 테이블에는 적합하지 않음

• B+Tree

  • 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조
  • 모든 노드에 데이터를 저장한 BTree와 다른 특성을 가짐
    1. Leaf Node만 인덱스와 함께 데이터(Value)를 가짐, 나머지 Node는 데이터를 위한 인덱스(Key)만 가짐
    2. Leaf Node간에는 LinkedList로 연결
    3. 데이터 Node크기는 인덱스 Node 크기와 다를 수 있음
  • LinkedList를 이용해 순차검색을 용이하게 하여 인덱스에 최적화
  • B+Tree는 O(logn)의 시간복잡도를 갖지만 더욱 적합

    • Inno DB의 B+Tree
      
    • InnoDB는 같은레벨의 Node는 DoubleLinkedList, 자식 Node로는 SingleLinkedList로 되어 있음

인덱스가 적용되지 않는 경우

1. NOT 또는 IN 연산자 사용, 부등호도 사용안됨(Hash Table에서)
2. LIKE 사용 시 %를 앞에 놓는 경우(단, 뒤에만 붙이면 적용 가능)
3. 다중 index에서 조건이 잘못되어 적용되지 않는경우
4. 다중 index활용시 제일 왼쪽 컬럼이 사용되지 않는 경우

참조

-인덱스: https://mangkyu.tistory.com/96