8.3 B-Tree 인덱스 (1)

2024년 3월 23일 작성

Real MySQLB-Tree인덱스 사용 기준

B-Tree 인덱스?

Balanced Tree 를 의미한다. B-Tree는 데이터베이스 인덱싱 알고리즘 가운데 가장 일반적으로 사용됨.

B-Tree에는 여러 변형 알고리즘이 있는데, 일반적으로 DBMS에서는 주로 B+트리 또는 B*Tree 가 사용된다. b트리는 앞서 말했듯 컬럼의 값을 변형하지 않고 항상 정렬된 상태로 유지한다.

전문검색이 아닌 경우 대부분 b트리로 커버할 수 있다.

8.3.1 구조 및 특성

b-tree 인덱스의 기본적인 구조를 알아보자! 😘

b-tree는 트리구조의 그림이다.

240324-001113

인덱스의 키값은 모두 정렬돼있지만, 데이터 파일의 레코드는 정렬돼있지 않은 것을 알 수 있다. (화살표 방향이 중구난방)

B-tree 인덱스 노드는 다음과 같이 생겼당. (InnoDB 기준, MyISAM은 다름)

240324-002153

b트리 리프노드에는 데이터파일에 접근할 수 있는 프라이머리키가 있다. 따라서 해당 PK정보로 Primary Key 인덱스를 타고 또 다시 리프노드로 도달하면, 그 때 레코드 정보에 도달할 수 있게 된다.

240324-002206

그리고 그림에서는 세컨더리 인덱스(이름) 을 통해 레코드에 접근하려고 하고 있는데, InnoDB에서는 세컨더리 인덱스를 사용하더라도 PK를 주소처럼 사용하기 때문에 PK인덱스를 한번 더 검색해서 레코드를 읽게 된다.

즉, InnoDB 스토리지엔진에서는 모든 세컨더리 인덱스 검색에서 레코드에 접근하기 위해 반드시 PK B-tree를 다시 한번 검색해야하는 것이다.

secondary index를 쓸때 pk index b-tree를 한번더 검색하는 것이 성능이 떨어질 것 같지만, 장점도 있다. 자세한 내용은 8.8절 클러스터링 인덱스에서 다룬다.

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

이걸 잘 알아두면 쿼리의 성능을 쉽게 예측할 수 있다.

+) 인덱스를 사용시 주의사항도 함께 알아보자.

8.3.2.1 인덱스 키 추가

우리가 보통 b-tree의 쓰기 작업에 비용이 많이 든다고 하는데, 그 이유는 다음과 같다.

앞서 봤듯, b-tree에 값이 저장될 때는 저장된 키값이 어디에 들어가야할지 적절한 위치를 검색한다. 그 후 위치가 결정되면 b-tree 리프노드에 키값과 레코드 정보를 저장해야하는데 만약 리프노드가 꽉차서 더 저장할 수 없으면 리프노드가 분리돼야하고, 이 때 상위 브랜치 노드까지 처리의 범위가 넓어지기 때문이다.

MyISAM, MEMORY 스토리지 엔진과 달리 InnoDB에서는 새로운 키 값을 b-tree에 즉시 추가하지 않고 지연시켜 나중에 처리 할수 있다. (필요시) 하지만 PK나 유니크 인덱스의 경우 중복 체크가 필요하기 때문에 즉시 반영해야한다. 자세한 내용은 4.2.10절 체인지 버퍼에서~

인덱스 추가로 인한 성능 예측

정확히 얼마나 영향을 받는지는 알 수 없음. 그걸 알려면

컬럼 수
컬럼 크기
인덱스 컬럼

등을 모두 확인해야한다.

대신, 대략적으로 지연시간을 예측하는 방법은 다음과 같다.

레코드 추가 작업 비용이 1이라고 하고, 인덱스에 키를 추가하는 작업 비용을 1.5로 계산하는 것이다.

