[MySQL] B-Tree 인덱스

1. 디스크 읽기와 쿼리 성능

1) 디스크 읽기의 오버헤드

• 컴퓨터의 CPU나 메모리처럼 전기적 특성을 띤 장치의 성능은 매우 빠른 속도로 발전했지만 디스크 같은 기계식 장치의 성능은 상당히 제한적으로 발전했다. 비록 최근 SSD가 많이 활용되고 있지만 여전히 컴퓨터에서 가장 느린 부분이라는 점은 변함이 없다. 이 때문에 데이터베이스의 성능 튜닝은 어떻게 디스크 I/O를 줄이느냐가 관건이다.

2) 랜덤 I/O와 순차 I/O

• 기본적으로 순차I/O는 랜덤I/O보다 빠른데, 이는 SSD에서도 동일하게 적용되는 개념이다. 따라서 일반적으로 쿼리를 튜닝하는 것은 랜덤 I/O를 줄여주는 것이 목적이라고 할 수 있다.

  

2. 인덱스

1) 인덱스란?

• 보통 인덱스란 찾아보기(색인)으로 설명한다. DBMS 인덱스 역시 동일한 의미로 쓰인다. 칼럼 또는 칼럼들의 값과 해당 레코드가 저장된 주소를 키,값 쌍으로 저장하고 최대한 빠르게 찾아갈 수 있게 특정 순서로 정렬하여 보관한다.
• 이러한 방식은 데이터의 저장(INSERT, UPDATE, DELETE)의 성능을 희생하고 데이터 읽기 속도를 높이는 기능이다. 일반적인 서비스에서 데이터 저장:데이터 읽기 = 1:9 정도로 발생하므로 데이터 저장을 희생하여 읽기를 높이는 것은 효율면에서 큰 의미가 있다.

3. B-Tree 인덱스

• B-Tree는 데이터베이스 인덱싱 알고리즘 가운데 가장 일반적이고 성숙한 알고리즘이다. B-Tree는 칼럼의 원래값을 변형시키지 않고 인덱스 구조체 내에서는 항상 정렬된 상태로 유지한다.

1) 구조 및 특성

• B-Tree는 최상위에 루트노드가 존재하고 중간노드인 브랜치노드를 거쳐 가장 하위에 리프노드가 존재한다. 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프노드는 실제 데이터 레코드를 찾기위한 주솟값을 가지고 있다.
• 그림과 같이 인덱스의 키값은 모두 정렬되어 있지만 실제 데이터 파일의 레코드는 정렬되어 있지 않고 임의의 순서로 정렬되어 있다. 하지만 InnoDB 테이블은 예외적으로 리프노드에 레코드 주소가 아닌 primary key가 저장되어 있고 primary key를 이용해 한번 더 인덱스 검색을 수행한다. (정렬됨)
• 이러한 InnoDB의 인덱스 구조와 일반적인 인덱스 구조는 각각 장단점을 가지고 있다.

2) 인덱스 키 추가 및 삭제

• B-Tree에 새로운 키 값이 저장될 때 해당 값을 이용해 적절한 위치를 검색하여 추가하여야 한다. 특히 리프 노드가 꽉 차있을 경우 리프노드가 분리돼야 하는데, 이러한 특징으로 인해 B-Tree는 쓰기 작업의 비용이 크다.
• InnoDB 외의 스토리지 엔진에서는 이러한 인덱스 키 추가 작업이 즉시 일어나게 되지만 InnoDB의 경우 체인지 버퍼를 이용하여 인덱스 키 추가 작업을 지연시켜 나중에 처리가 가능하다. 하지만 프라이머리 키나 유니크 인덱스의 경우 중복 체크가 필요하여 즉시 추가 및 삭제한다.

3) 인덱스 키 검색

