DB Index

DB 인덱스

Hash Table

• Key-value로 이루어진 데이터를 저장하는데 특화된 구조
  • 컬럼 값으로 해시 값을 계산해서 인덱싱 하는 방법
  • Hash Table 기반의 DB Index는 특정 컬럼의 값과 데이터의 위치를 key-value로 사용
• 속도 빠름
  • O(1)
• 값을 변형하는 방법
• 동등 연산에 특화된 방법
  • 해시 함수는 Key가 조금이라도 다르면 완전히 다른 해시 값을 생성하기에 WHERE 조건의 등호(=) 연산에는 효율이 좋지만, 부등호 연산(>, <)은 부적합하다.

B-tree

• 자식 노드가 2개 이상인 트리
• 왼쪽은 key보다 작은 값, 오른쪽은 key보다 큰값
  • 트리 기반의 DB Index는 특정 컬럼의 값(key)에 해당하는 노드에 데이터의 위치(value)를 저장
• 항상 key를 기준으로 오름차순 정렬되어 있다.
  • 부등호 연사에 대해 효율적인 데이터 탐색이 가능
• 균형 트리
  • 평균 시간 복잡도 O(logN)
• 단점
  • 데이터 갱신 반복 → 트리 균형 깨짐 → 성능 약화
  • 순차 검색의 경우 중위 순회를 사용하여 효율이 좋지 않음

B+tree

• B-tree를 확장 및 개선한 자료구조

• 리프 노드에서만 데이터의 위치를 관리

  • 중간 노드에 Value가 없어 메모리 덜 차지하게 되어 하나의 노드에 더 많은 key를 저장할 수 있게됨 →트리의 높이가 낮아짐(빠른 탐색이 가능)
  • 리프 노드들끼리는 LinkedList 구조를 가져 서로 참조하고 있다.
    • 부등호를 이용한 순차 검색 연산의 경우 한번의 탐색으로 충분

• Index 주의점

  • Index는 최신상태로 정렬되기 위해 데이터 개신 작업에 대한 추가적인 연산이 발생
    • INSERT : 새로운 데이터에 대한 인덱스 추가
    • DELETE : 삭제된 데이터를 인덱스에서 제거
    • UPDATE : 기존의 인덱스를 제거, 갱신된 데이터에 대해 인덱스를 추가
  • 주로 사용될 컬럼에만 index를 생성할 것
    • Cardinality가 높은 컬럼을 인덱싱할 것
      • Cardinality는 특정 데이터 집합의 유니크 한 값의 개수
        • 중복도가 높은면 Cardinality가 낮고 중복도가 낮은면 Cardinality가 높다.

스캔

• Full Table Scan
  • 테이블의 첫번째 블록부터 차례대로 엑세스됨
  • 테이블의 전체 블록이 모두 엑세스될 때까지 수행
• Index Unique Scan
  • 하나의 건만 반환
  • 컬럼이 유일한 값으로 구성
• Index Range Scan
  • 수직 탐색 후 필요한 범위까지만 탐색
• Index Full Scan
  • Index Full Scan은 첫번째 리프블록까지 수직적 탐색 후, 인덱스 전체를 탐색하는 방법
  • Table Full Scan의 부담이 크거나 정렬작업을 생략하기 위해 테이블 전체를 탐색하는 것보다 Index를 사용하는 것이 유리(생성된 인덱스가 없어서 사용되는 방법)

스캔 관련1
스캔 관련2
인덱스 스캔 관련 블로그 글

참고

• DB Index 입문
• [자료구조] 그림으로 알아보는 B-Tree
• [MySQL] B-tree, B+tree란? (인덱스와 연관지어서)

Primary Index VS Secondary Index

Primary Index

• Clustered index
  • 비슷한 레코드끼리 묶어서 저장하는 것을 클러스터드 인덱스
  • 키와 대응하는 데이터들이 같은 블록에 있다.
• 기본키를 포함한 인덱스
  • 유일성과 최소성을 가지는 기본키 중 하나로 설정
  • index의 search key가 대게 PK이다.
• 테이블 당 하나만 가지게 된다.
• 인덱스의 리프 노드에 실제 데이터가 있다.(리프 노드에 실제 데이터 페이지가 존재)
• 데이터가 정렬되어 있어야 한다.
  • data가 정렬되어 저장되므로, Secondary Index에 비해 범위로 질의를 하는 것에 유리하다. 빈번한 I/O가 덜 발생할 것이기 때문이다.