테이블에 B-tree 인덱스가 3개 있다면 인덱스가 하나도 없는 경우, 레코드만 쓰는 작업 비용이므로 1이라 예측, 인덱스가 3개인 경우에는 (1.5*3 + 1) 정도로 예측하는 것이다.

참고로 단위는 지연시간으로, 대부분 디스크로부터 인덱스 페이지를 I/O하는 시간이다. (메모리/cpu 처리 시간은 적음)

8.3.2.2 인덱스 키 삭제

B-Tree의 키 값이 삭제되는 경우는 간단하다.

B-Tree의 리프노드를 찾아서 삭제 마크 만 하면 작업이 완료된다. 삭제 마킹된 공간은 방치되거나 추후 재활용할 수 있다.

삭제 마킹 작업또한 b-tree 노드에 쓰기 작업을 해야하므로 디스크 io가 필요하다. 따라서, InnoDB를 쓴다면 삭제 마킹 작업도 버퍼링돼 지연될 수 있다. 하지만 특별한 사이드이펙트는 없으므로 걱정 X

8.3.2.3 인덱스 키 변경

240324-010126

인덱스 키를 변경하는 것은 리프노드에서 값만 다시 고칠 수 없다. 따라서 다음과 같이 삭제 후 추가를 해야한다.

240324-010705

8.3.2.4 인덱스 키 검색

인덱스는 select 뿐 아니라, update나 delete를 처리하기 위해서도 사용된다.

b-tree 인덱스 검색 특징

b-tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우에 사용할 수 있다.

부등호 비교 조건에서도 인덱스 사용 가능
하지만 키 값의 뒷부분만 검색하는 용도로는 인덱스 트리를 통한 검색 ❌

함수나 연산으로 변형된 값

인덱스 키 값에 변형이 가해진 후에는 B-tree 탐색이 불가. (당연한가?)

이 말은, 함수나 연산을 수행한 결과로 정렬하거나 검색하는 작업은 b-tree의 장점을 이용할 수 없다는 것이다. 이걸 알고 주의하고 쓸 수 있어야한다.

innodb 엔진에서의 인덱스 검색

InnoDB 테이블에서는 레코드 잠금 + 넥스트키락이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼있다.

따라서 udpate나 delete 문장이 실행될 때, 테이블에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠근다. 심지어 테이블의 모든 레코드를 잠가버릴 수도 있기 때문에 InnoDB 스토리지 엔진을 쓸 때는 인덱스 설계가 매우 중요하게 생각해야한다.

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

B-Tree 검색/변경 성능은 다음 요소에 영향받는다.

인덱스 구성 컬럼 크기
레코드 건수
유니크한 인덱스 키값의 개수 등

8.3.3.1 인덱스 키 값의 크기

InnoDB 스토리지 엔진의 데이터 저장 기본 단위: Page

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지(Page) 또는 블록(Block)이라고 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다. 또한 페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 하다. 인덱스도 결국은 페이지 단위로 관리되며, 앞의 그림 8.4에서 루트와 브랜치, 그리고 리프 노드를 구분한 기준이 바로 페이지 단위다.

B-Tree는 자식 노드를 몇개까지 가질까?

B-Tree가 이진트리였다면 자식노드가 2개만 있을것이다. 만약 그렇다고 하면 페이지에는 두개의 정보만 있었겠지?

240324-015210

이런 식이면 검색이 상당히 비효율적일 것이다. 그래서 B-Tree의 "B"가 이진(Binary) 트리의 약자는 아니라고 강조했던 것이다.

일반적으로 DBMS의 B-Tree는 자식 노드의 개수가 가변적인 구조다.

B-Tree의 노드 갯수는 바로, 인덱스의 페이지 크기와 키 값의 크기에 따라 결정된다.

MySQL 5.7부터 InnoDB 스토리지 엔진의 페이지 크기를 innodb_page_size 시스템 변수를 이용해서 지정할 수있고, 기본값은 16KB이다.

인덱스의 키가 16byte 라고 가정하면 다음 그림과 같이 인덱스 페이지가 구성된다.

