B+-Tree의 구조 이해를 통한 효율적인 Index 사용 법 정리.

안녕하세요, 이번 글에서는 MySQL index가 사용하는 B+-Tree 자료구조의 동작방식을 살펴보고 그를 통해 index를 조금 더 이해하는 글을 적어보려 합니다.

 

SQL 튜닝이란, 인덱스를 통해 접근할 페이지의 개수를 줄여 성능을 높이는 과정이라 생각합니다. 그러니 인덱스를 잘 이해하고 있다면 인덱스를 잘 활용할 수 있는 SQL을 작성할 수 있을 것이고, 훨씬 더 성능 좋은 애플리케이션을 만들 수 있을 것입니다.

 

1. B+-Tree

B+-Tree 는 아래의 조건을 만족시키는 Rooted Tree 구조를 말합니다.

• 루트로부터 모든 leaf 노드로의 길이는 동일하다 (Balanced Tree)
• 루트, 리프 노드가 아닌 모든 노드는 n/2 ~ n개의 자식 노드를 가질 수 있다.
• 모든 리프 노드는 (n-1)/2 ~ (n-1)개의 값을 갖는다.
• 단 루트가 리프가 아닐경우 최소 2개의 자식을 가져야 하고, 만약 루트가 리프일 경우 0~n-1개의 값을 가질 수 있다.

 

n=6인 B+-Tree를 예시로 살펴보면,

루트로부터 모든 리프로의 길이(depth)는 1로 동일하고, 모든 리프노드는 3~5개의 값을 가져야 합니다.

 

1-1. Node의 구조

각각의 노드를 살펴보면 아래와 같은 구조로 되어있습니다.

 

 

각각 데이터 하나당 Pointer와 Key로 이루어져 있습니다. 여기서 Pointer는 다음 노드의 위치를 가리키는 Pointer이고, Key는 인덱스의 검색 키를 의미합니다. 당연히 인덱스 색인 조건에 따라 K1 < K2... < Kn-1 순으로 정렬이 되어 저장됩니다.

 

리프노드는 다음으로 가리킬 노드의 위치가 없기 때문에 리프 노드의 포인터에는 실제 데이터가 저장되어 있는 위치를 가리키게 됩니다. 

 

 

1-1-1. Internal Node (Branch)

루트, 리프가 아닌 중간 노드는 다음의 특징에 따라서 구성됩니다.

P1 포인터가 가리키는 다음 노드의 Key들은 K1보다 작아야합니다.

 

 

즉 이 부분을 보게 되면 Einstein이 가리키는 노드 (Brandt, Califieri, Crick)의 값들이 모두 Einstein보다 정렬 순서가 앞이어야 합니다.

 

1-1-2. Leaf Node

 

모든 Leaf Node는 연결 리스트로 이루어져 있기 때문에 다음 Leaf Node를 가리키는 포인터를 가지고 있습니다.

그리고 각각 Key에 대한 Pointer는 실제 레코드가 저장된 위치를 가리키고 있습니다.

 

1-2. 구조를 통해 살펴본 B+-Tree의 특징

위 구조를 통해 다음과 같이 이해할 수 있습니다.

 

1-2-1. 정렬

결국 index란 key들이 정렬된 상태로 저장되어 있는 자료구조입니다. 이 정렬조건을 활용해서 범위 탐색을 할 경우 모든 leaf 노드들은 순차 탐색이 가능합니다. 즉 아래와 같이 수행이 되는 것이죠.

출처: https://d2.naver.com/helloworld/1155

 

범위 스캔을 진행하려면 당연히 시작 키와 끝 키가 필요합니다. 첫 번째로 루트에서부터 리프까지 시작 키를 찾습니다. 그리고 순차적으로 리프노드를 탐색하면서 끝 키에 도달할 때까지 키를 읽습니다. 

 

1-2-2. 컬럼의 순서

여러 개의 컬럼으로 인덱스를 생성하게 되면 두번째 컬럼은 첫번째 컬럼에 의존적으로 정렬이 됩니다. 따라서 선두 컬럼이 조건문에 없게 되면 해당 인덱스는 절대 사용할 수 없게 됩니다.

CREATE TABLE sample (
    a INT NOT NULL,
    b VARCHAR(255),
    c BIGINT
);

CREATE INDEX idx ON sample (a, b);

select * 
from sample
where b = "asd";

>> index 사용할 수 없음.

 

2. 인덱스 설계

앞서 인덱스의 구조와 특징을 살펴보았는데요, 이를 토대로 인덱스를 생성할 때 생각해봐야 할 점에 대해 적어보겠습니다.

2-1.  조건절에 자주 등장하는 컬럼

우선 Where절에 자주 등장하는 컬럼의 경우 Index 생성을 고려해보는 것이 좋습니다. 조건을 만족하는 데이터가 전체 데이터의 15~20%라면 생성을 하는 것이 좋습니다. 

2-2-1. 조건절에 항상 사용되는 컬럼

위 구조에서 살펴보았듯, 결합 인덱스의 경우 선두 컬럼이 조건절에 포함되지 않으면 인덱스를 사용할 수 없습니다.

