8.3 B-Tree 인덱스

인덱싱 알고리즘 중 가장 일반적으로 사용되는 알고리즘. B는 Binary의 약자가 아닌, Balanced의 약자이다.

8.3.1 구조 및 특성

B-Tree의 구조

• 제일 상단에 있는 루트 노드, 중간에 있는 브랜치 노드, 가장 마지막에 있는 리프 노드가 있다.
  • 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있다.
• 인덱스들은 모두 정렬이 된 상태로 저장이 되어 있다.
• 실제 디스크의 저장된 데이터 파일의 레코드는 정렬되어있지 않다.
  • 엄밀히 말하면, InnoDB에서는 레코드가 클러스터되어 저장되기 때문에 기본적으로 PK 순서로 정렬되어 저장된다.

데이터 레코드 구조 (InnoDB)

리프 노드와 데이터 파일의 구조를 자세하게 살펴보자.

데이터 파일에는 결국 PK를 저장하고 있는 B-Tree가 있다. 그렇기 때문에 인덱스를 이용해 리프노드를 찾은 다음 PK가 저장된 B-Tree 탐색을 또 해야 한다.

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

8.3.2.1 인덱스 키 추가

1. B-Tree에 저장될 때는 저장될 키 값을 이용해 B-Tree상의 적절한 위치를 검색해야 한다.
2. 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장한다.
3. 만약, 리프 노드가 꽉 차 더는 저장할 수 없는 경우에는 리프 노드를 분리하는 작업을 해야 한다.
   1. 이 작업은 상위 노드에까지 영향을 미친다. 이 때문에 쓰기 작업에는 비용이 많이 든다.

InnoDB 스토리지 엔진은 키 추가 작업을 지연시켜 나중에 처리할 수 있다. 하지만 PK, 유니크 인덱스의 경우 중복 체크가 필요하기 때문에 즉시 처리 된다. (체인지 버퍼를 이용해 지연작업을 처리한다.)

8.3.2.2 인덱스 키 삭제

삭제할 키 값이 저장된 리프 노드를 찾아 삭제 마크만 하면 작업이 끝난다. 삭제 마킹된 인덱스 키 공간은 그대로 방치 되거나 재활용할 수 있다. 마킹 작업 또한 디스크 쓰기가 필요하다. InnoDB 스토리지 엔진에서는 이 작업이 버퍼링되어 지연 처리될 수도 있다.

8.3.2.3 인덱스 키 변경

인덱스 키 값에 따라 저장되는 리프 노드의 위치가 결정되므로 단순하게 변경할 수 없다. 그렇기 때문에 1. 먼저 키를 삭제한 뒤 → 2. 새롭게 추가를 한다

이 작업 역시 InnoDB 스토리지 엔진이 체인지 버퍼를 활용해 지연 처리될 수 있다.

8.3.2.4 인덱스 키 검색

인덱스는 조회를 빠르게 하기 위한 목적이다. 하지만 주의를 해야 할 점들이 있다.

• LIKE 조건일 경우 “A%” 경우는 가능하나, “%B”의 경우는 불가능 하다.
• 100% 일치 조건은 가능
• 부등호(<, >) 조건 가능
• 키 값이 변형되면 불가능
  • ex) where substr(name, 1) = ‘A’

인덱스 설계가 중요한 또 다른 이유는 InnoDB 스토리지 엔진에서의 레코드 잠금은 결국 인덱스 레코드를 먼저 잠근 후 테이블의 레코드를 잠그는 방식이기 때문에, 최대한 적은 레코드를 잠그도록 해야 한다.

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

1. 인덱스 키 값의 크기

디스크에 데이터를 저장하는 가장 기본 단위를 페이지라고 한다.

B-Tree는 자식 노드의 개수는 가변적이다. 페이지 크기와 키 값의 크기에 따라 결정되는데, MySQL의 페이지 크기 기본값이 16KB이고 자식 노드 주소 영역이 대략 12바이트라고 가정하면 하나의 인덱스 페이지(16KB)에 16*1024/(16+12) = 585개를 저장할 수 있다. 최종적으로 자식 노드를 585개 가질 수 있는 B-Tree가 되는 것이다.