240324-015620

위 그림에서는 인덱스가 16바이트이고 자식노드주소가 12바이트로 되어있다. 이 경우에는 몇 개의 키를 가질 수 있을까?

페이지의 기본크기인 16KB를 하나의 키+주소 쌍의 크기로 나누면 되겠다.

16 * 1024 / (16 + 12) = 약 585.

그러므로 585개를 저장할 수 있다.

여기서 인덱스 키 값이 커지면, 최대 자식노드의 수는줄어들게 될 것이다. 만약 키 값의 크기가 32바이트로 늘어났다고 하면

16 * 1024 / (32 + 12) = 약 372. 개를 저장할 수 있다.

전자는 인덱스 페이지 한번으로 해결될 수 있지만,

240324-025110

후자는 최소한 2번 이상 디스크로부터 읽어야 한다.

240324-025417

인덱스가 커지는 것

인덱스가 커지면 페이지의 자식노드 개수에 영향을 준다고 했다.

또한 인덱스 키 값의 길이가 커지면, 전체적인 인덱스의 크기가 커진다는 것을 의미한다.

하지만, 인덱스를 캐시해두는 InnoDB 버퍼풀은 크기가 제한적이기 때문에 하나의 레코드를 위한 인덱스 크기가 커지면 커질 수록 버퍼풀(메모리)에 캐시해 둘 수 있는 레코드 수가 줄어든다.

자연스럽게, 메모리의 효율이 떨어지는 결과를 초래한다.

8.3.3.2 B-Tree 깊이

Depth는 상당히 중요하지만 직접 제어할 방법은 없다.

저자가 데이터베이스 인덱스 키 값의 크기가 작을 수록 좋다는 것을 강조하기 위해 아래 예시를 든 것이고 실제로는 아무리 대용량 데이터베이스여도 뎁스가 5단계 이상 깊어지는 경우는 거의 없다고 한다. 알아서 잘 필터링해서 생각해야한다.

앞서 얘기한, 인덱스 길이가 늘어나는 상황에서 덧붙여보면

B-Tree 깊이가 3인 경우 최대 몇개의 키값을 가질 수 있는지 살펴보자.

키 값이 16바이트 인경우 한 페이지가 자식노드를 585개 가질 수 있었으므로 깊이가 3이면 585 * 585 * 585 = 약 2억 개의 키 값을 담을 수 있다.

하지만 키값이 두배가 되면 372 * 372 * 372 = 약 5천만 개 로 줄어든다.

따라서, 같은 수의 데이터를 읽을 때, 인덱스의 길이가 길 경우 데이터를 읽기까지 depth가 더 깊을 것이다. 그러므로 데이터 읽기가 더 많이 필요해지는 것이다.

8.3.3.3 Cardinality

Cardinality는 Selectivity와 거의 같은 의미로 사용되며, 모든 인덱스 키값 중 유니크한 값의 수를 의미한다.

전체 인덱스 키 값이 100개인데 그 중 유니크한 값을 세었을 때 10개가 나오면 cardinality는 10이다.

인덱스는 cardinality가 높을 수록 검색 대상이 줄어 빠르게 처리될 수 있다.

하지만 cardinality가 낮다고 해서 인덱스를 걸지 않는 것은 아니다. order by, group by 같은 작업을 위해 인덱스를 만드는 것이 훨씬 나은 경우도 있기 때문이다.

Cardinality 를 통해 인덱스를 적절히 설정했는지 판단하는 방법

첫번째 예시

country 라는 컬럼과 city 라는 컬럼이 포함된 tb_test 테이블을 예로 들자.

그리고 tb_test 테이블에 저장된 전체 레코드 건수를 1만 건✨ 이라고 하자.