따라서 조건절에 항상 포함된다면, 선두 컬럼으로 고려해보는 것이 좋습니다.

2-2-2. 항상 '='로 비교되는 컬럼

조건절에서 사용되는 컬럼 가운데 '=' 혹은 in이나 or과 같이 내부적으로 '='연산을 수행하는 조건으로 사용되는 컬럼이 선두 컬럼에 있으면 좋습니다. 범위 조건 (range scan)이 선두 컬럼에 잡히게 되면 뒤에 있는 Index 조건들은 필터조건으로만 사용되게 되어 인덱스 스캔 범위를 줄일 수 없습니다.

2-2-3. 분포도가 좋은 컬럼

10명의 사람에 대한 데이터가 있다고 가정해 봅시다.

주민등록번호는 10명이 모두 다른 데이터를 가지고 있을 것이고, 성별은 보통 5:5의 비율을 가지고 있을 것입니다.

 

이때 주민등록번호와 같이 필터링이 많이 될 수 있는 정보를 선두 컬럼에 배치하는 것이 좋습니다.

2-2-4. order by 절에 기술된 순서

인덱스는 그 자체로 컬럼들 간에 정렬된 순서를 보장하기 때문에 order by 절에 기술된 순서로 인덱스가 잡혀 있다면, 데이터를 가져온 뒤 별도로 정렬을 수행하지 않아도 됩니다. 정렬을 수행하려면 임시 테이블에 데이터를 모은 뒤 정렬하는 과정이 필요하게 되는데 이 과정이 생략된다는 것은 엄청난 성능적 이득을 가져올 수 있습니다.

2-2 조인 조건으로 사용되는 컬럼

조인 조건으로 자주 등장하는 컬럼에 대해서도 인덱스 생성을 고려해 보는 것이 좋습니다.

2-3 인덱스를 사용할 수 없는 조건

특정 조건에 따라서 인덱스를 사용할 수 없는 경우가 있습니다. 다음과 같은 케이스는 인덱스를 사용할 수 없기 때문에 튜닝이 필요합니다.

2-3-1 Like 검색의 좌변에 %가 붙는 경우

CREATE TABLE sample (
    a INT NOT NULL,
    b VARCHAR(255),
    c BIGINT
);

CREATE INDEX idx ON sample (b);

select * 
from sample
where b like "%asd";

>> index 사용할 수 없음.

 

인덱스는 일반적으로 문자열의 시작 부분부터 검색을 최적화하도록 설계되었습니다. 좌변에 %를 붙이면, 검색이 문자열의 임의의 위치에서 시작할 수 있기 때문에 인덱스를 사용할 수 없게 됩니다. 이는 전체 테이블을 스캔해야 하는 상황을 초래합니다.

 

2-3-2 부정 연산자를 사용할 경우 

비교 연산자(=, <, >, <=, >=, BETWEEN, IN)를 제외한 부정 연산자 (!=, <>)를 사용하는 경우에도 인덱스 사용에 제약이 있습니다.

SELECT * FROM table_name WHERE column != 'value';

>> 최적화

SELECT * FROM table_name WHERE column < 'value' OR column > 'value';

 

부정 연산자는 범위 검색과는 달리, 특정 값을 제외한 모든 값을 검색해야 하기 때문에 인덱스의 효율성을 떨어뜨립니다. MySQL 옵티마이저는 이러한 조건을 효율적으로 처리하기 위해 인덱스를 사용하지 않고 전체 테이블을 스캔할 수 있습니다.

2-3-3 인덱스의 칼럼을 조건절에서 가공하는 경우.

인덱스는 컬럼의 실제 값에 대한 정렬된 구조를 사용합니다. 산술 연산이 포함된 조건은 각 행에 대해 계산을 수행해야 하므로, 인덱스를 사용할 수 없습니다. 이 경우, MySQL은 전체 테이블 스캔을 수행하게 됩니다.

SELECT * FROM employee WHERE salary * 12 < 10000;

>> 최적화

SELECT * FROM employee WHERE salary < 10000 / 12;

 

3 끝으로...

오늘은 MySQL의 인덱스를 사용하는 방법에 대해 정리해 보았는데요, 실제로 현업을 하다 보면 항상 최적화된 쿼리를 사용할 수 없는 경우가 많은 것 같습니다.

 

• 기존에 생성한 인덱스가 시간이 지나고, 해당 기능이 사용되지 않게 되면서 인덱스가 방치된 경우
• 기존에 생성된 인덱스 수가 너무 많아서, 인덱스를 추가하기 어려운 경우
  • 이 경우 기존 인덱스를 활용하기 위해 쿼리가 수정되는 경우가 많습니다.
• JPA와 같은 ORM을 사용하며 원하는 쿼리를 만들기가 어려운 경우

하지만, 그래도 이러한 인덱스에 대한 지식을 바탕으로 주기적으로 점검 및 추가/삭제를 진행하며 운영을 하는 것도 Backend 개발자로서의 중요한 역할이라 생각합니다.

 

읽어주셔서 감사합니다.