B-Tree Index (2)

들어가며

지난 글인 B-Tree Index(1) 에서는 네 부분에 대해 알아보았다.

 

(1) B-Tree의 구조

(2) B-Tree Index를 사용해 레코드를 읽는 방법

(3) B-Tree Index의 추가, 삭제, 변경

(4) B-Tree Index를 사용한 검색

 

이 글에서는 B-Tree Index 사용에 영향을 미치는 요소에 대해 알아보겠다.

 

B-Tree Index 사용에 영향을 미치는 요소

Page

InnoDB 엔진에서 데이터를 저장하는 기본 단위이다. Block이라고도 한다.

디스크 모든 I/O 작업의 최소 작업 단위다.

버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 하다.

Page의 기본값은 16KB이다.

 

Index도 페이지 단위로 관리되며 루트노드, 브랜치노드, 리프노드를 구분하는 기준 또한 페이지이다.

 

다시 한번 B-Tree

B-Tree의 B는 Binary가 아니라 Balanced의 약자라고 말한 바 있다.

이 말의 의미는 B-Tree 노드의 자식 노드가 두 개가 아니라는 의미인데,

그렇다면 이쯤에서 'B-Tree 노드들의 자식노드가 몇 개인지' 궁금할 것이다.

 

답부터 말하자면 B-Tree의 자식노드 개수는 가변적이다.

여기서 '가변적'이라 함은 B-Tree의 자식노드 개수는 페이지의 크기와 키 값의 크기에 따라 달라진다는 말이다.

그럼 이제 다음 요소들이 B-Tree Index 사용에 어떤 영향을 미치는지 알아보자.

 

키 값의 크기

키 값의 크기라 함은 Index로 사용될 컬럼의 값의 크기를 말한다.

이 값의 크기에 따라 B-Tree Index 사용에 어떤 영향을 받는지 문제로 설명해보겠다.

문제1

페이지의 크기가 16KB, 키 값의 크기가 16Byte일 때 B-Tree의 자식노드는 몇 개일까?

 

설명

자식 노드의 개수를 구하기 위해서는 페이지 크기를 노드의 개수로 나누면 될 것이다.

하지만 이 문제를 풀기 위해서는 B-Tree의 노드가 어떻게 구성되는지를 먼저 알아야 한다.

 

B-Tree의 노드는 키 값 이외에도 여러 가지 정보가 담긴 영역인 자식노드 주소로 구성된다.

여기에서는 편의 상 자식노드 주소 영역이 12Byte의 크기를 갖는다고 가정하겠다.

그렇다면 식은 16*1024/28이 되고, 이를 계산하면 약 585개의 자식 노드를 가질 수 있다는 것을 알 수 있다.

 

키 값의 크기가 B-Tree Index 사용에 미치는 영향에 대해 알아보기 위해서는 문제가 하나 더 필요하다.

 

문제2

페이지의 크기가 16KB, 키 값의 크기가 32Byte, 자식노드 주소 영역의 크기가 12Byte일 때

이 B-Tree가 가질 수 있는 자식 노드는 몇 개일까?

 

설명

16*1024/44를 계산하면 약 372개의 자식 노드를 가질 수 있음을 알 수 있다.

 

키 값의 크기와 B-Tree 자식노드의 개수

키 값의 크기가 커질수록 자식노드의 개수가 줄어든다는 것을 알 수 있었다.

이게 어떤 영향을 줄 수 있을까?

 

영향

500개의 레코드를 읽어야 하는 쿼리가 있다고 가정하자.

문제 1의 경우와 문제 2의 경우를 각각 놓고 봤을 때

문제 1의 경우에는 한 번의 디스크 읽기가, 문제 2의 경우에는 두 번의 디스크 읽기가 필요하다.

Disk I/O는 비용이 많이 발생하는 작업임을 알고 있을 것이다.

한 번의 디스크 읽기가 발생하는 작업과 두 번의 디스크 읽기가 발생하는 작업 중 어느 것이 더 빠를 것인지는 자명하다.

 

정리

루트노드, 브랜치노드, 리프노드를 구분하는 기준은 Page이다.

Page는 디스크 I/O 작업의 최소 단위이다.

 

키 값의 크기가 커지면, B-Tree의 자식노드 개수는 적어진다.

자식노드 개수가 적어진다는 말은 한 Page에 들어가는 노드의 개수가 적어진다는 의미이다.

한 Page에 들어가는 노드의 개수가 적어진다는 것은, 동일한 개수의 레코드를 읽어올 때 여러 Page를 조회해야 한다는 의미이다.

여러 Page를 조회해야 한다는 말의 의미는 디스크 I/O 작업이 여러 번 수행되어야 한다는 의미이다.

디스크 I/O 작업은 비용이 많이 드는 작업으로, I/O 작업이 많아질수록 성능은 느려질 수 밖에 없다.

 

정리하자면 아래와 같은 영향을 미치게 되는 것이다.

키 값의 크기가 큼 > 자식 노드 개수가 적어짐 > 한 페이지에 들어가는 노드의 개수가 적음 > 여러 페이지를 조회해야 함 > I/O 작업이 페이지 수만큼 발생 > 느려짐

 

또다른 영향

인덱스 키 값의 길이가 길어진다는 것은 전체적인 인덱스 크기가 커진다는 것을 의미한다.

InnoDB의 버퍼 풀이나 MyISAM의 키 캐시 영역의 크기는 제한되어 있는데,

인덱스 크기가 커질수록 메모리에 캐싱할 수 있는 레코드 수가 줄어들어 메모리 효율을 떨어뜨린다.

 

