[MySQL] B-Tree 인덱스

디스크 읽기 방식

랜덤 I/O와 순차 I/O

랜덤 IO와 순차 IO 모두 하드 디스크 드라이브의 플래터를 돌려 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것은 동일합니다.

그러나 순차 IO가 3개의 페이지를 디스크에 기록하기 위해 1번의 시스템 콜을 호출한다면, 랜덤 IO는 3번의 시스템 콜을 호출합니다. 즉, 디스크 헤드를 3번 움직이며 3배의 속도 차이가 발생합니다.

쿼리를 튜닝해서 랜덤 IO를 순차 IO로 바꾸는 방법은 많지 않습니다. 쿼리 튜닝의 목적은 랜덤 IO 자체를 줄이는 것이며 꼭 필요한 데이터만 읽도록 쿼리를 개선하는 것을 의미합니다.

인덱스란

인덱스란 컬럼의 값과 해당 레코드가 저장된 주소를 키-값 쌍으로 만들어 둔 것을 의미합니다. 컬럼의 값을 기준으로 정렬해서 보관하기 때문에 책의 제일 마지막에 있는 찾아보기와 같습니다.

인덱스는 이미 정렬되어 있기 때문에 원하는 값을 빠르게 찾아올 수 있습니다. 그러나 데이터가 저장될 때마다 값을 정렬해야 하므로 INSERT, UPDATE, DELETE 문장의 처리가 느려집니다.

인덱스는 역할 또는 알고리즘, 데이터 중복 허용 여부로 구분할 수 있습니다. 역할별로 구분했을 때는 클러스터링 인덱스와 논 클러스터드 인덱스로 나눌 수 있습니다.

클러스터드 인덱스(Clustered Index)

• 유사한 값을 가진 컬럼을 기준으로 정렬되어 모여있는 인덱스
• InnoDB의 프라이머리 키에 자동으로 클러스터링 인덱스가 생성됨
  

논 클러스터드 인덱스(Non-clustered index, Secondary index)

• 프라이머리 키를 제외한 나머지 인덱스
• InnoDB는 레코드가 저장된 주소 대신 프라이머리 키를 논리적인 주소로 사용함
  

알고리즘 별로 구분했을 때는 B-Tree 인덱스와 Hash 인덱스로 나눌 수 있습니다.

B-Tree 알고리즘

• 인덱스 값을 변형하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘
  

Hash 알고리즘

• 컬럼의 값으로 해시값을 계산해서 인덱싱하는 알고리즘
• 빠른 검색을 지원하지만 원래의 값을 변행해서 인덱싱하기 때문에 프리픽스 검색, 범위 검색에는 해시 인덱스를 사용할 수 없음
  

데이터 중복 허용 여부로 구분했을 때는 유니크 인덱스와 유니크하지 않은 인덱스로 나눌 수 있습니다.

B-Tree 인덱스

B-Tree는 컬럼의 원래 값을 변형시키지 않고 인덱스 구조체 내에서는 항상 정렬된 상태로 유지합니다. 일반적인 용도로 가장 많이 사용하는 인덱스입니다.

구조 및 특성

B-Tree의 구조는 최상위에 루트 노드(Root node), 트리의 가장 하위에 리프 노드(Leaf node), 루트와 리프 사이의 중간 노드인 브랜치 노드(Branch node)로 구성되어 있습니다.

데이터베이스에 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되며, 리프 노드에는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있습니다.

클러스터드 인덱스의 경우 인덱스 키 값의 순서대로 데이터 파일의 레코드도 정렬되어 저장되지만 논 클러스터드 인덱스는 임의의 순서로 저장됩니다.

InnoDB에서 인덱스는 프라이머리 키를 논리적인 주소값으로 사용합니다. 따라서 모든 세컨더리 인덱스의 검색에서 데이터 레코드를 읽기 위해서 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한 번 검색하는 과정을 거칩니다.

인덱스 키 추가 및 삭제

인덱스 키 추가

키 값에 따라 B-Tree상의 저장될 위치가 걸졍되면 키-주소 쌍은 리프 노드에 저장됩니다. 리프 노드가 꽉 차서 더는 저장할 수 없는 경우, 리프 노드가 분리되며 이러한 작업은 상위 브랜치 노드까지 처리 범위가 넓어집니다.

