인덱스

DB

Index

• RDBMS에서 검색 속도를 높이기 위한 기술
  • SELECT && WHERE 를 이용한 조건 검색 시, 효율적으로 검색하기위해
  • INSERT, UPDATE, DELETE의 성능은 저하된다.
    • insert가 성능을 저하시키는 이유 : 추가적인 쓰기작업과 저장공간을 활용하기 때문에
      
    • update, delete의 행위가 느린이유 : delete는 데이터를 실제 지우지 않고 인덱스안에 사용안함이라고 표시를 하고, index에는 update의 개념이 없고 delete(사용안함표시) 및 insert가 발생한다.
      • update, delete 행위가 느린것이고 행위를 하기위해 데이터를 조회하는것은 인덱스가 있으면 빠르게 조회가 되기 때문에, 인덱스가 있는 컬럼을 기준으로 update, delete를 하는게 좋은 경우가 많다.
• DB의 인덱스에서 쓰이는 대표적인 알고리즘은 이진트리(binary tree), 해시가 있다.
• 사용
• CREATE INDEX {name} ON {table.name} ({column.name1}, {column.name2});
• 모든 DB는 해당 쿼리 실행 시, 인덱스를 사용하는지 안하는지 확인할 수 있는 예약어가 있다.
  • mysql : EXPLAIN

인덱스의 자료구조

• 해시 테이블(Hash Table)
  • 컬럼의 값으로 생성된 해시를 기반으로 인덱스를 구현한다.
  • 시간복잡도가 O(1) 이라 검색이 빠르다.
  • 부등호(<,>) 와 같은 연속적인 데이터를 위한 순차 검색이 불가능하다.</,>
  • =연산에만 특화되어있다.
• B-tree
  • 이진트리(BinaryTree)는 자식노드가 2개 이상인 B-tree를 개선시킨 자료구조이다.
  • 리프노드만 인덱스와 함께 데이터를 가지고, 나머지 노드들은 데이터를 찾기위한 인덱스 키만 갖는다.
  • B-tree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하였다.
  • 해시테이블 보다 나쁜 O(logn)의 시간복잡도를 갖지만 순차검색이 용이하여 주로 사용된다.
  • 리프노드(데이터 노드)의 크기는 인덱스 노드의 크기와 같지 않아도된다.
  • 리프노드안에 데이터가 모두 비게 되는경우(모두 delete 되어) Btree 양쪽 노드에 밸러스가 맞지 않아 재정렬작업이 일어나 성능저하를 일으킬 수 있다.
    

    

    • 이러한 부분을 보완하기 위해 삭제하지않고 마킹을 하는것으로 추측된다.
