B-Tree
B-Tree는 인덱싱 알고리즘 중 가장 보편적으로 사용되고, 가장 먼저 도입된 알고리즘이면서 여전히 가장 범용적인 목적으로 사용되는 인덱스 알고리즘 입니다. 그리고 B-Tree의 B는 Binary(이진)이 아닌, Balanced를 의미합니다.
B-Tree는 칼럼의 원래 값을 변형시키지 않고 인덱스 구조체 내에서는 항상 정렬된 상태로 유지합니다.
특별한 검색 조건이 없는 경우엔 대부분 B-Tree 또는 B+Tree를 사용합니다.
B-Tree 인덱스 구조
인덱스는 트리 구조로 되어 있으며, 루트 노드 → 브랜치 노드 → 리프 노드 순으로 구성됩니다. 리프 노드에는 실제 데이터를 가리키는 프라이머리 키 주소를 가지고 있습니다.
인덱스 자체는 데이터 테이블의 키 컬럼만을 포함하고, 실제 데이터는 별도로 저장합니다.
아래는 B-Tree 인덱스의 각 노드와 데이터 파일 관계를 나타낸 그림입니다.
그림에서 보면, 인덱스와 키 값은 모두 정렬돼 있지만, 데이터 파일의 레코드는 정렬돼 있지 않고 임의의 순서로 저정돼 있습니다.
이는 많은 경우 INSERT 순서대로 저장되지만, 삭제된 공간이 재사용되기 때문에 항상 순서대로 저장된다고 보장할 수 없기 때문입니다.
MyISAM과 InnoDB 인덱스 방식의 차이
MyISAM
리프 노드가 물리적인 레코드 주소를 가지고 있어, 인덱스에서 바로 데이터 파일로 접근이 가능합니다.
따라서 인덱스를 한 번만 검색하면 바로 레코드로 접근이 됩니다.
InnoDB
리프 노드가 프라이머리 키 값을 저장하고 있습니다.
즉 세컨더리 인덱스를 검색하면, 프라이머리 키를 찾고, 이 키를 활용해 레코드에 접근하게 됩니다.
이로 인해서 데이터 검색 시 2번의 인덱스 탐색이 필요하게 됩니다. (세컨더리 인덱스 → 프라이머리 키 인덱스)
두 방식을 나타낸 그림은 아래와 같습니다.
B-Tree 인덱스 키 추가, 삭제, 검색
인덱스 키 추가
새로운 레코드가 삽입되면, 해당 레코드의 키 값을 이용해 B-Tree의 적절한 위치(리프 노드)를 탐색합니다.
그 다음, 리프 노드에 여유 공간이 있다면 바로 추가하고, 리프 노드가 꽉찬 경우 Split(노드 분할)을 합니다. 이는 상위 브랜치까지 노드까지 처리 범위가 넓어지게 되고, 이로 인해 성능 부하가 발생하게 됩니다.
대략적인 비용 측정 관점으로 보면, 예를 들어, 일반적으로 테이블에 레코드 1건을 삽입하는 작업 비용을 1이라 가정할 때, 인덱스가 1개라면 삽입 비용은 1.5정도로 예측을 하고, 인덱스가 3개라면 총 5.5(1.5 * 3 + 1) 수준의 비용이 예측 됩니다. 이 비용은 대부분이 메모리와 CPU에서 처리하는 시간이 아닌, 디스크로부터 인덱스 페이지를 읽고 쓰기를 하는데 걸리는 시간(디스크 I/O)이라는 점입니다.
인덱스 키 삭제
인덱스 키 삭제는 단순하게 처리 됩니다.
리프 노드에서 해당 키의 위치를 찾아 단순히 마크만 하고 끝납니다. 이는 즉시 디스크에서 삭제되지 않고, 이후 재활용됩니다.
단, MyISAM은 인덱시 키 삭제시 삭제를 즉시 수행하지만, InnoDB는 체인지 버퍼(Change Buffer)라는 구조로 지연 처리를 하게 됩니다.
인덱스 키 변경
인덱스의 키 값을 변경하는 것은 단순히 값을 바꾸는 것이 아니라, 삭제를 하고 새로 추가하는 과정을 거칩니다.
이렇게 하는 이유는 키 변경 시에도 노드의 Split이 발생할 수 있기 때문입니다. 내부적으로 insert와 delete를 함께 처리합니다.
InnoDB 스토리지 엔진을 사용하는 테이블에 대해서는 해당 작업이 모두 체인지 버퍼(Change Buffer)를 활용해 지연 처리 될 수 있습니다.
인덱스 키 검색
인덱스 키 검색은 Select, Update, Delete 시 사용됩니다.
검색은 루트 노드 → 브랜치 노드 → 리프 노드 순서로 검색을 하고, 이 과정은 트리 탐색이라고 부르며 O(logN) 수준의 성능을 가집니다.
인덱스 키 검색은 검색 조건이 정확히 일치하거나 값의 앞부분만 일치하는 경우에만 효과적입니다.
LIKE %abc 같은 조건은 사용 불가능하고, 이미 변형된 값(함수나 연산 등)은 테이블 풀 스캔을 유발하기 때문에 인덱스 검색이 불가능합니다.
InnoDB에서의 인덱스와 레코드 잠금 동작
InnoDB 스토리지 엔진은 단순한 데이터 저장만을 넘어 정교한 잠금 메커니즘을 가지고 있습니다.
InnoDB는 UPDATE나 DELETE 문처럼 레코드에 변경이 발생할 수 있는 작업을 실행할 때, 아래와 같은 흐름을 가집니다.
1. 인덱스를 먼저 탐색을 하고 잠급니다.(Next-Key Lock, Gap Lock)
2. 탐색한 인덱스를 통해 찾아낸 해당 테이블의 실제 레코드를 잠급니다.
인덱스를 잠금은 B-Tree 인덱스 구조의 리프 노드에 있는 인덱스 엔트리(인덱스 키 + 레코드 포인터)에 잠금을 거는 것을 의미합니다.
즉, 레코드 잠금이 인덱스를 거쳐서 실행하게 됩니다.
인덱스가 없을 때 발생하는 문제
만약 WHERE 절에 사용하는 컬럼에 적절한 인덱스가 없는 경우라면, InnoDB는 테이블 전체를 스캔하며 조건을 맞는 레코드를 찾고 모든 레코드에 대해 잠금을 걸게 됩니다. 이는 결과적으로 성능 저하와 잠금 경합 문제를 일으킵니다. 심지어 최악의 경우엔 모든 테이블의 모든 레코드를 잠글 수도 있습니다.
인덱스 키 값의 크기
InnoDB 스토리지 엔진은 디스크에 데이터를 페이지(Page) 또는 블록(Block) 단위로 저장합니다.
이는 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 됩니다. 또한, 페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 합니다. 루트와 브랜치, 그리고 리프 노드를 구분한 기준이 바로 페이지 단위입니다.
B-Tree의 자식 노드 개수는 페이지 크기와 인덱스 키 길이에 영향을 받습니다.
하나의 인덱스 페이지에 저장 가능한 "인덱스 키 수 = 페이지 크기 / 키 크기" 가 됩니다.
예를 들어, 하나의 페이지의 크기가 기본 크기(16KB)이고, 키의 크기가 16B이면 인덱스 키의 수는 16KB / 16B로 약 1000개가 됩니다.
즉, 인덱스 키 값의 크기가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고, 그만큼 느려지게 됩니다.
또한, 인덱스 키 값의 길이가 길어진다는 것은 전체적인 인덱스의 크기가 커진다는 것을 의미합니다.
인덱스를 캐시해두는 InnoDB의 버퍼 풀이나 MyISAM의 키 캐시 영역은 크기가 제한적이기 때문에 하나의 레코드를 위한 인덱스 크기가 커지면 커질수록 메모리에 캐시해 둘 수 있는 레코드 수는 줄어듭니다. 이는 메모리의 효율을 떨어트리게 됩니다.
B-Tree 깊이와 키 크기
인덱스 깊이
B-Tree 인덱스는 계층적 구조로 되어 있으며, 루트 노드부터 리프 노드까지의 거리(계층 수)를 인덱스의 깊이라고 부릅니다.
검색 시에 이 깊이만큼 디스크에서 페이지를 랜덤하게 읽는 횟수가 발생하게 됩니다.
키 값의 크기와 B-Tree의 관계
인덱스 키 크기가 작을수록 한 페이지에 더 많은 키를 담을 수 있습니다.
예를 들어, 키가 16바이트 일때는 한 페이지에 약 585개의 키를 담을 수 있고, 트리 깊이가 3이라면 최대 585^3개로 2억개의 키 저장이 가능합니다. 키가 32바이트 일때는 페이지 당 키 개수가 줄어들고, 전체적으로 커버할 수 있는 키는 372^3개로 5천만개 수준으로 감소합니다.
B-Tree의 깊이가 깊어지는 경우
디스크에서 읽어야 할 페이지 수가 증가하기 때문에, 검색 속도가 저하 됩니다.
예를 들어, SELECT 쿼리에서 트리 깊이가 깊을수록 더 많은 디스크 접근이 필요하게 됩니다.
대부분의 실무 환경에서 트리 길이가 3-4 단계 수준에 그칩니다.
5단계 이상으로 깊어지는 경우는 거의 존재하지 않습니다. 이는 현대의 디스크 I/O 속도와 메모리 캐싱 전략이 인덱스를 효과적으로 관리하고 있기 때문입니다.
따라서, 인덱스 키 크기는 가능하면 작게 설계하는 것이 좋습니다. 키가 작을수록 더 많은 키를 한 페이지에 저장할 수 있고, 이는 곧 B-Tree 깊이를 얕게 유지시켜줍니다. 그 결과 디스크 I/O 감소 → 검색 성능 향상 → 전체 DB 성능 최적화로 이어집니다.
선택도(기수성)
선택도란 인덱스 키 값 중 유니크한 값의 수를 의미합니다.
예를 들어, 전체 인덱스 키가 100개인데, 유니크한 값이 10개뿐이라면 선택도는 10이 됩니다.
선택도가 낮은 경우, 동일한 값이 많이 존재하면 인덱스를 이용해도 결과가 너무 많아져 성능 저하가 발생합니다.
예를 들어, 성별, Boolean 타입(예/아니오) 같은 경우는 선택도가 낮기 때문에 인덱스 효과가 적습니다.
반면, 선택도가 높은 경우 검색 대상이 줄어들기 때문에 인덱스를 통해 빠르게 조회가 가능해집니다.
예를 들어, 주민등록번호, 이메일, 사용자 ID는 신뢰도가 매우 높고, 인덱스 효과를 극대화합니다.
결과적으로 유니크한 값이 많을 수록 선택도는 높아지고 인덱스 효과가 좋아지고, 중복되는 값이 많아질수록 선택도는 낮아지고 인덱스 효과도 나빠집니다.
선택도가 낮아도 유용한 경우
선택도가 낮은 컬럼에 인덱스를 건다고 해서 무조건 쓸모가 없는 것은 아닙니다.
정렬, 그룹핑과 같은 작업에서는 여전히 인덱스가 유용할 수 있기 때문입니다.
하지만, 검색 성능을 높이기 위해 인덱스를 설계할 때는, 선택도가 높은 컬럼을 위주로 인덱스를 고려해야 효율이 좋습니다.
예제로 보는 인덱스 선택도
SELECT * FROM tb_test
WHERE country='KOREA' AND city='SEOUL';
country에만 인덱스가 걸린 상태에서 두 케이스를 비교해보겠습니다. (단, 테이블의 전체 레코드 수는 1만건임을 가정합니다.)
첫번째 케이스는 country의 유니크 값이 10개이고, 두번째 케이스는 유니크 값이 1000개라고 가정을 합니다.
결과 적으로 두번째 케이스는 WHERE country=? 만으로 범위를 좁혀서 평균 10건 정도만 읽으면 되지만,
A번재 케이스는 평균적으로 약 1,000건을 읽어야 하므로 비효율적입니다.
선택도가 낮은 컬럼에 인덱스를 걸면 생기는 문제
인덱스를 사용하더라도 많은 레코드를 읽게 되므로 성능 향상 효과가 적어집니다.
특히, MySQL은 유니크한 값의 갯수를 기본적으로 관리하지 않기 때문에 옵티마이저가 효율적인 인덱스를 판단하지 못합니다. 이로 인해, 불필요한 인덱스 스캔이 발생할 수 있습니다.
읽어야 하는 레코드의 건수
DBMS 옵티마이저는 인덱스를 거쳐 읽는 것과 테이블을 전체 스캔해서 읽는 것중 어느게 더 좋은 방법일지 판단합니다.
일반적으로 전체 테이블의 20-25% 이상을 읽어야 하는 경우, 인덱스 사용보다 풀 스캔이 더 효율적일 수 있습니다. 그 이유는 인덱스를 거치는 것이 디스크 I/O가 4-5배 더 비싸기 때문입니다.
예를 들면, 전체 100만 건 중 50만 건을 읽는 경우, 인덱스를 건너뛰고 테이블을 직접 읽는 방식을 더 낫다고 판단하는 것입니다.
마무리
인덱스는 무조건 사용하는게 좋은 것이 아닙니다. 사용 패턴에 따라, 오히려 성능을 떨어뜨릴 수도 있습니다. 다음과 같은 경우 주의해야 합니다.
- 인덱스 키가 너무 긴 경우
- 선택도가 너무 낮은 경우
- 읽어야 할 레코드가 전체 20%이상인 경우
결국 좋은 인덱스는 잘 골라 쓰는 것이 핵심입니다.
참조
- Real MySQL 8.0(1권)
'Mysql' 카테고리의 다른 글
| Index (0) | 2025.04.23 |
|---|---|
| 디스크 I/O 병목 (0) | 2025.04.22 |
| Master & Slave 구조 (0) | 2025.03.04 |
| MySQL 구조와 동작 원리 (0) | 2025.02.18 |
| 커버링 인덱스 & 성능 테스트 (0) | 2025.01.30 |
