[Real Mysql 8.0] B-Tree 인덱스

1. B-Tree (Balanced Tree) 구조 및 특성

B-Tree 인덱스를 제대로 사용하려면 기본적인 구조를 알아야 한다.
B-Tree는 최상위에 "루트 노드(Root node)"가 존재한다.
트리 구조의 가장 하위에 있는 노드를 "리프 노드(Leaf node)"라 한다. 
트리 구조에서 루트 노드도 아니고 리프 노드도 아닌 중간 노드를 "브랜치 노드(Branch node)"라고 한다.

 

인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값(프라이머리 키)을 가지고 있다. 나머지 칼럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 한다. 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한번 검색해야 한다.

 

루트 노드(Root node) - 브랜치 노드(Branch node) - 리프 노드(Leaf node) -> 데이터 파일

2. B-Tree 인덱스 키 추가 및 삭제

테이블의 레코드를 저장하거나 변경하는 경우, 인덱스 키 추가나 삭제 작업이 발생한다. 

• 인덱스 키 추가
  • B-Tree에 저장될 때는 저장될 키 값을 이용해 B-Tree상의 적절한 위치를 검색해야 한다. 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장한다. 리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리돼야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어진다. 이런 작업 탓에 B-Tree는 상대적으로 쓰기 작업에 비용이 많이 든다.

• 인덱스 키 변경
  •  B-Tree의 키 값 변경 작업은 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리된다.
• 인덱스 키 검색
  • INSERT, UPDATE, DELETE 작업을 할 때 인덱스 관리에 따르는 추가 비용을 감당하면서 인덱스를 구축하는 이유는 바로 빠른 검색을 위해서다.
  • * InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키락(갭락)이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼 있다. 따라서 UPDATE나 DELETE 문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠근다. 심지어 테이블의 모든 레코드를 잠글 수도 있다.

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

• 인덱스 키 값의 크기
• B-Tree의 깊이
• 기수성(Cardinality - 카디널리티) 
  • 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미한다.
  • 전체 인덱스 키 값은 100개인데, 그중에서 유니크 한 값의 수는 10개라면 기수성은 10이다.
• 읽어야하는 레코드 건수

 

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

• 인덱스 레인지 스캔
  • 인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다. 루트노드에서부터 비교를 시작해 브랜치 노드를 거치고 최종적으로 리프 노드 까지 찾아 들어가야만 비로소 필요한 레코드의 시작 지점을 찾을 수 있다. 이처럼 차례대로 쭉 읽는 것을 스캔이라고 표현한다. 만약 스캔하다가 리프 노드의 끝까지 읽으면 리프노드 간의 링크를 이용해 다름 리프 노드를 찾아서 다시 스캔한다.
    지금 까지는 인덱스만을 읽는 경우를 보여주었지만 리프 노드를 스캔하면서 실제 데이터 파일의 레코드를 읽어 와야 하는 경우도 많다. 인덱스의 리프 노드에서 검색 조건이 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요한데, 레코드 한 건 한 건 단위로 랜덤 I/O가 한 번씩 일어난다. 그리고 인덱스를 통해 읽어야 할 데이터가 20%~25%를 넘으면 인덱스를 통한 읽기보다 테이블의 데이터를 직접 읽는 것이 더 효율적인 처리 방식이 된다.
• 인덱스 풀 스캔
  • 인덱스 레인지 스캔과 달리 인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라고 한다. 대표적으로 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 칼럼이 아닌 경우 인덱스 풀 스캔 방식이 사용된다.
• 루스 인덱스 스캔
  • 루스 인덱스 스캔은 인덱스 레인지 스캔과 비슷하게 작동하지만 중간에 필요치 않은 인덱스 키 값은 무시하고 다음으로 넘어간다. 일반적으로 GROUP BY 또는 집합함수 가운데 MAX(), MIN() 함수에 대해 최적화를 하는 경우에 사용된다.
    
    SELECT dept_no, MIN(emp_no)
    FROM dept_emp
    WHERE dep_no BETWEEN 'd002' AND 'd004'
    GROUP BY dept_no;
    
    위 dept_emp 테이블은 dept_no와 emp_no라는 두 개의 칼럼으로 인덱스가 생성돼 있다. 또한 이 인덱스는 (dept_no, emp_no) 조합으로 정렬까지 돼 있다.
    dep_no 그룹별로 첫 번째 레코드의 emp_no 값만 읽으면 된다. 즉 인덱스에서 WHERE 조건을 만족하는 범위 전체를 다 스캔할 필요가 없다는 것을 옵티마이저는 알고 있다.
• 인덱스 스킵 스캔
  • 인덱스의 핵심은 값이 정렬돼 있다는 것이며, 이로 인해 인덱스를 구성하는 칼럼의 순서가 매우 중요하다. 
  • employees 테이블에 다음과 같은 인덱스를 생성해보자
    • ALTER TALE employees ADD INDEX ix_gender_birthdate (gender, birth_date);
  • 이 인덱스를 사용하려면 WHERE 조건절에 gender칼럼에 대한 비교 조건이 필수이다
    1. 인덱스를 사용할 수 있는 쿼리
       • SELECT * FROM employees WHERE gender = 'M' AND birth_date >= '1965-02-01';
         
    2. 인덱스를 사용하지 못하는 쿼리
       • SELECT * FROM employees WHERE birth_date >= '1965-02-01';
       • 주로 이런 경우 birth_date 칼럼부터 시작하는 인덱스를 새로 생성해야만 했다.
  • MySql 8.0부터 gender 칼럼을 건너 뛰어서  birth_date 칼럼만으로도 인덱스 검색이 가능하게 해주는 인덱스 스킵 스캔 최적화 기능이 도입됐다.
  • 인덱스 스킵 스캔의 한계점
    • WHERE 조건절에 조건이 없는 인덱스의 선행 컬럼의 유니크한 값의 개수가 적어야함.
    • 쿼리가 인덱스에 존재하는 칼럼만으로 처리 가능해야함

 

 

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

