인덱스, B-Tree

인덱스의 존재 이유

조회 성능을 높이기 위해, 특정 컬럼의 값을 정렬/구조화하여 저장해 조회에 필요한 데이터만 조회해 디스크 I/O를 최소화하기 위함. 따라서 인덱스가 있다면 WHERE, JOIN, ORDER BY .. 등의 스캔 범위를 줄일 수 있다.

B+ Tree

데이터를 조회할 때 디스크 I/O를 최소화하기 위해 이진 탐색 트리를 변형해, 하나의 부모가 N개의 자식을 가질 수 있으며 루트 - 중간 - 리프 레벨로 구성된 균형 트리이다.

각 노드는 설정한 키를 중심으로 정렬되어 있으며 하나의 페이지 단위로 구성된다. B-Tree는 중간 노드들이 데이터가 아닌 키들로만 구성되어 있는데, 이를 통해 하나의 노드(페이지)에 들어갈 데이터의 양을 최대한 늘려 트리의 높이(=디스크 I/O 횟수)를 줄이기 위함이다.

궁극적으로는 키값을 기준으로 미리 정렬된 색인 구조를 만들어 → 디스크에 저장된 모든 데이터를 찾는 것이 아닌 필요한 데이터만 접근해 랜덤 I/O를 줄이기 위해 있는 것이다.

클러스터 인덱스 vs 논클러스터드 인덱스 (feat. 인덱스가 비효율적인 경우)

기본적으로 개발자가 설정한 보조 인덱스 B+Tree의 경우 리프 노드에는 해당 레코드의 실체 혹은 물리 주소가 아닌 PK가 저장되어있다. 이유는 레코드의 물리적 위치나 실제값이 수정될 때마다 설정된 인덱스 트리의 모든 리프 노드를 수정해야 하는 것을 방지하기 위해서다.

하지만 실제 데이터는 클러스터 인덱스 B+Tree를 기준으로 구성되어 있으며, PK 기준으로 정렬되어 있고 리프 노드에 실제 데이터가 존재한다. 따라서 인덱스를 탄다고 한다면 보조 인덱스의 리프노드에서 PK 찾기 → 클러스터 인덱스에서 PK 기반으로 리프 노드에서 데이터 조회가 이루어 지는 것이다.

직접 데이터를 읽는 것과 인덱스를 통해서 읽는 것의 트레이드오프는 다음과 같다. ( Random I/O는 디스크 헤더를 계속해서 멀리까지 옮겨야하기 때문에 비용이 높다. Sequential I/O는 디스크 헤드를 블록따라 쭉 이동시키면 되므로 비용이 낮다. )

• 인덱스가 없는 경우
  • PK로 읽는 경우 : 클러스터 인덱스에서 트리의 높이 만큼만 I/O를 수행하며 리프 노드(페이지)의 데이터가 위치한 1개의 페이지만 읽는다.
  • PK가 아닌 값으로 읽는 경우. : 클러스터 인덱스의 리프 노드 연결리스트의 처음~끝까지 읽어가며 Sequential I/O를 수행한다. 1번의 I/O가 아니고 링크드 리스트따라 순차적으로 읽는 것이다.
• 인덱스가 있는 경우
  • 1개의 레코드를 읽을 때, 보조 인덱스 B+Tree만큼 읽고 → 클러스터 인덱스 트리의 탐색으로 Random I/O 비용
  • N개의 데이터를 읽는다면 N*(보조 인덱스 + 클러스터 인덱스) 읽는 비용이 드는 것이다.

따라서, 인덱스를 통해 전체 읽는 데이터의 비율이 20 ~ 25%를 넘어섰다면 전체 풀스캔하는 것이 효율적이다. 옵티마이저가 알아서 실행 계획을 세운다.

키를 설계할 때 고려사항

선택도

• 전체 대비 특정 컬럼의 고유한 값의 비율을 의미한다. ( 카디널리티는 고유한 갯수만을 뜻한다. )

  • 100 * ( 특정값의 매칭 개수 / 전체 개수 )

  • 매칭 비율이 낮을수록 선택도가 높은 것이다. → 매칭된 개수만큼만 디스크에 I/O하면 되니까 효율적

  • 예시

    // payment_status로 인덱스 설정
    SELECT * FROM orders WHERE payment_status = 'paid';
    

    payment_status로 인덱스 설정되어 있는데 선택도가 95%다. 그렇다면 95%의 데이터에 랜덤 I/O를 수행해야 한다.