📝Index란?

데이터베이스에서 table의 검색 성능을 높여주는 대표적인 방법.

• Index 소개
  Index는 책의 색인(원하는 내용이 어디에 있는지 명시 해주는)과 같은 기능을 가지고 있는 자료구조이다. DB Table에 데이터가 계속 쌓일 경우 조건을 만족하는 데이터 값을 찾을 때 모두 비교하는(full scan) 시간이 오래걸린다. 이러한 문제를 특정 column값을 이용한 index를 생성할 경우 정보를 정렬시킬 수 있기 때문에 검색속도가 훨씬 빨라지게 된다. 주로 RDBMS에서 B+Tree구조로된 index를 사용해 검색 속도를 높인다.
  하지만 장점만 있는것은 아니다. 인덱스를 위한 추가공간이 필요(보통 table 크기의 10%)하고 인덱스 생성에 시간이 소요되며 조회를 제외한 삽입/수정/삭제가 많이발생하면 인덱스를 재구성 해야하므로 성능이 오히려 떨어질 수 있다.

• Index 구조
  index는 Btree B+tree, hash, bitmap 등으로 구현될 수 있다. 보통의 DB는 B+tree구조를 많이 사용한다. Index를 특정 column을 기준으로 생성하면 데이터의 위치정보와 함께 파일로 저장되며, search-key값을 기준으로 정렬된 pointer가 각 개별로 저장된다. 이 때 search-key외에는 pointer만 저장하기 때문에 매우 적은 용량을 사용한다.
  [search-key,pointer와 B+tree]
  

• index 종류
  크게 Cluster index와 Non Cluster index로 나뉜다.
  Cluster index는 특정 column을 기본키로 지정하면 자동으로 cluster index가 생성되고 지정한 column 기준으로 정렬된다. 영어사전 책과 유사하며 테이블당 1개만 생성 가능하다.
  Non Cluster index는 일반 책의 찾아보기와 유사하며 테이블당 여러개의 생성이 가능하다.

  Cluster index & Non Cluster index
  
  

• Index를 만들때 column의 선택기준

1. 조회가 많고 수정/삭제 빈도는 낮을 때 적합(수정/삭제는 인덱스를 정렬해야하므로 성능 부하 발생가능)
2. 카디널리티(특정 집합의 유니크 값의 개수, 카디널리티UP -> 중복도DOWN)가 높은 column이 적합
3. 선택도가 낮은 column이 좋다. 전체 행 중에 조회되는 행의 비율이 높을수록 선택도가 낮아 인덱스에 적합(조회되는 데이터 밀도가 높으면 선택도가 낮아짐)
4. 조회 활용도가 높은(SELECT WHERE절 사용이 많은) 경우 적합

🎄그렇다면 Btree와 B+tree란?

Btree(Balanced-tree)는 부모노드와 자식노드가 2개이상인 균형트리이며 각 노드는 키값과 좌우로 포인터를 가진다. 모든 리프노드들이 같은 레벨에 머무르도록 밸런스를 맞춰주는 특징을 가지며 트리가 편향되지 않아 조회 시 O(logN)의 시간복잡도를 보장해준다.

B+tree는 Btree의 확장개념으로 INNER노드에서는 key값만 저장이 가능하고 끝단의 리프노드에서만 key, data값의 저장을 하는 트리이다. 이 때 리프노드 끼리 Linked list로 연결되어있어서 풀 스캔 시 선형탐색을 하므로 Btree보다 빠르다. B+tree는 INNER노드에 데이터 값을 저장하지 않으므로 Disk Block에 더 많은 INNER노드를 배치할 수 있어 Btree보다 더 나은 성능을 보인다. 또 HashTable은 O(1), B+tree는 O(logn)인데 B+tree를 사용하는 이유는 부등호를 사용하는 쿼리에서 더 효율적이기 때문에 주로 B+tree를 인덱스로 사용한다고 한다. HashIndex는 등호의 값을 찾는 쿼리에 특화되어있어 제한적이다.

💡결론

- Index는 데이터베이스에서 table의 검색 성능을 높여주는 대표적인 방법

- Index는 규모가 크고 중복도가 낮고 삽입/수정/삭제가 자주 발생되지 않는 테이블에서 WHERE나 ORDER BY, JOIN 등이 자주 사용되는 컬럼을 사용해 만들어야 좋다.