• 인덱스를 쓰는 가장 큰 이유는 빠른 검색을 위해서다. B-Tree 인덱스를 이용한 검색은 100% 일치 혹은 앞부분만 일치하는 경우에 사용할 수 있다.
  InnoDB 스토리지 엔진에서 인덱스는 더 특별한 의미가 있는데, InnoDB가 지원하는 레코드 잠금이나 넥스트 키락이 검색을 수행한 인덱스를 잠근 후 레코드를 잠그는 방식으로 구현되어 있다. 적절한 인덱스가 없다면 쓸데없이 많은 레코드를 잠그게 된다.

4. B-Tree 인덱스 사용에 영향을 주는 요소

1) 인덱스 키 값의 크기

• 인덱스 키 값의 크기가 커지면 하나의 인덱스 페이지(디스크에 데이터를 저장하는 가장 기본 단위)에 저장할 수 있는 키의 갯수는 줄게 된다. 이는, 특정 쿼리 갯수를 읽을 때 디스크에 접근하는 횟수를 늘리게 되며 느려진다.
• 또한 인덱스 키가 커지면 인덱스를 캐시하는 버퍼 풀의 공간을 줄이게 되어 캐시할 수 있는 레코드 수를 줄인다. 이는 메모리 효율을 떨어뜨리게 된다.

2) B-Tree 깊이

• B-Tree 인덱스 깊이는 상당히 중요하지만 따로 제어할 방법은 없다. 이는 인덱스 키 값의 크기에 의존적인데 키 값이 커질수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 갯수가 적어지고, B-Tree 깊이가 깊어져 디스크 읽기가 더 많아진다. (위와 같은 결과)

3) 선택도/기수성(Cardinality)

• 선택도가 높다는 뜻은, 중복이 적어서 더 잘 선택된다는 뜻이다. 인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.

4) 읽어야 하는 레코드 건수

• 인덱스를 통해 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 드는 작업이다. 전체 레코드 중에 50%를 인덱스를 통해 읽는다면 테이블을 모두 읽어서 필요없는 50%를 버리는 것이 좋은 선택일 것이다.
• 인덱스를 통해 레코드 1건을 읽는 것은 테이블에서 직접 읽는 것보다 4~5배 정도 비용이 많이 든다. (리프 노드에 저장된 레코드 주소로 데이터를 읽어오는데, 이때 랜덤 I/O 발생) 따라서 인덱스를 통해 읽어야할 레코드가 전체 테이블의 20%~25%를 넘어서면 테이블을 모두 읽는 것이 효율적이다.

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

1) 인덱스 레인지 스캔

- 인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다. 가능한 쿼리와 스캔의 단계는 다음과 같다.

ex) SELECT * FROM empolyees WHERE name BETWEEN 'ABC' AND 'BCD';
1. 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다. (Index seek)
2. 1번에서 탐색된 위치부터 필요한 만큼 인덱스를 차례로 쭉 읽는다. (Index scan)
3. 2번에서 읽은 인덱스 키와 레코드 주소를 이용하여 최종 레코드를 읽어온다.

2) 인덱스 풀 스캔 (인덱스를 효율적으로 사용X)

- 인덱스 레인지 스캔과 마찬가지로 인덱스를 사용하지만 인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라 한다. 대표적으로 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 번째 칼럼이 아닌 경우 인덱스 풀 스캔 방식이 사용된다. - 인덱스 풀 스캔 역시 인덱스를 이용하지만 효율적인 방식은 아니며, 인덱스를 생성하는 목적도 아니다.

3) 루스 인덱스 스캔

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

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

4) 인덱스 스킵 스캔

• 인덱스 (A, B)가 있을때 B의 범위로만 조건절을 구성하면 인덱스를 사용할 수 없었다. 하지만 MYSQL8.0 부터는 옵티마이저가 A칼럼을 건너 뛰어서 B 칼럼만으로도 인덱스 검색이 가능하게 해주는 인덱스 스킵 스캔 최적화 기능이 도입되었다.
• 선행 인덱스의 가능한 모든 값을 고려하여 여러 쿼리를 만들어 수행한다. (인덱스 사용하도록)