Index

Index란?

• 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조
• 자주 조회되는 Column에 대한 Index Table을 따로 만들어 SELECT 문 수행 시 Index Table에 있는 값으로 결과를 조회
• 만약 Index를 적용하지 않은 컬럼을 조회할 시. Full Scan이 수행
• 주로 B+tree로 구성된 구조를 사용

Index 사용 시 주의할 점

• 항상 정렬된 상태를 유지하기 때문에 원하는 값을 탐색하는 것은 빠르다
• 새로운 값을 추가하거나 삭제, 수정하는 경우에는 쿼리문 실행 속도가 느려짐
  • INSERT: 테이블에는 입력 순서대로 저장, 인덱스 테이블에는 정렬하여 저장하기 때문에 성능 저하 발생
  • UPDATE: 인덱스에는 UPDATE가 없어서, DELETE 후 INSERT하는 작업을 수행해 부하 발생
  • DELETE: 테이블에서만 삭제되고 인덱스 테이블에는 남아있어 쿼리 수행 속도 저하
• 데이터의 중복이 높은 컬럼 (cardinality가 낮은 컬럼)을 인덱스로 생성 시 불리함
  • 선택하는 데이터가 많아질수록 Full scan에 가까워진다

Primary Index vs Secondary Index

Primary Index

• 기본키를 포함하는 인덱스 (키의 순서가 레코드의 순서를 결정)
• 정렬된 파일
• Clustering Index라고도 불림

Secondary Index

• 기본 인덱스 이외의 인덱스 (키의 순서가 레코드의 순서를 의미하지 않음)

B-+tree

B-tree

• 노드의 자료수가 N이라면 자식의 수는 N+1이어야 한다.
• 각 노드의 자료는 정렬된 상태여야 한다.
• 노드의 자료Dk의 왼쪽 서브트리는 Dk보다 작은 값들이고 오른쪽 서브트리는 Dk보다 큰 값들이어야 한다.
• Root 노드는 적어도 2개이상의 자식을 가져야 한다.
• Root 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다.
• 외부 노드로 가는 경로의 길이는 모두 같다.
• 외부노드는 모두 같은 레벨에 있다
• 입력자료는 중복될 수 없다.

B+tree

• B-tree의 각 노드에서는 key 뿐만 아니라 data도 들어갈 수 있다.
  • 여기서 data는 disk block으로의 포인터가 될 수 있다.
• B+tree는 각 node에서는 key만 들어가야 한다.
  • B+tree에서는 data는 오직 leaf에만 존재한다.
• B+tree는 B-tree와는 달리 add, delete가 leaf에서만 이루어진다.
• B+ tree는 leaf node 끼리 linked list로 연결되어 있다.

더 알아보기

Index를 생성하는데 Hash와 B+tree 중 B+tree를 사용할까?

• Hash Table의 경우 O(1)의 시간복잡도를 보장해 B+tree보다 빠르다
• SELECT 질의의 조건에는 부등호(<, >) 연산을 포함한다
• Hash Table의 경우 등호(=)를 제외한 부등호 연산의 경우 부적합하다

여러 Column의 Index 사용

• 인덱스의 모든 컬럼을 사용할 필요는 없다. (누락이 가능하다)
• 아래와 같이 Index가 잡혀있다.

  Index: A, B, C

• 아래 쿼리문은 실행 계획 분석 시 인덱스를 사용했다.

  explain SELECT *
  FROM EXAMPLE
  WHERE
  A = 'EXAMPLE'
  AND C = true;

• 아래 쿼리문은 실행 계획 분석 시 인덱스를 사용하지 않았다.

  explain SELECT *
  FROM EXAMPLE
  WHERE
  B = '2002-07-30'
  AND C = true;

• 조회 쿼리 사용 시 인덱스를 사용하려면 최소한 첫번째 인덱스 조건은 조회 조건에 포함되어야한다.

Reference

• Tech Interview
• [mysql]인덱스 정리 및 팁
• 클러스터드 인덱스 / 넌클러스터드 인덱스 / primary 인덱스
• 클러스터드 인덱스와 넌 클러스터드 인덱스
• [MSSQL]인덱스의 내부 동작방식
• Clustered Index와 Secondary Index
• [파일구조] B tree 와 B+ tree