B-Tree 인덱스 정리 (8.1 ~ 8.3.5)

인덱스를 걸면 조회가 왜 빠른지에 대한 의문을 해소하고자 Real MySQL을 학습하게 되었습니다.

 

인덱스를 알기 전, 어떻게 디스크에서 데이터를 읽는지를 알아보겠습니다.

8.1 디스크 읽기 방식

# 기계식 장치인 HDD(하드 디스크)

기존 데이터는 기계식 장치인 원판 모양의 HDD(하드 디스크)에 저장하였습니다.

HDD는 원판을 돌려가며 데이터를 읽어야 하기 때문에 랜덤I/O 작업은 매우 비효율적이었습니다.

 

# 전자식 장치의 등장

HDD의 단점을 보완하고자 SSD, CPU, 메모리 같이 전기적 특성을 띈 전자식 장치가 등장하게 되었습니다.

SSD는 데이터를 읽기 위해 HDD를 회전시킬 필요가 없기 때문에 데이터를 읽고 쓰는 작업이 매우 빠릅니다.

 

그리고, DBMS가 이 SSD를 채택하여 데이터를 저장하게 되었습니다.

그러나 이 SSD 도 순차I/O 와 랜덤I/O 간의 성능 차이가 존재합니다.

 

그렇기에 랜덤I/O 자체를 줄여주면 성능이 좋아지는데, 이 작업을 인덱스로 해결할 수 있는 것입니다.

 

8.2 인덱스

# 인덱스 구조

인덱스는 key-value 구조로 보통 key 에는 column 의 값, value 에는 데이터가 저장됩니다.

 

# 인덱스 특징

DBMS는 인덱스를 column 의 값을 이용해 항상 정렬된 상태를 유지합니다.

항상 정렬을 유지해야 하기 때문에 인덱스를 만들어서 저장하는 과정을 느릴 수 밖에 없습니다.

하지만, 항상 정렬이 되어있기 때문에 매우 빠른 속도로 데이터를 찾아올 수 있습니다,

 

이를 통해 다음과 같은 생각을 하게 되었습니다.

인덱스가 많은 테이블에서 INSERT, UPDATE, DELETE 문장의 처리는 느려지지만, SELECT 는 매우 빠릅니다.

CQRS 패턴(데이터를 변경하는 작업과 데이터를 읽는 작업을 분리)을 들어본 적이 있습니다.
인덱스가 많은 테이블에서 인덱스 쓰기 작업과 조회 작업이 빈번하게 발생할 때, 쓰기 작업과 조회 작업의 성능을 둘 다 높이기 위해 고려할 수 있을 것 같습니다. 다만, 이는 데이터 동기화문제를 충분히 고려해야 하지 않을까 생각하며 추후에 공부해보겠습니다.  

 

즉, 인덱스는 데이터의 저장(쓰기)성능을 희생하고 데이터의 읽기 속도를 높이는 기능입니다.

테이블의 인덱스를 하나 더 추가할지 말지는 데이터의 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만들어아 할지를 결정해야 합니다.

* SELECT 의 WHERE 절에 사용되는 column 이라고 전부 인덱스를 생성하면 쓰기 작업 성능이 떨어집니다.

 

# 인덱스 알고리즘 B-Tree 와 Hash

• B-Tree 인덱스는 column 에 저장된 실제 데이터를 그대로 사용해서 인덱스를 생성합니다.
• Hash 인덱스는 column 의 값으로 해시값을 계산해서 인덱스를 생성합니다.
  • 해시맵의 조회가 O(1) 인 것처럼, Hash 인덱스일 경우 조회속도가 매우 빠릅니다.
  • 하지만, column 의 값을 변형하기 때문에 column 의 값으로 범위 검색을 하거나 일부만을 검색할 때는 인덱스를 사용할 수 없습니다.
  • 그렇기 때문에 이러한 Hash인덱스는 메모리DB인 Redis 나 스프링부트의 내장된 메모리DB인 h2 에서 사용됩니다.

 

8.3 B-Tree 인덱스