• 인덱스를 생성할 때 설정한 정렬 규칙에 따라서 인덱스의 키 값은 항상 오름차 순이거나 내림차순으로 정렬되어 저장된다.
• 인덱스를 어느 방향으로 읽을지는 쿼리에 따라 옵티마이저가 실시간으로 만들어 내는 실행 계획에 따라 결정된다.
• 인덱스의 정렬 8.0 버전부터는 정렬 순서를 혼합한 인덱스도 생성 할 수 있다.
  • CREATE INDEX ix_teamname ON employees (team_name ASC, user_score DESC);

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

• 작업범위 결정 조건, 체크 조건
• 비교 조건의 종류와 효율성
  • 쿼리의 WHERE 조건이나 GROUP BY 또는 ORDER BY절이 어떤 경우 인덱스를 사용할 수 있는지, 어떤 방식으로 인덱스를 사용하는지 식별할 수 있어야한다.
  • 다중 칼럼 인덱스에서 각 칼럼의 순서와 그 칼럼에 사용된 조건이 동등비교(=)인지 아니면 크다(>) 또는 작다(<) 같은 범위 조건인지에 따라 각 인덱스 칼럼의 활용 형태가 달라진다.
    • SELECT * FROM dept_emp WHERE dept_no='d002' AND emp_no >= 10114; 이 쿼리를 위해 두 가지 케이스의 인덱스를 생성했다고 가정하자.
      1. 케이스 A INDEX (dept_no, emp_no)
         • dept_no='d002' AND emp_no >= 10114인 레코드를 찾고, 그 이후 dept_no='d002'가 아닐 때까지 인덱스를 그냥 쭉 읽기만 하면 된다.
      2. 케이스 B INDEX (emp_no, dept_no)
         • dept_no='d002' AND emp_no >= 10114인 레코드를 찾고, 그 이후 모든 레코드에 대해dept_no='d002'인지 비교하는 과정을 거쳐야 한다.
• B-Tree인덱스의 가용성
  • B-Tree 인덱스의 특징은 왼쪽 값에 기준해서 오른쪽 값이 정렬돼 있다는 것이다. 여기서 왼쪽이란 하나의 칼럼 내에서뿐만 아니라 다중 칼럼 인덱스의 칼럼에 대해서도 함께 적용된다.
  • 왼쪽 부분이 없으면 인덱스 레인지 스캔 방식의 검색이 불가능하다.
    1. 케이스 A: INDEX (first_name)
       • SELECT * FROM employees WHERE first_name LIKE '%mer';
       • 이 쿼리는 인덱스 레인지 스캔 방식으로 인덱스를 이용할 수 없다. 왜냐하면 first_name 칼럼에 저장된 값의 왼쪽부터 한 글자씩 비교해 가면서 일치하는 레코드를 찾아야 하는데, 
         조건절에 주어진 상숫값('%mer')에는 왼쪽 부분이 고정되지 않았기 때문이다.
    2. 케이스 B: INDEX (dept_no, emp_no)
       • SELECT * FROM dept_emp WHERE emp_no >= 10144;
       • 인덱스의 선행 칼럼인 dept_no 조건 없이 emp_no값으로만 검색하면 인덱스를 효율적으로 사용할 수 없다.
• 가용성과 효율성 판단
  • 앞서 확인했던 emp_no와 같이 작업 범위 결정 조건으로 사용할 수 없는 경우
    1. NOT-EQUAL로 비교된 경우 ("<>", "NOT IN", "NOT BETWEEN", "IS NOT NULL")
    2. LIKE '%??'(앞부분이 아닌 뒷부분 일치) 형태로 문자열 패턴이 비교된 경우
    3. 스토어드 함수나 다른 연산자로 인덱스 칼럼이 변형된 후 비교된 경우
       • WHERE SUBSTRING(column, 1, 1) = 'X'
       • WHERE DAYMONTH(column) = 1
    4. NOT-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용된 경우
       • WHERE column = deterministic_function()
    5. 데이터 타입이 서로 다른 비교(인덱스 칼럼의 타입 변환해야 비교가 가능한 경우)
       • WHERE char_column = 10
    6. 문자열 데이터 타입의 콜레이션이 다른 경우
       • WHERE utf8_bin_char_column = euckr_bin_char_column
    7. // 다음 쿼리는 인덱스를 사용할 수 없음
       • WHERE column_1 <> 2
    8. // 다음 쿼리는 column_1과 colum_2까지 범위 결정 조건으로 사용됨
       • WHERE column_1 = 1 AND column_2 > 10
    9. // 다음 쿼리는  column_1, column_2, column_3까지 범위 결정 조건으로 사용됨
       • WHERE column_1 IN (1, 2) AND column_2 = 2 AND column_3 <= 10
    10. // 다음 쿼리는 column_1, column_2, column_3까지 범위 결정 조건으로, // column_4는 체크 조건으로 사용됨
        •  WHERE column_1 = 1 AND column_2 =2 AND column_3 IN (10, 20, 30) AND column_4 <> 100
    11. // 다음 쿼리는 column_1, column_2, column_3, column_4까지 범위 결정 조건으로 사용됨 // 좌측 패턴 일치 LIKE 비교는 크다 또는 작다 비교와 동급으로 생각하면 됨
        • - WHERE column_1 = 1 AND column_2 IN (2, 4) AND column_3 = 30 AND column_4 LIKE '김승%'