• 인덱스 추가의 대락적인 비용은 레코드 추가를 1로 두었을 때 1.5 정도
• 정확한 비용을 알기 위해서는 테이블의 컬럼 수, 컬럼의 크기, 인덱스 컬럼의 특성 등을 확인해야 함
• InnoDB는 체인지 버퍼를 이용하여 인덱스 키 추가 작업을 지연시킬 수 있음
  • 단, 중복 여부를 확인해야하는 경우 즉시 B-Tree에 반영
    
    

인덱스 키 삭제

키 값이 저장된 B-Tree의 리프 노드를 찾아서 삭제 마크만 하면 작업이 완료됩니다. 마킹된 인덱스 키 공간은 방치하거나 재활용할 수 있습니다.

• MySQL 5.5 이상 버전 InnoDB에서는 이 작업 역시 체인지 버퍼에서 버퍼링 되어 지연 처리될 수 있음
  
  

인덱스 키 변경

B-Tree의 키 값 변경 작업은 먼저 키 값을 삭제한 후, 새로운 키 값을 추가하는 형태로 처리됩니다. 물론 체인지 버퍼를 활용해 지연 처리 될 수 있습니다.

인덱스 키 검색

인덱스 검색은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행하며, 이를 트리 탐색이라 합니다. 트리 탐색은 SELECT 뿐만 아니라 UPDATE, DELETE를 처리하기 위해 해당 레코드를 검색하는 경우에도 사용됩니다.

• B-Tree 검색은 완전 일치 또는 프리픽스 일치, 부등호 비교에서 사용 가능
• 다음의 경우 B-Tree 사용 불가
  • 키 값의 뒷부분 검색
  • 함수, 연산의 결과를 이용하여 값을 변경시키는 경우
    
    

InnoDB는 레코드 잠금이나 넥스트 키락이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현되어 있습니다. 따라서 UPDATE, DELETE 문장을 처리하기 위해 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠그는 것에 유의해야 합니다.

B-Tree 인덱스 사용에 영향을 미치는 요소

인덱스 키 값의 크기

InnoDB는 디스크에 데이터를 저장하는 가장 기본 단위를 페이지(Page) 또는 블록(Block)이라고 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 됩니다. 또한 페이지는 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 합니다.

• B-Tree는 자식 노드의 개수가 가변적으로 변함
• 자식 노드의 수는 인덱스의 페이지 크기와 키 값의 크기에 따라 결정
• 페이지 크기(innodb_page_size)의 기본값은 16KB
  
  

자식 노드 주소는 복합적인 정보가 담긴 영역이며, 페이지의 종류별로 6바이트에서 12바이트까지 다양한 크기의 값을 가질 수 있습니다.

• 위의 경우 하나의 인덱스 페이지에 16*1024(10+12)=744개의 인덱스를 저장

• 키 값의 크기가 두 배인 20바이트로 늘어나게 되면 한 페이지에 512개를 저장

• SELECT를 통해 600개의 레코드를 읽는다면 후자는 최소 2번의 디스크 읽기가 필요

  
  

• 키 값의 크기가 커짐 -> 디스크 읽기 횟수 증가 -> 처리 시간 증가

• 키 값의 길이가 길이지면 인덱스의 전체적인 크기도 증가

• InnoDB 버퍼 풀의 크기는 제한적, 따라서 인덱스의 크기가 커질수록 메모리에 캐시해 둘 수 있는 레코드 수는 적어짐

  
  

B-Tree 깊이

B-Tree 인덱스의 깊이를 직접 제어할 수 있는 방법은 없습니다. 인덱스 키 값이 커질수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수가 적어지고, 같은 레코드 건수를 가지고 있더라도 깊이가 깊어져서 디스크 읽기가 더 많이 필요할 수 있습니다.

선택도(기수성)

선택도(Selectivity) 또는 기수성(Cardinality)은 유사한 의미로 사용되며, 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미합니다. 인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리됩니다.

동일한 테이블에 똑같은 쿼리를 실행하더라도 유니크한 값의 개수에 따라 1건의 레코드를 읽어오기 위해 999건의 불필요한 레코드를 더 읽을 수도 있고, 9건의 불필요한 레코드만을 더 읽을 수도 있습니다. 이처럼 인덱스에서 유니크한 값의 개수는 인덱스나 쿼리의 효율성에 큰 영향을 미칩니다.

읽어야 하는 레코드의 건수

일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 읽는 것보다 4~5배 정도 비용이 더 많이 드는 작업으로 예측합니다. 즉, 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블을 직접 읽어서 필요한 레코드만 필터링 방식으로 처리하는 것이 효율적입니다.

B-Tree 인덱스를 통한 데이터 읽기

인덱스 레인지 스캔