8.3.1 B-Tree 구조

B-Tree 의 B는 Binary(이진) 트리가 아니라 Balanced 를 의미합니다.

트리 구조의 최상위에 하나의 루트(Root) 노드가 존재하고, 트리구조의 가장 하위에 있는 노드를 리프(Leaf) 노드라 하고, 트리구조에서 루트도 리프도 아닌 중간 노드를 브랜치(Branch) 노드라 합니다.

 

인덱스(B-Tree)의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있습니다.

* 인덱스 및 데이터 레코드는 파일 형태로 SSD에 저장됩니다.

 

인덱스의 키는 정렬되어 있지만, 아래 그림 처럼 대부분의 RDBMS에서 데이터 레코드는 정렬돼 있지 않고 무작위 순서로 저장됩니다.

데이터 레코드가 무작위 순서로 저장되기 때문에 Random I/O 가 발생하고, 이러한 RandomI/O 줄이기 위해 정렬되어 있는 인덱스로 조회를 하여 순차 I/O 로 바꾸는 것이라 생각합니다.

클러스터링 인덱스의 B-Tree 구조

 

하지만, MySQL 8.0 의 클러스터링 인덱스는 다릅니다.

MySQL 엔진 중에서도 InnoDB 엔진은 아래 그림처럼 테이블의 레코드를 PK 순서로 정렬시켜 디스크에 저장합니다.

그리고, 세컨더리 인덱스를 생성하여 해당 인덱스로 데이터 레코드를 찾을 때, 아래 그림의 노란색 선을 따라 B-Tree 를 2번 탐색합니다. 세컨더리 B-Tree 인덱스의 key 는 column 의 실제 값, value 에 PK값이 들어갑니다.

이것이 MySQL 8.0 과 다른 RDBMS 와 다른 특징들 중 하나입니다.

MySQL InnoDB엔진의 인덱스 탐색 구조

 

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

인덱스는 쓰기 작업의 성능을 포기하고 읽기 작업의 성능을 얻고자 하는 것이라고 다시 한 번 상기하며 인덱스의 키가 추가될 때를 알아보겠습니다.

 

# 추가

레코드가 추가되어 세컨더리 인덱스 B-Tree 에 노드(인덱스)를 추가하는 상황입니다.

1. 이 노드를 B-Tree 어디에 저장할지 탐색

2. 적절한 위치를 찾아서 리프노드에 저장할 때, 리프노드가 꽉차 있다면 리프노드를 분리하는 작업이 발생합니다.

 

이러한 과정이 있기에 B-Tree 인덱스의 추가는 비용이 많이 듭니다.

다만, InnoDB 스토리지 엔진(MySQL 8.0 의 기본 스토리지 엔진)은 이 작업을 지연시켜 나중에 처리할 수 있지만, PK 나 유니크 인덱스의 경우 중복 체크가 필요하기 때문에 즉시 B-Tree 에 추가하거나 삭제합니다.

Memory 스토리지 엔진, MyISAM 스토리지 엔진을 사용하는 테이블에서는 즉시 B-Tree 인덱스에 반영합니다.

 

# 삭제

인덱스 키 삭제는 단순히 해당 키를 찾아서 삭제합니다.

 

# 변경

다만, 키 변경은 단순히 값을 덮어씌우는 것이 아니라, 먼저 인덱스를 찾아서 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리됩니다.

 

이러한 작업을 거치기 때문에 인덱스는 쓰기 작업의 성능을 포기하고, 정렬된 상태의 인덱스로 조회 성능을 높이게 됩니다.

 

# 검색

• 인덱스를 사용하는 검색은 SELECT 구문뿐 아니라 UPDATE 와 DELETE 쿼리를 처리하는데도 사용
  • 해당 쿼리문에도 WHERE 가 있습니다
• 인덱스를 구성하는 column 의 키 값의 뒷부분만 검색하는 용도로 인덱스를 사용할 수 없습니다.
  • ex) SQL쿼리에서 WHERE 절에 'Like %특별시' 같이 와일드 카드 사용