만약 인덱스 키 값이 32바이트로 늘어났다면, 16*1024/(16+32) = 372개 저장할 수 있다.

이게 왜 중요하냐면, SELECT로 500개의 데이터를 조회해야 한다면, 인덱스 키 값이 16 바이트였다면 1개의 페이지만 읽으면 되는데, 32바이트였다면 최소 2개 이상 페이지를 읽어야 하는 것이다.

페이지를 읽는 다는 것은 결국 디스크 I/O가 발생하는 것이고 이는 속도가 느려진다는 의미이다.

2. B-Tree 길이

B-Tree 깊이가 3인 경우 가지는 키 값의 총 개수

• 인덱스 키 값이 16바이트일 때: 최대 2억 (585 * 585 * 585)
• 인덱스 키 값이 32바이트일 때: 5천만 (372 * 372 * 372)

인덱스 키 값이 커지면 트리 깊이가 깊어질 것이고 이는 성능과 직결된다.

결론적으로, 인덱스 키 값의 크기는 가능하면 작게 만드는 것이 좋다.

3. 선택도 (기수성)

모든 인덱스 키 값 가운데 유니크한 값의 수를 의미한다. 전체 인덱스 키 값은 100개인데, 그 중 유니크한 값의 수가 10개라면 기수성은 10이다. 선택도가 높을수록 검색 대상이 줄어들기 때문에 성능에 도움이 된다.

예시를 통해 알아보자

전체 레코드 수는 1만 건이고, country 컬럼으로만 인덱스가 생성되어있다.

테스트 1:

• 케이스 A: country 컬럼의 유니크한 값의 개수(기수성)가 10개
• 케이스 B: country 컬럼의 유니크한 값의 개수(기수성)가 1,000개

select * from test where country='korea' and city='seoul';

MySQL에서는 인덱스의 통계 정보(유니크한 값의 개수)가 관리되기 때문에 city 컬럼의 기수성은 작업 범위에 아무런 영향을 미치지 못한다. 위 쿼리는 케이스 A의 경우 평균 1,000건, B의 경우 평균 10건이 조회될 수 있다는 것을 예측할 수 있다.

만약 해당되는 결과 레코드가 1건만 존재한다면, 케이스 A는 1건의 데이터를 위해 쓸모없는 999건의 레코드를 더 읽었지만, 케이스 B는 9건만 더 읽은 것 이다.

4. 읽어야 하는 레코드의 건수

레코드가 100만 건이 있는데 50만 건을 읽어야 한다고 해보자. 인덱스를 이용한 읽기의 손익 분기점이 얼마인지 판단할 필요가 있는데, 일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드 1건을 읽는 것보다 45배 정도 비용이 든다고 예측한다. 즉 읽어야 하는 레코드가 전체 레코드의 2025%를 넘어서면 인덱스를 사용하지 않고 직접 테이블을 읽는다.

강제로 인덱스를 사용하도록 힌트를 추가해도 옵티마이저가 이를 무시하고 테이블을 직접 읽어 들이므로 주의해야 한다.

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

8.3.4.1 인덱스 레인지 스캔

인덱스의 접근 방법 가운데 가장 대표적인 접근 방식이다.

select * from test where first_name between 'Ebbe' and 'Gad';

인덱스 레인지 스캔은 인덱스의 범위가 결정됐을 때 사용하는 방식이다.