• MySQL에서 사용하는 B-Tree 인덱스구조에 대해 좀 더 보자.
  • 인덱스의 탐색은 Root -> Branch -> Leaf -> 디스크 저장소로 진행된다.
    
  • team01의 멤버 번호 5번을 찾는다면 child 주소를 따라가서 Leaf노드에서 탐색을한다.
    • 3번부터 조회를 하다가 5번을 찾으면 스캔을 멈춘다.((Range scan)
  • 페이지(블록)는 innoDB엔진에서 읽기 쓰기 작업의 최소 단위이다.(16KB)
  • 인덱스의 두번째 컬럼은 첫번째 컬럼에 의존하여 정렬한다. (하나의 인덱스안에 두개의 컬럼인 경우)
    • 두번째 컬럼의 인덱스는 첫번째 컬럼이 똑같을 때만 의미가 있다.
  • 디스크에서 읽는 것은 메모리에서 읽는것보다 성능이 훨씬 떨어진다.
    • 결국 인덱스 성능을 향상시킨다는 것은 디스크 저장소에 얼마나 덜 접근하게 만드느냐, 즉, 인덱스 Root에서 Leaf까지 오고가는 횟수를 얼마나 줄이는지가 중요하다.
  • 인덱스의 갯수는 3~4개 정도가 적당하다.
    • 너무 많은 인덱스는 insert, update, delete에 성능저하를 유발한다.
    • 공간을 많이 차지한다.
    • 잘못된 인덱스를 선택할 확률이 높아진다.

인덱스 키 값의 크기

• 인덱스의 column의 length가 길수록 성능이 저하된다.
• 인덱스는 페이지로 관리되며, 16KB 크기가 고정되어 있다.
• 만약 인덱스 키의 크기가 16Byte, 자식노드가 가지고 있는 데이터의 주고가 12Byte라면, (16 * 1024) / (16 + 12) = 585 로 하나의 페이지에 585개가 저장될 수 있다.
• 따라서 키값이 커지면 하나의 페이지에 담을 수 있는 데이터의 양이 줄어들게 된다.
• 데이터양이 줄게되면, 조회시 읽어야 하는 페이지수가 많아지게되고 이것은 성능저하의 원인이 된다.

인덱스 기준

• 카디널리티가 높은 -> 낮은순으로 잡는것이 좋다.

카디널리티란?
어느그룹안에 몇개의 요소가 있는지. 즉, 중복된 요소가 많으면 카디널리타가 낮다.

인덱스 조회시 주의 사항

• 인덱스 컬럼이 여러개 설정되어있을때 (하나의 인덱스에 여러개의 컬럼)
  • 모든 컬럼을 조회조건에 포함시켜야 인덱스가 사용되는것은 아니다.
  • 하지만, 첫번째 컬럼은 반드시 조회조건에 포함되어야한다. 그렇지 않으면 인덱스를 타지 않는다.
• between, like, <,> 등 범위조건은 해당컬럼은 인덱스를 타지만, 그 뒤 인덱스 컬럼들은 인덱스가 사용되지 않는다.
  • 즉, group_no, from_date, is_bonus으로 인덱스가 잡혀있는데 조회 쿼리를 where group_no=XX and is_bonus=YY and from_date > ZZ등으로 잡으면 is_bonus는 인덱스가 사용되지 않습니다.
  • 범위 조건으로 사용하지 않는것이 좋다. </,>
• =, in 은 다음 컬럼도 인덱스를 사용한다.
  • in은 =을 여러번 실행시킨 것이다.
  • 단 in의 조건에 서브쿼리를 넣게되면 성능상 이슈가 발생한다.
  • in의 인자로 서브쿼리가 들어가면 서브쿼리의 외부가 먼저 실행되고 in은 체크 조건으로 실행되기 때문에
• AND는 row 수를 줄여주는 역할을 하지만, OR는 비교해야할 row가 늘어나 full table scan이 일어날 확률이 높아진다.
• 컬럼값 그대로르 사용해야만 인덱스가 사용된다.
  • 연산값들은 사용할 수 없다.(ex. where salary * 10 > 150000;)
• null 값의 경우 is null 조건으로 인덱스 Range Scan이 가능하다.

클러스터 인덱스

• 논클러스터 인덱스는 위의 설명과 같은 보통의 인덱스들이다.
• 클러스터 인덱스는 테이블의 PK에 대해서만 적용된다.(PK는 클러스터 인덱스의 기준)
• PK에 의해 레코드 저장 위치가 결정된다.
  • PK값이 변경되면? 레코드의 물리적인 저장위치가 변경 -> 랜덤 액세스 증가 -> IO증가
• 구조
  • 테이블 구조 자체는 B-tree와 유사하다.
  • 논클러스터 인덱스는 Leaf 노드에 데이터의 주소가 있다.
  • 반면, 클러스터 인덱스는 리프노드에 데이터의 모든 컬럼이 다 저장되어있다.
  • 리프페이지가 데이터, 즉, 테이블 자체가 인덱스이다.
  • PK 설정 시, 자동으로 클러스터드 인덱스가 만들어진다.
  • 데이터 입력, 수정, 삭제 시 항상 정렬 상태를 유지한다.
  • 검색속도가 매우가 빠르고, insert, update, delete는 느리다. (논클러스터 인덱스보다)
  • 30% 이내에서 사용해야 좋은 선택도를 가진다.
  • 커버링 인덱스 가능
  • 보조인덱스가 PK를 가지고 있어 인덱스만으로 원하는 데이터를 검색할 수 있다.
  • 구조차이 간단한 그림
    • 클러스터 인덱스
      • 논 클러스터 인덱스
        
        

기타

• 인덱스 컬럼 순서와 조회 컬럼 순서가 다른경우에는 옵티마이저가 조회조건의 컬럼을 인덱스 컬럼 순서에 맞춰 재배열 하는 과정이 추가 되지만 거의차이가 없어 신경쓰지 않아도된다.

더 생각해볼것

• 단일 인덱스 vs 복합 인덱스
  • 단일 인덱스가 여러개인 경우에 위의 주의사항중 해당되는 내용들은?
• 커버링 인덱스란?

참고

• 망나니개발자-기술면접 질문
• 망나니개발자-인덱스란?
• jojoldu-mysql인덱스 정리
• 코딩시그널-클러스터 인덱스와 넌클러스터 인덱스/ 개념 총정리
• 그럼에도 불구하고-클러스터드인덱스