인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식입니다. 루트 노드에서부터 비교를 시작해 브랜치, 리프 노드의 레코드 시작 지점을 찾으면 그때부터는 리프 노드의 레코드만 순서대로 읽으면 됩니다.

스캔하다가 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아서 다시 스캔합니다. 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝냅니다.

인덱스의 리프 노드에서 검색 조건에 일치하는 건들은 리프 노드에 저장된 레코드 주소로 데이터 파일의 레코드를 읽어오는데, 레코드 한 건 단위로 랜덤 IO가 한 번씩 일어납니다.

따라서 인덱스 레인지 스캔은 다음과 같이 크게 3단계를 거칩니다.

1. 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다. 이 과정을 인덱스 탐색(index seek)이라고 한다.
2. 1번에서 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 쭉 읽는다. 이 과정을 인덱스 스캔(index scan)이라고 한다.
3. 2번에서 읽어 들인 인덱스 키와 레코드 주소를 이용해 레코드가 저장된 페이지를 가져오고, 최종 레코드를 읽어 온다.
   • 커버링 인덱스의 경우 마지막 과정이 생략될 수 있음
   • 디스크 레코드를 읽지 않아도 되기에 랜덤 읽기가 줄어들고 성능은 그만큼 향상됨
     
     

인덱스 풀 스캔

인덱스를 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라 합니다. 대표적으로 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우 이 방식이 사용됩니다.

• 쿼리가 인덱스에 명시된 컬럼만으로 조건을 처리할 수 있는 경우 주로 이 방식이 사용
• 데이터 레코드까지 모두 읽어아 한다면 절대 이 방식으로 처리되지 않음
  
  

루스 인덱스 스캔

인덱스 레인지 스캔과 인덱스 풀 스캔은 타이트(Tight) 인덱스 스캔으로 분류됩니다. 루스 인덱스 스캔은 듬성듬성하게 인덱스를 읽는 것을 의미합니다.

• 인덱스 레인지 스캔과 비슷하게 동작하지만 중간에 필요하지 않은 인덱스 키 값은 무시(SKIP) 하고 다음으로 넘어가는 형태로 처리
• 일반적으로 GROUP BY 또는 집합 함수 중 MAX(), MIN()을 최적화 하는 경우에 사용
  
  

SELECT dept_no, MIN(emp_no)
FROM dept_emp
WHERE dep_no BETWEEN 'd002' AND 'd004'
GROUP BY dept_no;

인덱스 스킵 스캔

인덱스의 핵심은 값이 정렬돼 있다는 것이며, 이로 인해 인덱스를 구성하는 컬럼의 순서가 매우 중요합니다.

MySQL 8.0 버전부터는 옵티마이저가 인덱스의 컬럼 순서가 조건 절의 컬럼 순서와 맞지 않아도 인덱스 검색이 가능하게 해주는 인덱스 스킵 스캔(Index skip scan) 최적화 기능이 도입되었습니다.

• 루스 인덱스 스캔은 GROUP BY 작업을 처리하기 위해 인덱스를 사용하는 경우에만 적용
• 인덱스 스킵 스캔은 WHERE 조건절의 검색을 위해 사용 가능
  
  

다음과 같은 인덱스가 있는 상태에서 쿼리를 실행하면 인덱스 스킵 스캔을 사용합니다.

INDEX ix_gender_birthdate (gender, birth_date);

SELECT gender, birth_date
FROM employees 
WHERE birth_date >= '1965-02-01';

옵티마이저는 gender 컬럼의 유니크한 값을 모두 조회해서 주어진 쿼리에 gender 컬럼의 조건을 추가하여 쿼리를 다시 실행하는 형태로 처리합니다.

옵티마이저가 인덱스 스킵 스캔을 사용하게 되면 Extra 컬럼에는 Using index for skip scan이라는 문구가 표시됩니다.

인덱스 스킵 스캔은 단점은 다음과 같습니다.

• WHERE 조건절에 조건이 없는 인덱스의 선행 컬럼은 유니크한 값의 개수가 적어야 함
  • 유니크한 값의 개수가 매우 많다면 옵티마이저는 인덱스에서 스캔 시작 지점을 검색하는 작업이 많이 필요
  • 쿼리 처리 성능이 저하될 수 있음
• 쿼리가 인덱스에 존재하는 컬럼만으로 처리 가능해야 함(커버링 인덱스)
  • 인덱스 키 컬럼 외에 나머지 컬럼도 필요하여 스킵 스캔 사용 불가
    
    

다중 컬럼(Multi-column) 인덱스