1. 루트 노드에서부터 비교해 브랜치 노드를 거치고 최종적으로 리프 노드까지 도달해야 필요한 레코드의 시작 지점을 알 수 있다. (인덱스 탐색)
2. 시작해야 할 위치를 찾았다면, 그때부터 리프 노드의 레코드만 순서대로 읽으면 된다. (인덱스 스캔(인덱스 탐색이 포함될 수 있음)
   1. 내림차순, 오름차순에 따라 정순 또는 역순으로 읽을 수 도 있다.
3. 만약 스캔하다가 리프 노드의 끝까지 읽으면 리프 노드 간 링크를 이용해 다음 리프 노드를 찾아 다시 스캔한다.
4. 최종적으로 멈춰야 할 위치에 도달하면 지금까지 스캔한 데이터를 반환한다.

만약 조회하는 컬럼이 인덱스를 이용해 굳이 데이터 파일을 조회하지 않아도 되는 경우를 커버링 인덱스이라고 한다.

8.3.4.2 인덱스 풀 스캔

인덱스를 처음부터 끝까지 모두 읽는 방식을 의미한다.

인덱스 구성 : (first_name, last_name)

select * from test where last_name like '%B';

쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우 인덱스 풀 스캔 방식이 사용된다. 예를 들어, 인덱스는 (A, B, C)의 순서로 만들어졌지만 쿼리의 조건절은 B 컬럼이나 C 컬럼으로 검색하는 경우이다.

• 쿼리가 인덱스에 명시된 컬럼만으로 조건을 처리할 수 있는 경우 주로 이 방식이 사용된다.
• 인덱스의 크기는 테이블의 크기보다 작으므로 테이블 풀 스캔보다는 효율적이다.

8.3.4.3 루스 인덱스 스캔

루스 인덱스 스캔은 인덱스 레인지 스캔과 비슷하게 작동하지만, 중간에 필요하지 않는 인덱스 키 값은 건너뛰면서 스캔한다. 일반적으로 GROUP BY 또는 집합 함수 가운데 MAX(), MIN() 함수에 대해 최적화를 하는 경우에 사용된다.

예를 들어, (dept_no, emp_no) 조합으로 인덱스가 구성되어 있다고 가정해보자.

• 이는 dept_no, emp_no 조합으로 정렬이 되어있다는 의미이다.

select dept_no, MIN(emp_no)
from dept_emp
where dept_no between 'd002' and 'd004'
group by dept_no;

위 쿼리는 depth_no 그룹 별로 제일 첫 번째 레코드만 읽으면 된다.

그렇기 때문에 다음과 같이 스캔하게 된다.

+---------------------+
| dept_no  |  emp_no  |
**|   d002   |  100000  | <- 스캔**
|   d002   |  103401  | -- 여기서 부터 d002라면 모두 스킵!
|   ....   |  ......  |
+---------------------+
...
+---------------------+
| dept_no  |  emp_no  |
**|   d004   |  200000  | <- 스캔**
|   d004   |  203401  | -- 여기서 부터 d004는 모두 스킵!
|   d004   |  203432  |
|   ....   |  ......  |
+---------------------+

8.3.4.4 인덱스 스킵 스캔

인덱스의 구성이 중요한 이유는 해당 키 값의 순서대로 정렬이 되어있기 때문이다.

아래 예시를 보자. 인덱스는 (col1, col2)로 구성되어 있다.

select * from test where col2='b'; // X
select * from test where col1='a' and col2='b'; // O

col2 단독으로 사용하는 쿼리는 인덱스를 사용하지 못할 뿐더러, 이런 경우에는 새로 생성을 해야 인덱스를 사용할 수 있었다.

하지만, 8.0 부터는 옵티마이저가 col1 컬럼을 건너뛰어 col2 컬럼만으로도 인덱스 검색이 가능하게 해주는 인덱스 스킵 스캔 최적화 기능이 도입됐다.

물론 이전 버전에서도 인덱스 스킵 스캔과 비슷한 루스 인덱스 스캔도 있었지만 루스 인덱스 스캔은 GROUP BY 작업을 처리하기 위해 인덱스를 사용하는 경우에만 적용할 수 있었다. 하지만 8.0 부터 도입된 인덱스 스킵 스캔은 WHERE 절까지 적용할 수 있도록 용도가 확장되었다.

인덱스 스킵 스캔은 단점이 있다.

• WHERE 조건절에 조건이 없는 인덱스의 선행 컬럼의 유니크한 값의 개수가 적어야 한다.
  • 만약 선행 컬럼이 사원번호 처럼 유니크한 값이라고 한다면 모든 사원 수 만큼 레인지 스캔 시작 지점을 검색하는 작업이 필요해 성능이 떨어진다.
• 쿼리가 인덱스에 존재하는 컬럼만으로 처리 가능해야 함(커버링 인덱스)
  • 모든 컬럼을 조회하도록 변경한다면, 이는 나머지 컬럼을 조회하기 위해 풀 테이블 스캔으로 실행계획을 수립한다.