1. 인덱스란?
(이미지 출처: https://tecoble.techcourse.co.kr/post/2021-09-18-db-index/)
인덱스는 특정 값을 가진 행을 빨리 찾는 데에 사용되는 자료구조입니다.
인덱스가 없다면 첫 번째 행부터 최악의 경우 마지막 행까지 전체 테이블을 읽어봐야 행을 찾을 수 있습니다. 하지만 테이블에 인덱스가 있다면 모든 데이터를 읽을 필요 없이 데이터 파일의 중간에서 찾을 위치를 빠르게 결정할 수 있습니다.
대부분의 MySQL 인덱스(PRIMORY KEY, UNIQUE, INDEXT 및 FULLTEXT)는 B-Tree에 저장됩니다. (공간 인덱스는 R-Tree를 사용합니다. MEMORY 테이블도 해시 인덱스를 지원합니다. InnoDB는 전문 검색 인덱스에 반전된 목록을 사용합니다.)
인덱스를 역할별로 구분해 본다면 프라이머리 키(Primary key)와 보조 키(세컨더리 인덱스, Secondary key)로 구분할 수 있습니다.
프라이머리 키(PK): 레코드를 대표하는 컬럼의 값, 즉 식별자로 만들어진 인덱스입니다.
보조 키(SK): 프라이머리 키를 제외한 나머지 모든 인덱스는 보조 키입니다. 유니크 인덱스는 PK와 성격이 비슷하고 PK를 대체할 수 있다고 해서 대체 키라고도 하는데, 별도로 분류하기도 하고 그냥 SK로 분류하기도 합니다.
인덱스를 데이터 저장 방식(알고리즘)별로 구분해 본다면 대표적으로 B-Tree 인덱스와 Hash 인덱스로 구분할 수 있습니다.
B-Tree 알고리즘: 컬럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘입니다. 위치 기반 검색을 지원하기 위한 R-Tree 인덱스 알고리즘 또한 B-Tree의 응용 알고리즘입니다.
Hash 인덱스 알고리즘: 컬럼의 값으로 해시값을 계산해서 인뎅싱하는 알고리즘으로, 매우 빠른 검색을 지원합니다. 값을 변형하여 인덱싱하므로 값의 일부만 검색하거나 범위를 검색할 때는 사용할 수 없습니다.
2. B-Tree 인덱스
(이미지 출처: 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. 인덱스 스킵 스캔(스킵 스캔)
MySQL 8.0 버전에 도입된 인덱스 스킵 스캔은 다중 칼럼 인덱스에서 옵티마이저가 특정 컬럼 인덱스를 건너 뛰어서 검색할 수 있도록 하는 최적화 방법입니다.
루스 인덱스 스캔은 GROUP BY 작업을 처리하기 위해 인덱스를 사용하는 경우에만 적용할 수 있었지만, 인덱스 스킵 스캔은 WHERE 조건절의 검색을 위해 사용 가능합니다.
🎯정리
인덱스는 특정 값을 가진 행을 빨리 찾는 데에 사용되는 자료구조입니다.
B-Tree 인덱스는 컬럼의 원래 값을 변형시키지 않고 항상 정렬된 상태로 유지합니다.인덱스 레인지 스캔은 인덱스 스캔 중 가장 효율적인 방법입니다인덱스 풀 스캔은 인덱스 전체를 읽는 방법으로,테이블 풀 스캔보다는 효율적입니다.루스 인덱스 스캔은 필요 없는 인덱스 키 값을 건너 뛰는 방법입니다.인덱스 스킵 스캔은 WHERE 조건절에서 사용할 수 있는 인덱스 키 값 스킵 방법입니다.