Secondary Index

• Non-clustered index
• 보조 인덱스
• 테이블 당 여러개 가질 수 있다.
• 인덱스의 리프 노드에 실제 데이터가 아닌 포인터가 있다.
• 데이터가 정렬되지 않아도 된다.
  • 인덱스 블록의 키만 정렬
  • 데이터 레코드가 index 순서대로 정렬 되어 있지 않기 때문에 범위 조건으로 검색하게 되면 많은 I/O가 발생할 수 있다.

참고

• Clustered Index와 Secondary Index
• 기본 인덱스 (primary index)와 보조 인덱스 (secondary index)의 차이점

복합 인덱스(composite index)

• 여러개의 필드로 인덱스를 설정
• 꼭 인덱스의 컬럼을 모두 사용해야만 하는 것은 아니다.
• 단, 첫 번째 인덱스 조건은 조회 조건에 반드시 포함되어야 한다.
• 필드의 순서가 굉장히 중요하다.
  • 컬럼 순서에 따라 다른 인덱스가 되며 성능도 크게 차이 날 수 있다.
  • AND 조건으로 검색되는 경우 사용해야 한다.
  • 결합 인덱스 컬럼의 설정 시 고려해야할 우선순위
    • (1) WHERE절 조건에 많이 사용되는 컬럼이 우선시
    • (2) Equal(=)로 사용되는 컬럼 우선
    • (3) 분포도가 좋은 컬럼을 우선(서로 다른 데이터들이 중복 없이 존재한다.)
    • (4) 자주 이용되는 순서대로 결합 인덱스 컬럼의 순서 결정

복합 인덱스 1
복합 인덱스 2
복합 인덱스 3
복합 인덱스 4
분포도에 대하여

인덱스 적용 순서

• 인덱스 적용 순서
  • Cardinality 높은 거(중복도가 낮은 것)
  • 자주 사용되는 것(where .. )
  • 덜 수정 되는 것

참고

• 단일인덱스 & 복합인덱스
• 우테코 - 인덱스

커버링 인덱스

• 쿼리를 충족시키는 데 필요한 모든 데이터를 가지고 있는 인덱스
• 실제 데이터에 대한 접근 과정 없이, 인덱스에 존재하는 컬럼 값으로만 쿼리를 완성하는 것을 의미
• 대용량 데이터를 다룰 때 좋다.

클러스터링 + 논클러스터링 인덱스 구성

• 논-클러스터링 인덱스의 리프 페이지에는 클러스터링 인덱스가 적용된 컬럼값(ex. Id)을 가지고 있다.
• 만약 클러스터링 인덱스의 주소값을 가지고 있다면 인덱스 추가 또는 삭제시 주소값을 지속적으로 변경해야하는 문제가 발생한다.

우테코 영상

(참고) 인덱스 적용

GROUP BY 인덱스 적용

• 인덱스 컬럼과 GROUP BY에 명시하는 컬럼의 순서는 동일해야 한다.
• 인덱스 컬럼 중 뒤에 있는 컬럼은 GROUP BY에 명시하지 않아도 된다.(앞에 있는 컬럼은 명시되어야 한다)
• 인덱스에 없는 컬럼을 GROUP BY에 명시하면 안된다.

WHERE + GROUP BY 인덱스 적용

• WHERE가 동등 비교인 경우 WHERE에 있는 컬럼은 GROUP BY에 없어도 인덱스가 적용된다.
• WHERE가 동등 비교가 아닌 경우 인덱스가 제대로 적용되지 않는다.

ORDER BY 인덱스 적용

• 인덱스 컬럼과 ORDER BY에 명시하는 컬럼의 순서는 동일해야 한다.
• 인덱스에 없는 컬럼을 ORDER BY에 명시하면 안된다.
• 특정 컬럼만 DESC를 적용한 경우 인덱스가 적용되지 않는다.

WHERE + ORDER BY 인덱스 적용

• WHERE가 동등 비교인 경우 WHERE에 있는 컬럼은 ORDER BY에 없어도 인덱스가 적용된다.
• WHERE가 동등 비교가 아닌 경우 인덱스가 제대로 적용되지 않는다.

GROUP BY + ORDER BY

• GROUP BY와 ORDER BY 모두 인덱스를 컬럼을 탈 수 있는 조건을 가져야만 인덱스가 적용된다.