• column 의 값을 변형해서 쿼리를 실행할 경우 인덱스를 사용하지 못합니다.
  • B-Tree 인덱스는 실제 column 의 값으로 인덱스를 만들기 때문
• InnoDB 스토리지 엔진은 검색을 수행한 인덱스를 잠근후 테이블의 레코드를 잠급니다.
  • 그래서, UPDATE 나 DELETE 문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠급니다.

 

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

# 인덱스 키 값의 크기

InnoDB 스토리지 엔진의 페이지 크기의 기본값은 16KB 입니다.

인덱스도 저장되어야 하기 때문에 인덱스의 키 값이 늘어난다면 자연스레 하나의 페이지(16KB)에서 읽을 수 있는 인덱스 개수가 적어지며 이는 디스크 I/O 횟수를 증가시킵니다.

 

그러니, 인덱스를 만들 column 의 타입을 varchar 나 blob 같은 걸 하지 말아야 합니다.

 

# 선택도(기수성)

인덱스에서 중복되지 않는 키의 개수를 의미합니다.

중복되지 않는 키의 개수가 많을 수록 인덱스 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리됩니다.

 

# 읽어야 하는 레코드의 건수

테이블의 레코드를 읽어야 하는데, 인덱스를 통해 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 더 비싼 비용인 작업입니다.

그래서, 인덱스를 통해 읽어야 할 레코드의 건수(옵티마이저가 예상한 건수)가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스가 있더라도 인덱스를 이용하지 않고, 테이블을 모두 직접 읽어서 필요한 레코드만 가려내는 필터링 방식으로 처리합니다.

 

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

# 인덱스 레인지 스캔

검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식

시작해야 할 리프 노드 위치를 찾으면 그때부터 리프 노드의 레코드만 순서대로 읽는다.

 

인덱스 레인지 스캔은 순차I/O? 랜덤I/O?

• 클러스터링 인덱스에 기반한 인덱스 레인지 스캔은 순차 I/O 라 생각합니다
  • PK 를 기준으로 레코드가 정렬되어있기 때문에 레인지 스캔이 순차 I/O 라 생각합니다.
• 세컨더리 인덱스에 기반한 인덱스 레인지 스캔은 랜덤 I/O 라 생각합니다.
  • 세컨더리 인덱스의 리프 노드부터 순차적으로 읽어도 레코드를 찾기 위해서는 PK 기반의 클러스터링 인덱스를 한 번 더 탐색해야하고, 이는 레코드에 랜덤 접근이 일어나기 때문입니다.

 

# 인덱스 풀 스캔

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

 

쿼리가 커버링 인덱스로 처리될 수 있을 때, 주로 이 방식으로 사용된다.

* 커버링 인덱스 : 쿼리로 찾고자 하는 레코드가 인덱스 탐색 만으로 찾을 수 있는 인덱스

 

# 루스 인덱스 스캔

듬성듬성하게 인덱스를 읽는 것을 의미한다.

인덱스 레인지 스캔과 비슷하게 작동하지만 중간에 필요치 않은 인덱스 키 값은 무시하고 다음으로 넘어가서 처리된다.

일반적으로 GROUP BY 또는 집합 함수의 MAX(), MIN() 에 대해 최적화 하는 경우에 사용된다.

 

ex) (dept_no, emp_no) 조합으로 인덱스 생성 시, dept_no 의 d002 컬럼들 중에서 첫 번째만 읽으면 되기 때문에 루스 인덱스 스캔을 사용하게 된다.

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

 

 # 인덱스 스킵 스캔

MySQL 8.0 부터 도입

다음 2가지 조건을 만족할 때, (gender, birth_date) 의 인덱스를 생성하고 아래 쿼리를 실행해도 인덱스를 탈 수 있다.

• 조건 2가지
  • WHERE 조건 절에 조건이 없는 인덱스의 선행 칼럼의 유니크한 값의 개수가 적어야 한다.(예시에서 gender 의 값은 Female 과 Male 둘 중 1개이다)
  • 쿼리가 커버링 인덱스로 처리 가능해야 한다.

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