country 의 cardinality가 10일 때
```
mysq1> SELECT *
    FROM tb_test
    WHERE country='KOREA' AND city='SEOUL';
```
이 쿼리를 날리면, 평균 1만 / 10 = 1,000 건을 스캔하게 될 것이다.
country 의 cardinality가 1,000일 때
```
mysq1> SELECT *
    FROM tb_test
    WHERE country='KOREA' AND city='SEOUL';
```
이 쿼리를 날리면, 평균 1만 / 1,000 = 10 건을 스캔하게 될 것이다.

만약 실제 모든 조건을 만족하는 레코드는 단 1건만 있었다면??

그렇다면 첫번째의 경우 인덱스를 적절히 설정하지 못한 것일 수 있다. (하지만 예시일 뿐, 현실에서는 이정도 낭비는 무시 가능)

두번째 예시

tb_city 라는 테이블에는 1만 건의 레코드가 있는데,

이번엔 country 컬럼에만 인덱스가 있다.

tb_city 테이블에는 국가와 도시가 중복해서 저장돼있지 않다고 가정한다.

mysql> CREATE TABLE tb_city country VARCHAR(10),
    city VARCHAR(10),
    INDEX ix_country (country)

그리고 두 가지 상황에서 다음 쿼리를 날릴 것이다.

mysql> SELECT *
    FROM tb_test
    WHERE country='KOREA' AND city='SEOUL';

country 컬럼의 Cardinality가 10일 때: 위의 where 조건으로 인덱스를 검색하면 평균 1만/10 = 1,000건이 일치할 것이다. 그런데 이 테이블은 국가+도시 조합이 유니크하므로 레코드는 1건만 조회될 것이다. 따라서 999개의 인덱스를 불필요하게 읽은 것으로 볼 수 있다.
country 컬럼의 Cardinality가 1,000일 때 마찬가지로 계산을 했을 때, 이때는 9건만 불필요하게 읽게 된다. 계산은 위와 같은 방식으로 직접 해보길 추천!

똑같은 쿼리를 실행해서 똑같은 결과를 받았지만 인덱스 Cardintality에 따라 MySQL 서버가 수행한 일의 양이 크게 달라지는 것을 알 수 있다.

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

인덱스는 기본적인 매커니즘에 의하면, 인덱스를 사용하는 것은 바로 레코드를 읽는 것보다 높은 비용이 드는 작업이다.

만약, 테이블에 레코드가 100만 건이 저장돼있는데, 그 중 50만건을 읽어야하는 쿼리가 있다면

옵티마이저는, 이 작업을

전체 테이블을 그냥 다 가져와서 필요없는 50만건을 버리는 것이 효율적인지
아니면 인덱스를 쓰느게 더 효율적일지

판단해야한다.

어느 지점부터는 인덱스를 사용해도, 비용이 더 줄어드는 때가 있는데, 이를 손익분기점이라고 할 수 있을 것 같다. 따라서 우리는 인덱스 사용을 결정하기 위해 읽기의 손익분기점을 판단할 수 있어야한다.

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

즉, 인덱스를 통해 읽어야 할 레코드의 건수 (물론 옵티마이저가 판단한 예상 건수)가 전체 테이블 레코드의 25%를 넘어서면 인덱스를 이용하지 않고 테이블을 모두 직접 읽어서 필요한 레코드만 가려내는(필터링) 방식으로 처리하는 것이 효율적이다.

전체 100만 건의 레코드 가운데 50만 건을 읽어야 하는 작업은 인덱스의 손익분기점인 25%보다 훨씬 크기 때문에 MySQL 옵티마이저는 인덱스를 이용하지 않고 직접 테이블을 처음부터 끝까지 읽어서 처리할 것이다. 이렇게 많은 레코드 (전체 레코드의 20~25% 이상)를 읽을 때는 강제로 인덱스를 사용하도록 힌트를 추가해도 성능상 얻을 수 있는 이점이 없다.

물론 이러한 작업은 MySQL의 옵티마이저가 기본적으로 힌트를 무시하고 테이블을 직접 읽는 방식으로 처리하겠지만 기본으로 알고 있어야 할 사항이다.

8.3.4 는 다음 글에서..