따라서 인덱스 키 값의 크기가 커지거나 길이가 길어질수록 Index 사용에 부정적 영향을 미치므로

키 값의 크기는 가능한 한 작게 하는 것이 좋다.

 

B-Tree의 깊이

B-Tree의 깊이를 직접 제어할 수는 없다.

B-Tree의 깊이는 인덱스 키 값의 크기가 커짐에 따라 나타나는 또다른 영향을 보여준다.

 

키 값의 크기가 클수록 한 페이지에 저장되는 인덱스의 개수가 줄어든다.

같은 개수의 레코드를 저장할 때, 키 값이 클수록 더 많은 페이지가 필요하게 된다.

한 페이지에 저장되는 인덱스의 개수(자식 노드의 개수)는 정해져있으므로 depth가 더 깊어지게 된다.

depth가 깊어진다는 것은 페이지의 개수가 늘어난다는 것과 같은 의미이므로, 여기서도 디스크 읽기가 더 많이 필요하게 된다.

 

인덱스 키 값의 크기가 커지거나 길이가 길어질수록 B-Tree의 depth가 깊어져 Index 사용에 부정적 영향을 미치게 된다.

 

선택도와 기수성, Selectivity and Cardinality

인덱스의 통계를 관리한다.

선택도와 기수성에 대해 알아보기 전에,

MySQL은 인덱스의 통계를 관리한다는 점을 알아야 한다.

인덱스의 통계에는 '인덱스의 Unique 값 개수'가 포함되므로, MySQL에서는 인덱스의 유니크 값 개수가 관리되는 것이다.

 

기수성

기수성은 전체 인덱스의 개수 중 유니크한 값의 개수를 의미한다.

예를 들어 전체 인덱스 100개 중 10개가 유니크한 값이라면 기수성은 10이 되는 것이다.

유니크한 값이 많으면 기수성은 높아지고, 중복 값이 많으면 기수성은 낮아진다.

기수성이 낮아지면 선택도 또한 떨어진다.

 

선택도

기수성이 높아 선택도가 높아지면, 검색 대상이 줄어들기 때문에 빠르게 처리된다.

 

예시

example 이라는 테이블이 있고, 이 테이블에는 country와 city 컬럼이 있다.

총 10,000개의 레코드가 있으며 같은 country와 city는 중복해서 들어가지 않았다.

Index는 country 컬럼으로만 생성된 상태일 때, 다음 쿼리에서 Index가 이용되는 방식을 두 가지 경우로 나누어 설명해보겠다.

SELECT *
FROM test
WHERE country = 'korea' AND city = 'seoul'

 

경우1. country 컬럼의 유니크 값 개수가 10개인 경우

중복된 레코드가 없다고 했으므로 country가 10개, 각 country마다 1000개의 city를 갖고 있다는 의미이다.

country가 korea이고 city가 seoul인 레코드를 찾기 위해 Index를 이용할 수 있다.

(1) country = 'korea'인 레코드를 찾으면, 1000개의 레코드가 나온다.

(2) 1000개의 레코드 중 city = 'seoul'인 레코드를 찾는다.

 

이 경우, 하나의 레코드를 찾기 위해 읽은 1000개의 레코드 중 999개의 레코드가 불필요한 레코드였다.

 

경우2. country 컬럼의 유니크 값 개수가 1000개인 경우

중복된 레코드가 없다고 했으므로 country가 1000개, 각 country마다 10개의 city를 갖고 있다는 의미이다.

country가 korea이고 city가 seoul인 레코드를 찾기 위해 Index를 이용할 수 있다.

(1) country = 'korea'인 레코드를 찾으면, 10개의 레코드가 나온다.

(2) 10개의 레코드 중 city = 'seoul'인 레코드를 찾는다.

 

이 경우, 하나의 레코드를 찾기 위해 읽은 10개의 레코드 중 단 9개의 레코드만이 불필요한 레코드였다.

 

정리

Unique 값의 개수, 즉 기수성과 선택도는 Index의 사용과 쿼리 효율성에 큰 영향을 미친다는 것을 알 수 있다.

 

읽어야 하는 레코드 건수

인덱스는 마냥 좋은 것일까?

https://heather-dev.tistory.com/22 이 글에서 Index는 저장 성능을 희생하여 검색 성능을 높이는 방법이라고 말한 바 있다.

더하여, 일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블을 직접 스캔하여 레코드를 읽는 것보다 4~5배 더 비용이 많이 드는 작업인 것으로 에측한다고 한다.

 

따라서 테이블을 직접 스캔하여 레코드를 읽으면서 원하는 레코드를 찾을 것인지,인덱스를 사용하여 필요한 부분만 읽을 것인지 결정해야 한다.보통 인덱스를 통해 읽어야 할 레코드가 전체 레코드의 20~25%를 넘으면 풀 테이블 스캔이 더 효율적이다.인덱스를 통해 레코드 1건을 읽는 것이 테이블을 직접 스캔하여 레코드를 읽는 것보다 4~5배 더 비용이 많이 들기 때문이다.

이런 경우 옵티마이저는 테이블을 직접 읽는 방식으로 작업을 수행하도록 되어 있지만, 알아두자.

 

마치며

이번 글에서는 Index 사용에 영향을 미치는 요소들에 대해 알아보았다.

하나씩 이해해보니 어떻게 Index를 생성하면 좋을지, 어떤 컬럼을 Index로 구성하면 좋을지에 대해 조금씩 알게 되는 것 같다.

다음 글에서는 인덱스를 통해 데이터를 읽는 방법, 즉 인덱스 스캔 방법에 대해 다룰 예정이다.