두 개 이상의 컬럼으로 구성된 인덱스를 다중 컬럼 인덱스 또는 복합 컬럼 인덱스라고 합니다. 복합 컬럼 인덱스에서 인덱스의 두 번째 컬럼은 첫 번째 컬럼에 의존해서 정렬되어 있습니다.

B-Tree 인덱스의 정렬 및 스캔 방향

인덱스의 정렬

MySQL 8.0 버전 부터는 인덱스의 컬럼 단위로 정렬 순서를 혼합한 인덱스 생성을 제공합니다.

인덱스 스캔 방향

옵티마이저는 인덱스의 정렬 방향과 무관하게 쿼리가 인덱스를 사용하는 시점에 필요에 따라 정순 또는 역순으로 인덱스를 사용합니다.

내림차순 인덱스

InnoDB에서 인덱스 역순 스캔은 다음의 이유로 정순 스캔에 비해 느립니다.

• 페이지 잠금이 인덱스 정순 스캔(Forward index scan)에 적합한 구조
• 페이지 내에서 인덱스 레코드가 단방향으로만 연결된 구조
  
  

B-Tree 인덱스의 가용성과 효율성

비교 조건의 종류와 효율성

다중 컬럼 인덱스에서 각 컬럼의 순서와 컬럼에 사용된 조건이 동등 비교인지, 범위 조건인지에 따라 인덱스 컬럼의 활용 형태가 달라지며, 효율 또한 달라집니다.

다음의 쿼리를 실행했을 때 인덱스 컬럼의 순서에 따라 서로 다른 스캔의 범위를 가집니다.

SELECT * FROM dept_emp
WHERE dept_no='d002' AND emp_no >= 10114;

• 첫번째 인덱스에서 dept_no, emp_no 컬럼은 작업 범위 결정 조건으로 사용
• 두번째 인덱스는 dept_no 컬럼은 작업 범위 결정 조건의 역할을 수행하고, emp_no 컬럼은 거름종이 역할만 하는 필터링 조건으로 사용
  
  

작업 범위를 결정하는 조건은 쿼리 처리 성능을 높이지만 필터링 조건은 쿼리 처리 성능을 높이지는 못하고, 오히려 쿼리 실행 성능을 느리게 만들 때가 있습니다.

인덱스의 가용성

B-Tree 인덱스의 특징은 왼쪽 값에 기준해서 오른쪽 값이 정렬된다는 것입니다. 따라서 값의 왼쪽 부분이 없으면 인덱스 레인지 스캔 방식의 검색은 사용할 수 없습니다.

가용성과 효율성 판단

B-Tree 인덱스의 특성상 다음 조건에서는 사용할 수 없습니다. 단, 경우에 따라 체크 조건으로 사용할 수는 있습니다.

• NOT-EQUAL로 비교한 경우(<>, NOT INT, NOT BETWEEN, IS NOT NULL)
• LIKE '%??'(뒷부분 일치) 형태로 문자열 패턴이 비교된 경우
• 스토어드 함수나 다른 연산자로 인덱스 컬럼이 변형된 후 비교된 경우
• NOT_DETERMINSTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우
• 데이터 타입이 서로 다른 비교(인덱스 컬럼의 타입을 변환해야 비교가 가능한 경우)
• 문자열 데이터 타입의 콜레이션이 다른 경우
  
  

다중 컬럼 인덱스의 경우 다음의 상황에서 사용할 수 없습니다.

INDEX ix_test (col_1, col_2, ..., col_n)

• 작업 범위 결정 조건으로 인덱스를 사용하지 못하는 경우
  • col_1에 대한 조건이 없는 경우
  • col_1 비교 조건이 위의 인덱스 사용 불가 조건 중 하나인 경우
• 작업 범위 결정 조건으로 인덱스를 사용하는 경우
  • col_1 ~ col_(i-1) 컬럼까지 동등 비교 형태(= 또는 IN)로 비교
  • col_i 컬럼에 대해 다음 연산자 중 하나로 비교
    • 동등 비교(= 또는 IN)
    • 크다 작다 형태(> 또는 <)
    • LIKE로 앞부분 일치(LINK '??%')
      
      

두 가지 조건을 만족하는 쿼리는 col_1부터 col_i까지 작업 범위 결정 조건으로 사용되고, col_(i+1)부터 col_n까지의 조건은 체크 조건으로 사용됩니다.

참고

Real MySQL 8.0 8장 인덱스_8.1 디스크 읽기 방식, 8.2 인덱스란?, 8.3 B-Tree 인덱스