인덱스

DB의 성능에 무엇이 중요한가

• 디스크 랜덤 I/O 횟수를 줄이는 것이 중요하다.
• 보통 db는 디스크에 저장되는데, 이 DB에 데이터를 저장하거나 읽을 려면 디스크의 플래터원판의 헤더를 움직여서 데이터를 읽게된다.
• DB에서 데이터를 읽고 쓰는 작업은 보통 랜덤 I/O이다.
• 순차 I/O는 한번에 많은 데이터를 읽는 경우이고, 랜덤 I/O는 헤더를 이곳저곳 움직이면서 데이터를 읽는다. (이 때 시스템콜이 발생한다.) 헤더를 많이 움직일 수록 성능에 영향이 가기 때문에 이 랜덤 I/O 횟수를 줄여야 한다.
• 랜덤 I/O 횟수를 줄이기 위해서는 데이터를 필요한 데이터를 한번에 읽는 것이 중요하다. 따라서 인덱스를 적용하여 인덱스 레인지 스캔과 같은 방식으로 필요한 데이터만 조회하도록 해야한다.

인덱스가 필요한 이유

빠른 검색을 위해서 사용

Index

• 책의 색인과 같다. 칼럼의 값과 레코드가 저장된 주소를 키값쌍으로 삼아 인덱스를 만들어 둔다.
• 책의 색인으로 비교하자면, 책의 내용을 데이터파일이라고 하고 책의 색인에 잇는 목차들이 칼럼의 값과 데이터 파일에 저장된 레코드 주소라고 할 수 있다. 또한 이 둘의 공통점은 정렬이다.
• 목적 : 빠른 검색을 위해서 사용
• 장점 : 빠른 검색이 가능
• 단점 : 생성, 수정, 변경이 많은 데이터의 경우 오히려 인덱스 크기가 커지고 빠른 검색이 불가능하게 된다

인덱스 알고리즘 B-Tree, Hash 알고리즘

인덱스를 어떻게 관리하느냐

• B-Tree
  • 설명 : B-Tree는 칼럼의 원래 값을 변형시키지 않고, 인덱스 구조체 내에서 항상 정렬된 상태로 유지하는 Self Balancing Binary Search Tree 형태의 자료구조이다.
    • 삽입,삭제, 검색 모두 트리 자기 혼자서 작은 높이를 유지하도록 함. 높이가 O(log N)이며, 모든 연산이 O(log N)이 든다.
    • 반면 그냥 이진탐색 트리는 편향일 수 있어서 삽입 삭제 검색 모두 평균 O(log n) 최악의경우 O(n)이 걸린다.
  • 루프노드, 브랜치 노드, 리프노드의 구조로 되어있으며 리프노드는 항상 실제 데이터 레코드 주소값을 갖고있다.
  • 인덱스 키값 ex. Aamer, Babette는 모두 정렬되어있지만 실제로 데이터 파일의 레코드는 정렬돼있지 않고, 임의의 순서로 저장되어있다. insert 순으로 저장되는 것도 아니다. 가능한 한 빈공간을 재활용해서 저장되지만 InnoDB 테이블에서는 기본적으로 레코드는 클러스터링되어 디스크에 저장되므로 기본적으로는 프라이머리 키 순서로 정렬되어 저장된다.
  • 장점
    • Hash 인덱스 알고리즘과는 달리 값의 앞부분 을 검색하는 전방일치 Prefix나 범위 검색에 사용할 수 있다. Hash 인덱스는 동등 비교와 전체 키 검색 사용이 가능하다.
    • 인덱스에 원본값이 정렬된 상태로 저장되어있어서 order by에서 이를 이용할 수 있다.
  • 단점 :
    • 매번 정렬과정을 거친다.
    • 인덱스 생성, 삭제, 수정이 많을 수록 인덱스의 효율이 떨어진다.
      • 생성 : 적절한 정렬 위치를 검색한다음 그 위치에 인덱스를 넣고 뒤에 있는 인덱스들의 위치를 하나씩 다 아래로 이동해야 한다. 또한, 리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리돼야 하는데 이는 상위 브랜치 노드까지 처리 범위가 넓어진다. 이러한 작업탓에 쓰기 비용이 많이 든다.
      • 삭제 : 키 값이 저장된 B-Tree의 리프노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료된다. 삭제 마킹된 인덱스 키 공간은 계속 방치되거나 재활용할 수 있다. 그리고 이 작업 역시 디스크 쓰기가 필요하므로 디스크 I/O가 필요하다.
      • 수정 : 삭제 + 추가를 합한 것. 먼저 키 값을 삭제한 후, 다시 새로운 키값을 추가하는 형태이다.
  • 왜 B-Tree를 사용하는지
    • Hash 인덱스는 전체 키 하나를 찾을 때는 O(1)로 빠를 수 있지만,
    • 정렬의 특징이 없고 원래의 컬럼값이 저장되지 않는다.
    • 따라서 범위 검색이나 전방일치 Prefix 검색이 불가하기 때문에 B-Tree를 사용
