대표적인 인덱스인 B-Tree 인덱스를 MySQL의 관점에서 알아봅시다.
구조
Tree는 루트 노드와 리프 노드 그 사이에 브랜치 노드로 이루어져 있습니다.
그중 리프 노드에 데이터 레코드의 주솟값을 저장하는 것이 Tree 자료 구조를 사용한 인덱스입니다.
B-Tree의 B는 Balanced의 약자입니다. 여기서 Balance(균형)은 트리의 높이가 균형을 이룬다는 뜻입니다. 균형을 이룬다는 뜻은 루트 노드에서 리프 노드까지의 거리를 일정하게 유지하는 것을 의미합니다.
리프 노드까지의 거리를 균일하게 유지하는 이유는 루트 노드에서 리프 노드까지의 탐색 시간을 줄이기 위해서입니다. 트리가 한쪽으로 편향되어 있다면 브랜치 노드가 많아져 리프노드까지의 탐색 시간이 증가합니다.
이러한 균형 잡힌 트리를 유지하기 위해 노드 삽입, 삭제 과정에서 복잡한 과정이 필요합니다.
B-Tree의 리프 노드는 정렬되어 있습니다. B-Tree 인덱스에 값을 삽입할 때 해당 값이 삽입될 위치를 계산해 정렬 상태를 유지합니다. 즉, 다음과 같은 정렬 상태를 유지합니다.
MySQL에서 B-Tree 인덱스를 사용하는 법은 스토리지 엔진에 따라 다릅니다. InnoDB 스토리지 엔진은 PK 클러스터링 인덱스를 사용합니다. 즉, InnoDB 테이블은 PK에 대한 인덱스가 자동으로 생성되고 세컨더리 인덱스는 리프 노드에 데이터 레코드의 주소가 아닌 PK를 저장합니다.
만약 세컨더리 인덱스로 검색을 했다면 다음과 같은 순서로 레코드를 탐색합니다.
1. 세컨더리 인덱스에서 PK 탐색
2. 프라이머리 키 인덱스로 레코드 주소 탐색
즉, InnoDB 스토리지 엔진은 모든 세컨더리 인덱스 검색에서 PK를 저장하는 B-Tree를 한 번 더 검색해야 합니다.
MyISAM 스토리지 엔진의 경우 인덱스에 데이터 레코드의 주소값이 저장되어 있기 때문에 데이터 파일로 바로 찾아갈 수 있습니다.
💡 InnoDB는 PK로 데이터 레코드들이 클러스터링 되어 있다. 즉, PK 순서대로 레코드가 저장되어 있습니다.
정리하면 InooDB 테이블은 세컨더리 인덱스가 PK를 주소처럼 사용하기 때문에 논리적인 주소를 가지고 MyISAM 테이블은 세컨더리 인덱스가 물리주소(ROWID)를 가집니다.
인덱스 키 추가 및 삭제
인덱스 키 추가
B-Tree에 값을 추가하면 리프 노드에 값이 추가됩니다. 하지만 리프 노드가 꽉 차있으면 리프 노드를 분리시켜야 합니다. 이는 상위 브랜치 노드까지 작업 범위가 넓어짐을 의미합니다. 그래서 B-Tree는 쓰기 작업에 비용이 많이 듭니다.
스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있습니다 다. InnoDB의 경우 체인지 버퍼를 통해 쓰기 지연이 가능합니다. 하지만 PK나 유니크 키의 경우 중복 체크가 필요하기 때문에 즉시 B-Tree에 추가합니다.
인덱스 키 삭제
삭제의 경우 해당 리프 노드를 찾아 삭제 마크만 하면 됩니다. 하지만 삭제 또한 디스크 쓰기가 필요하므로 디스크 I/O가 발생합니다. 추가와 마찬가지로 InnoDB에서 삭제 작업은 버퍼링 될 수 있습니다.
인덱스 키 변경
인덱스 구조상 키 값만 변경하는 것은 불가능합니다. 그래서 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 작업이 수행됩니다.
인덱스 키 검색
인덱스 검색 작업은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하며 비교 작업을 수행합니다. 이를 "트리 탐색"이라 한다. 인덱스 트리 탐색은 SELECT뿐만 아니라 UPDATE나 DELETE를 처리하기 위해 해당 레코드를 먼저 검색해야 할 경우에도 사용됩니다.
B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분(Left-most part)만 일치하는 경우에 사용할 수 있습니다. 부등호 비교 조건에서도 인덱스를 사용할 수 있지만, 키 값의 뒷부분만 검색하는 용도로는 사용할 수 없습니다. 이는 B-Tree 인덱스의 정렬 방식과 관련 있습니다. 이 내용은 뒷부분에서 다루겠습니다.
또한 인덱스의 키 값에 변형이 가해진 후 비교되는 경우 인덱스를 사용할 수 없습니다. 그래서 함수나 연산을 수행한 결과로 정렬을 하거나 검색하는 작업은 B-Tree의 장점을 이용할 수 없습니다.
InnoDB는 레코드 락을 인덱스에 락을 거는 방법으로 구현합니다. 그래서 UPDATE나 DELETE 문장이 실행될 때 테이블에 적절히 사용할 수 있는 레코드가 락이 걸려 있으면 불필요하게 많은 레코드를 잠글 수 있습니다.
B-Tree 인덱스 사용에 영향을 미치는 요소
B-Tree 인덱스는 인덱스를 구성하는 칼럼의 크기와 레코드의 건수, 유니크한 인덱스 키값의 개수 등에 의해 검색이나 변경 작업의 성능이 영향을 받습니다.
인덱스 키 값의 크기
인덱스는 인덱스 키와 데이터 주소를 저장합니다. 때문에 인덱스 키 값의 크기는 인덱스의 크기를 결정하는 요소입니다. InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 단위로 페이지를 사용합니다. 인덱스도 페이지 단위로 관리되며 노드는 하나의 페이지로 구성됩니다.
B-Tree는 이진트리가 아닙니다. 따라서 여러 개의 자식을 가질 수 있습니다. 자식 노드의 수는 인덱스의 페이지 크기와 키 값의 크기에 따라 결정됩니다. 인덱스 페이지 크기는 innodb_page_size 시스템 변수로 조정할 수 있습니다(기본값 16KB). 만약 인덱스 키 값의 크기가 16Byte라면 다음과 같은 인덱스 페이지가 구성될 것입니다.
자식 노드 주소의 크기는 평균적으로 12바이트로 구성됩니다. 그렇다면 하나의 인덱스 페이지는 16 x 1024 / (16 + 12) = 585개의 인덱스 키를 저장할 수 있습니다. 인덱스 키 값의 크기가 32바이트로 늘어나면 16 x 1024 / (32 + 12) = 372개를 저장할 수 있습니다. 즉, 인덱스 키 값의 크기가 커지면 인덱스 페이지가 저장할 수 있는 인덱스 키 값의 개수가 줄어듭니다.
만약 SELECT 쿼리로 500개의 레코드를 읽어야 한다면 위의 경우 하나의 페이지로 해결할 수 있지만 인덱스 키 값의 크기가 더 큰 경우 최소 두 개 이상의 페이지를 읽어야하며 이는 디스크 I/O의 증가로 이어집니다.
또한 인덱스 키 값의 크기가 커짐에 따라 전체적인 인덱스의 크기가 커지고 인덱스를 캐시해 두는 버퍼 풀의 효율도 떨어집니다.
💡 InnoDB의 B-Tree 인덱스를 페이지 관점에서 그린 그림을 참고하자.
B-Tree 깊이
트리의 깊이는 검색을 위해 몇개의 노드를 읽을지 결정합니다. 하지만 B-Tree 인덱스의 깊이를 직접 제어할 방법은 없습니다.
선택도(기수성)
모든 인덱스 키 값 중 유니크한 값의 수를 의미합니다. 중복된 값이 많아질수록 기수성은 낮아 선택도 또한 떨어집니다. 인덱스는 선택도가 높을수록 검색 대상이 줄어들어 처리 속도가 빨라집니다.
다음 예를 보고 선택도에 따른 처리 성능의 차이를 알아봅시다.
country 칼럼과 city 칼럼이 포함된 tb_test 테이블이 있습니다. 전체 레코드는 1만건이며, country 칼럼으로 인덱스가 생성된 상태에서 다음 두 케이스를 살펴봅시다.
A. country칼럼의 유니크한 값의 개수 10개
B. country칼럼의 유니크한 값의 개수 1000개
다음 쿼리를 실행합니다.
mysql> SELECT *
FROM tb_test
WHERE country='KOREA' AND city='SEOUL';
MySQL는 인덱스의 유니크한 값의 개수를 관리합니다. 때문에 city 칼럼의 기수성은 작업 범위에 영향을 주지 않습니다. 인덱스를 사용하는 과정을 살펴보면
1. country='KOREA'를 만족하는 인덱스 키의 시작점을 찾습니다.
2. country='KOREA'가 아닐때까지 city='SEOUL'인 레코드를 탐색합니다.
여기서 A 케이스와 B 케이스가 2번 과정에서 읽는 레코드 수가 달라집니다. A 케이스의 경우 1000(10000 / 10)개의 레코드를 읽어야하고 B 케이스의 경우 10(10000 / 1000)개의 레코드를 읽어야합니다.
이처럼 인덱스에서 유니크한 값의 개수는 인덱스나 쿼리의 효율성에 큰 영향을 미칩니다.
읽어야 하는 레코드 건수
인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블을 읽는 것보다 비용이 높은 작업입니다. 그래서 인덱스를 이용한 읽기의 손익 분기점이 얼마인지 판단할 필요가 있습니다. 옵티마이저는 인덱스를 통해 레코드를 읽는 작업이 테이블에서 직접 레코드를 읽는 것보다 4~5배 정도 비용이 더 많이 든다고 예측합니다. 그래서 전체 테이블 레코드의 20~25%를 넘어서는 레코드를 읽어야 한다면 테이블을 직접 모두 읽고 필요한 레코드만 가려내는 방식으로 처리하는 것이 효율적입니다.
'Database' 카테고리의 다른 글
| [MySQL] B-Tree 인덱스 - 3 (0) | 2023.05.19 |
|---|---|
| [MySQL] B-Tree 인덱스 - 2 (0) | 2023.05.12 |
| [MySQL] 인덱스 - 개요 (0) | 2023.04.21 |
| [MySQL] 데이터 암호화 (0) | 2023.03.29 |
| [MySQL] 데이터 압축 (0) | 2023.03.24 |
