# B-Tree 인덱스 스캔 방식
💡
이 글은 Real MySQL 8.0과 공식 문서를 읽고 개인적으로 정리한 내용입니다.
### **1\. 인덱스란?** ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1691564659611/374f7e4a-a335-4531-bdef-0b278995abec.png align="center") *(이미지 출처:* [https://tecoble.techcourse.co.kr/post/2021-09-18-db-index/](https://tecoble.techcourse.co.kr/post/2021-09-18-db-index/)*)* 인덱스는 특정 값을 가진 행을 빨리 찾는 데에 사용되는 자료구조입니다. 인덱스가 없다면 첫 번째 행부터 최악의 경우 마지막 행까지 전체 테이블을 읽어봐야 행을 찾을 수 있습니다. 하지만 테이블에 인덱스가 있다면 모든 데이터를 읽을 필요 없이 데이터 파일의 중간에서 찾을 위치를 빠르게 결정할 수 있습니다. 대부분의 MySQL 인덱스(PRIMORY KEY, UNIQUE, INDEXT 및 FULLTEXT)는 `B-Tree`에 저장됩니다. (공간 인덱스는 `R-Tree`를 사용합니다. MEMORY 테이블도 해시 인덱스를 지원합니다. InnoDB는 전문 검색 인덱스에 [반전된 목록을 사용](https://dev.mysql.com/doc/refman/8.0/en/innodb-fulltext-index.html)합니다.) 인덱스를 역할별로 구분해 본다면 `프라이머리 키`(Primary key)와 `보조 키`(세컨더리 인덱스, Secondary key)로 구분할 수 있습니다. * 프라이머리 키(PK): 레코드를 대표하는 컬럼의 값, 즉 식별자로 만들어진 인덱스입니다. * 보조 키(SK): 프라이머리 키를 제외한 나머지 모든 인덱스는 보조 키입니다. 유니크 인덱스는 PK와 성격이 비슷하고 PK를 대체할 수 있다고 해서 대체 키라고도 하는데, 별도로 분류하기도 하고 그냥 SK로 분류하기도 합니다. 인덱스를 데이터 저장 방식(알고리즘)별로 구분해 본다면 대표적으로 `B-Tree 인덱스`와 `Hash 인덱스`로 구분할 수 있습니다. * B-Tree 알고리즘: 컬럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘입니다. 위치 기반 검색을 지원하기 위한 R-Tree 인덱스 알고리즘 또한 B-Tree의 응용 알고리즘입니다. * Hash 인덱스 알고리즘: 컬럼의 값으로 해시값을 계산해서 인뎅싱하는 알고리즘으로, 매우 빠른 검색을 지원합니다. 값을 변형하여 인덱싱하므로 값의 일부만 검색하거나 범위를 검색할 때는 사용할 수 없습니다. ### **2\. B-Tree 인덱스** ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1691564780828/9ca4bbcb-1329-4a1b-a97d-2dadaf1a5697.png align="center") *(이미지 출처:* [https://tecoble.techcourse.co.kr/post/2021-09-18-db-index/](https://tecoble.techcourse.co.kr/post/2021-09-18-db-index/)*)* `B-Tree`는 데이터베이스의 인덱싱 알고리즘 가운데 가장 범용적인 알고리즘입니다. 컬럼의 원래 값을 변형시키지 않고 인덱스 구조체 내에서 각 Key의 왼쪽 자식은 항상 Key보다 작은 값을, 오른쪽 자식은 큰 값을 가지는 상태로 유지합니다. Tree 기반의 DB Index는 특정 컬럼의 값(Key)에 해당하는 노드에 데이터의 위치(Value)를 저장합니다. `B-Tree`의 Key-Value 값들은 항상 Key를 기준으로 오름차순 정렬입니다. 이로 인해 부등호 연산시 `Hash 인덱스`보다 효율적인 데이터 탐색이 가능합니다. **2.1. B-Tree 인덱스를 통한 데이터 읽기** MySQL이 인덱스를 이용하는 대표적인 방법 세 가지로 `인덱스 레인지 스캔`, `인덱스 풀 스캔`, `루스 인덱스 스캔`이 있습니다. **2.1.1. 인덱스 레인지 스캔** `인덱스 레인지 스캔`은 검색해야할 인덱스의 범위가 결정됐을 때 사용되며 `인덱스 풀 스캔`, `루스 인덱스 스캔`보다 빠른 방법입니다. 루트 노드에서부터 브랜치 노드를 거치고 최종적으로 리프 노드까지 찾아 들어가서 필요한 레코드의 시작 지점을 찾습니다. 시작 지점을 찾았다면 그때부터 리프 노드 레코드의 끝 지점까지 쭉 읽습니다. 스캔 중 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아서 다시 스캔합니다. 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 클라이언트에게 반환하고 쿼리를 끝냅니다. **2.1.2. 인덱스 풀 스캔** `인덱스 풀 스캔`은 `인덱스 레인지 스캔`처럼 인덱스를 사용하지만, 인덱스의 처음부터 끝까지 모두 읽는 방식이며, `인덱스 레인지 스캔`보다는 느리지만 `테이블 풀 스캔`보다는 효율적입니다. 대표적으로 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우 사용됩니다. 예를 들어, 인덱스는 (A, B, C) 컬럼 순서로 만들어져 있지만 쿼리의 조건절은 B나 C 컬럼으로 검색하는 경우 `인덱스 풀 스캔`이 사용됩니다. 인덱스의 전체 크기는 테이블 자체의 크기보다는 훨씬 작으므로 `인덱스 풀 스캔`은 테이블 전체를 읽는 `테이블 풀 스캔`보다는 적은 디스크 I/O로 쿼리를 처리할 수 있습니다. **2.1.3. 루스 인덱스 스캔** `루스 인덱스 스캔`은 `인덱스 레인지 스캔`과 비슷하게 동작하지만, 중간중간 필요 없는 인덱스 키 값을 건너뛰고 다음으로 넘어가는 형태로 처리하는 방법입니다. `GROUP BY`, `MIN`, `MAX` 함수에 대해 최적화를 하는 경우 사용됩니다. 예를 들어 인덱스에서 WHERE 조건을 만족하는 범위 전체를 다 스캔할 필요가 없다는 것을 옵티마이저가 알고 있는 경우, 조건에 만족하지 않는 레코드는 무시하고 다음 레코드로 이동합니다. **2.1.4. 인덱스 스킵 스캔(**[**스킵 스캔**](https://dev.mysql.com/doc/refman/8.0/en/range-optimization.html#range-access-skip-scan)**)** MySQL 8.0 버전에 도입된 `인덱스 스킵 스캔`은 다중 칼럼 인덱스에서 옵티마이저가 특정 컬럼 인덱스를 건너 뛰어서 검색할 수 있도록 하는 최적화 방법입니다. `루스 인덱스 스캔`은 GROUP BY 작업을 처리하기 위해 인덱스를 사용하는 경우에만 적용할 수 있었지만, `인덱스 스킵 스캔`은 WHERE 조건절의 검색을 위해 사용 가능합니다. --- ### **🎯정리** * 인덱스는 특정 값을 가진 행을 빨리 찾는 데에 사용되는 자료구조입니다. * `B-Tree 인덱스`는 컬럼의 원래 값을 변형시키지 않고 항상 정렬된 상태로 유지합니다. * `인덱스 레인지 스캔`은 인덱스 스캔 중 가장 효율적인 방법입니다 * `인덱스 풀 스캔`은 인덱스 전체를 읽는 방법으로, `테이블 풀 스캔`보다는 효율적입니다. * `루스 인덱스 스캔`은 필요 없는 인덱스 키 값을 건너 뛰는 방법입니다. * `인덱스 스킵 스캔`은 WHERE 조건절에서 사용할 수 있는 인덱스 키 값 스킵 방법입니다. --- ### **🔖참고** * [https://product.kyobobook.co.kr/detail/S000001766482](https://product.kyobobook.co.kr/detail/S000001766482) * [https://dev.mysql.com/doc/refman/8.0/en/](https://dev.mysql.com/doc/refman/8.0/en/) * [https://tecoble.techcourse.co.kr/post/2021-09-18-db-index/](https://tecoble.techcourse.co.kr/post/2021-09-18-db-index/) * [https://hudi.blog/mysql-index-scan/](https://hudi.blog/mysql-index-scan/)