• Hash
  • 설명 : 칼럼의 값으로 해시값을 계산해서" 인덱싱하는 알고리즘으로, 매우 빠른 검색을 지원한다. 하지만 값을 변형해서 인덱싱하므로 "전방 일치(Prefix) 와 같이 값의 일부만 검색하거나 범위를 검색"할 때는 해시 인덱스를 사용할 수 없다.
  • 장점 : 동등 검색 시에는 매우 빠른 검색이 가능하다. 해싱해서 인덱스를 만들기 때문에 O(1) 복잡도를 가진다.
  • 단점 : 전방일치 Prefix, 범위 검색이 되지 않는다. 해시 인덱스는 컬럼값을 해싱해서 그 해싱값을 인덱싱하는 알고리즘이기 때문에 원래의 칼럼의 변경이 된다. 그래서, 전방일치나 범위 검색이 되지 않는 이유는 원래의 컬럼값이 변경이 되며 순서도 정렬되지 않기 때문에 불가능한 것이다.

클러스터드 인덱스

• 설명 : InnoDB의 모든 테이블은 기본적으로 프라이머리 키를 기준으로 크러스터링되어 저장된다. 즉, 프라이머리 키 값의 순서대로 디스크에 저장된다는 뜻이다. 이를 클러스터드 인덱스라고 표현한다.

Composite Index

인덱스로 설정하는 필드의 속성이 중요하다. title, author 이 순서로 인덱스를 설정한다면 title 을 search 하는 경우, index 를 생성한 효과를 볼 수 있지만, author 만으로 search 하는 경우, index 를 생성한 것이 소용이 없어진다. 따라서 SELECT 질의를 어떻게 할 것인가가 인덱스를 어떻게 생성할 것인가에 대해 많은 영향을 끼치게 된다.

프라이머리 인덱스, 세컨더리 인덱스

• 프라이머리 인덱스
  • InnoDB의 경우 프라이머키에 클러스터링 인덱스를 만들어준다. 이를 프라이머리 인덱스라고 한다.
  • 클러스터링이란 여러개를 하나로 묶는다는 의미로 사용된다. 즉, 프라이머리 키를 기준으로 순서대로 디스크에 저장된 것을 프라이머리 인덱스라고 한다.
  • 결과적으로 프라이머리 키에 대해 인덱스가 걸려있어서 프라이머리 키를 이용한 인덱스 레인지 스캔을 상당히 빠르게 처리할 수 있다.
• 세컨더리 인덱스
  • 프라이머리가 아닌 인덱스를 세컨더리 인덱스라고 한다.이 경우에는 인덱스의 값에 레코드의 주소 대신 프라이머리 키값을 논리적인 주소를 저장한다. 그래서 세컨더리 인덱스를 사용하면 마지막엔 반드시 프라이머리 인덱스를 거친다.

인덱스의 성능

• 인덱스의 성능을 위해서는 Cardinality가 중요하다.
  • 설명 : Cardinality가 높다는 것은 유니크한 인덱스 값이 많은 것을 의미한다. 유니크한 값이 많을 수록 검색 대상이 줄어들기 때문에 빠른 처리가 가능하다.
• 인덱스의 추가나 변경이 많은 경우에는 오히려 성능에 영향을 주기 때문에 되도록이면 조회용일 때 인덱스를 사용한다.
• 인덱스를 사용하는 이유는 빠른 검색이다. 한번에 원하는 데이터를 빠르게 스캔하는 것이 중요하다. 즉, 인덱스 레인지 스캐으로 필요한 범위만 스캔해야 한다.
• 인덱스를 타도 마지막에는 필요한 데이터를 가져오기 위해 실제 데이터 파일의 레코드를 가져오는 경우가 있다. 이런 경우 레코드 한건 한건 단위로 랜덤 I/O가 한번씩 실행된다. 따라서 테이블의 데이터의 많은 레코드를 인덱스를 통해 읽어야한다면 차라리 테이블로 직접 인덱스말고 그냥 읽는 게 나을 수 있다.

인덱스 삽입, 삭제 성능이 느린 이유를 B-Tree와 연관지어 설명

• 생성 : 적절한 정렬 위치를 검색한다음 그 위치에 인덱스를 넣고 뒤에 있는 인덱스들의 위치를 하나씩 다 아래로 이동해야 한다. 또한, 리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리돼야 하는데 이는 상위 브랜치 노드까지 처리 범위가 넓어진다. 이러한 작업탓에 쓰기 비용이 많이 든다.

• 삭제 : 키 값이 저장된 B-Tree의 리프노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료된다. 삭제 마킹된 인덱스 키 공간은 계속 방치되거나 재활용할 수 있다. 그리고 이 작업 역시 디스크 쓰기가 필요하므로 디스크 I/O가 필요하다.

• 수정 : 삭제 + 추가를 합한 것. 먼저 키 값을 삭제한 후, 다시 새로운 키값을 추가하는 형태이다.

참고

Real MySQL

B-tree - Wikipedia