B-Tree 인덱스
B-Tree는 가장 범용적인 인덱스 알고리즘입니다. 칼럼의 원래 값을 변형하지 않고, 항상 정렬된 상태로 유지하는 알고리즘입니다.
구조 및 특성
B-Tree는 최상위에 하나의 루트 노드(Root node)가 존재하고, 그 하위에 자식 노드가 붙어있는 형태입니다.
가장 하위에 있는 노드를 리프 노드(Leaf node), 중간의 노드를 브랜치 노드(Branch node)라 부릅니다.
인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있습니다.
위는 b-tree 인덱스의 구조입니다. 인덱스의 키를 보시면 모두 정렬된 형태인 것을 볼 수 있습니다.
그러나 데이터 파일 부분을 보면, 레코드는 정렬되지 않고 있습니다. 화살표가 여기저기 섞여있죠?
데이터 파일의 레코드는 insert 순서대로 저장되는 것이 아닌, 기존 레코드가 삭제된 빈 공간을 재활용하도록 설계됐기 때문입니다.
인덱스의 리프 노드는 데이터 파일에 저장된 레코드의 주소를 가지고 있습니다. 위 사진은 InnoDB에서 B-Tree의 리프 노드와 데이터 파일간의 관계를 보여줍니다.
보이는 것 처럼 InnoDB에서 인덱스를 통해 레코드를 읽을 때, 데이터 레코드를 바로 찾지 않고 다시 한 번 프라이머리 키 인덱스의 루트 노드로 가는 모습을 볼 수 있습니다.
InnoDB 테이블의 프라이머리 키를 주소처럼 사용합니다. 물리적인 주소가 아닌 논리적인 주소를 사용하는 것이죠.
InnoDB 는 프라이머리 키 값을 이용해 프라이머리 키 인덱스를 한 번 더 검색한 후, 프라이머리 키 인덱스의 리프 페이지에 저장돼 있는 레코드를 읽어옵니다.
(당연히 애초에 프라이머리 키에 접근하면 위와 같은 반복 과정은 필요가 없겠죠)
따라서 PK가 아닌 세컨더리 인덱스를 통해 데이터를 읽을 때는, 반드시 프라이머리 키를 저장하는 B-Tree 인덱스를 다시 한 번 검색해야 합니다.
B-Tree 인덱스 키 추가 및 삭제
인덱스 키 추가 및 삭제는 쿼리의 성능에 영향을 주므로, 주의할 점을 알아둬야 할 것입니다.
인덱스 키 추가
B-Tree에 키 값이 저장될 때는 트리 상의 적절한 위치를 검색해야 합니다. 저장 위치가 결정되면 키 값과 주소 정보를 리프 노드에 저장해야 하는데,
리프 노드가 꽉 찼을 때는 리프 노드를 분리시켜야 하므로 상위 브랜치 노드까지 변경이 일어나야 합니다. 따라서 B-Tree는 상대적으로 쓰기 작업(새로운 키 추가)에 비용이 많이 듭니다. 이 비용의 대부분이 메모리와 CPU 처리가 아닌, 디스크로부터 인덱스 페이지를 읽고 쓰기 때문입니다.
인덱스 키 삭제
삭제는 상당히 간단합니다. 해당 키가 있는 리프 노드를 찾아서 삭제 마크만 하면 끝납니다. 남는 공간은 그대로 방치하거나 재활용할 수 있습니다.
하지만 이 작업 역시 디스크 I/O가 필요하므로, InnoDB에서는 버퍼링해 지연 처리하는 기능이 존재합니다.
인덱스 키 변경
인덱스의 키 값에 따라 리프 노드의 위치가 변경되므로, 키가 변경되면 단순히 인덱스의 값만 변경할 수 없습니다.
따라서 키 값을 삭제하고, 다시 새로운 키를 추가하는 형태가 돼야 합니다. 이 작업은 위에 설명한 삭제-추가 작업과 동일하게 처리 됩니다.
인덱스 키 검색
인덱스 검색 작업을 “트리 탐색” 이라고 합니다. 이 작업은 select 뿐이 아닌, update나 delete 상황에서 앞의 레코드를 검색하는 과정에 쓰이기도 합니다.
B-Tree 인덱스 검색은 100% 일치하거나, 값의 앞부분만 일치하는 경우 사용할 수 있습니다.
중요한 점은 인덱스의 키 값에 변형이 가해진 후 비교되는 경우에는 B-Tree의 빠른 검색이 일어날 수 없습니다.
예를 들어 어떤 함수나 연산을 수행한 결과로 정렬하거나 검색을 한다면, 이 변형 값은 B-Tree에 존재하지 않으므로 인덱스 검색이 일어날 수 없습니다. → 예시를 더 찾아야 할듯.
InnoDB에서 인덱스는 큰 의미가 있습니다. InnoDB에서 지원하는 레코드 잠금 혹은 캡 락은, 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식입니다.
따라서 적절한 인덱스가 없으면, update나 delete 시 불필요하게 많은 레코드(심하면 테이블의 전부)를 잠글 수도 있습니다.
B-Tree 인덱스 사용에 영향을 미치는 요소
B-Tee 인덱스는 다양한 요소에 의해 검색 혹은 변경 작업의 성능이 영향을 받습니다.
인덱스 키 값의 크기
인덱스는 페이지 단위로 관리됩니다. 페이지는 디스크에 데이터를 저장하는 가장 기본 단위이며, 읽기/쓰기와 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 합니다.
이진(Binary) 트리는 각 노드가 자식 노드를 2개씩만 가집니다. 인덱스를 이 형태로 관리하면 인덱스 검색이 비효율적일 것입니다. 그래서 인덱스의 B-Tree는 이진 트리의 약자가 아닌 Balance의 약자입니다.
B-Tree의 자식 노드 개수는 가변적입니다. 그렇다면 MySql의 B-Tree는 최대 몇 개 까지 자식 노드를 가질 수 있을까요?
이는 인덱스의 페이지와 키 값의 크기에 따라 결정됩니다.
Mysql 5.7 버전부터는 InnoDB 페이지 크기를 innodb_page_size 시스템 변수를 이용해 4KB~16KB 사이에서 선택 가능한데, 기본적으로는 16KB입니다. 자식 노드의 주소는 6바이트~12바이트 까지 다양한 값을 가질 수 있습니다.
키 값의 크기를 16B, 자식 노드의 크기를 12B, 인덱스 페이지 하나의 크기를 16KB라 가정하면, 한 페이지에 저장할 수 있는 키의 수는
16*1024 / (16+12) = 585개 저장할 수 있습니다.
만약 키 값의 크기가 32B로 늘어난다면, 한 페이지에 저장할 수 있는 갯수가
16*1024 / (32+12) = 372개로 줄어들게 됩니다.
따라서 select 쿼리가 레코드 500개를 읽어야 할 때, 전자는 인덱스 페이지 하나로 해결되지만, 후자는 최소 2번을 읽어야 합니다.
즉, 인덱스를 구성하는 키 값의 크기가 커지면, 그만큼 느려집니다.
또 인덱스의 크기가 커지면 그만큼 메모리에 캐시할 수 있는 레코드 수가 줄어드므로, 메모리의 효율이 떨어질 수 있습니다.
B-Tree 깊이
인덱스 키 값의 크기는 트리의 깊이와도 연관이 있습니다. 위의 예시(키 크기가 16B)에서 트리의 깊이가 3이라면
585 585 585 = 최대 2억개 정도의 키 값을 가질 수 있지만,
키 크기가 32B로 늘어나면
372 372 372 = 최대 5천만 개로 줄어듭니다
결과적으로 키 값의 크기가 커지면 페이지가 담을 수 있는 키 값의 개수가 적어지고, 같은 레코드 건수여도 깊이가 깊어져 디스크 읽기가 더 많이 필요합니다.
선택도(기수성)
인덱스에서 선택도(Selectivity)와 기수성(Cardinality)는 거의 같은 의미로 사용됩니다.
모든 인덱스 키 값 가운데 유니크한 값의 수를 의미하죠.
(인덱스 키 100개중 유니크한 값이 10개면 기수성은 10)
인덱스는 선택도가 높을 수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리됩니다.
선택도가 낮다면 더 많은 데이터를 조회할 것이고, 높다면 더 적은 데이터를 조회하기 때문입니다.
따라서 선택도가 낮다면 그만큼 더 불필요한 데이터를 읽어온다고 할 수 있습니다.
읽어야 하는 레코드의 건수
인덱스를 통해 레코드를 읽는 것은 인덱스를 거치지 않는 것 보다 높은 비용이 듭니다. 따라서 100만 건 중 50만 건을 읽을 때, 전체 테이블을 모두 읽어 50만개를 버릴지, 인덱스를 통해 필요한 50만개를 읽어올 지,
무엇이 더 효율적일지를 판단해야 합니다.
일반적인 dbms의 옵티마이저는 인덱스를 통해 레코드 1건을 읽는 것이, 테이블에서 직접 레코드 1건을 읽는 것 보다 4~5배의 비용이 드는 것으로 추산합니다.
따라서 인덱스를 통해 읽을 레코드가 전체 테이블의 20~25%를 넘어서는 인덱스를 이용하지 않고 테이블을 모두 읽어 필터링하는 것이 효율적입니다.
B-Tree 인덱스를 통한 데이터 읽기
그렇다면 Mysql이 어떻게 인덱스를 이용해 실제 레코드를 읽을까요?
인덱스 레인지 스캔
검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식입니다.
루트노드부터 비교를 시작해 리프 노드에 도달하고, 필요한 레코드의 시작점을 찾습니다.
시작할 위치를 찾으면 리프 노트의 레코드만 순서대로 읽으면 됩니다.
스캔을 멈춰야 할 위치에 다다르면 레코드를 사용자에게 반환하고 쿼리를 끝냅니다.
위 예시는 인덱스만을 읽지만 리프 노드를 스캔하면서 실제 데이터 레코드를 읽을 때도 있습니다.
같은 방식으로 스캔 시작 위치를 정하고, 그 지점부터 필요한 방향(오름차순 혹은 내림차순)으로 레코드를 읽어옵니다.
어떤 방식으로 스캔하든 상관없이, 인덱스 자체의 정렬 특성 덕에 정순, 혹은 역순 정렬된 상태로 레코드를 가져옵니다.
중요한 것은 인덱스의 리프 노드에서 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요합니다.
이때 리프 노드에 저장된 레코드 주소로 데이터 파일의 레코드를 읽어오는데, 이 한 건 단위로 랜덤 I/O가 한 번씩일어납니다.
그래서 인덱스를 통해 데이터 레코드를 읽는 작업은 비용이 많이 드는 것입니다.
인덱스 레인지 스캔은 다음과 같이 크게 3단계를 거치는 것으로 정리 가능합니다.
- 인덱스에서 조건에 해당하는값이 저장된 위치를 찾는다
- 위치부터 필요한 만큼 인덱스를 차례로 읽는다
- 읽어들인 키와 레코드 주소를 이용해 레코드가 저장된 페이지를 가져오고, 최종 레코드를 읽어온다.
쿼리가 필요하는 데이터에 따라 3번은 필요하지 않을 수 있습니다. 이를 커버링 인덱스라고 합니다.
커버링 인덱스로 처리되는 쿼리는 디스크의 레코드를 읽지 않아도 되기 때문에, 랜덤 읽기가 상당히 줄어들고 성능은 그만큼 빨라집니다.
Mysql에서는 show status like 'Handler%' 명령어를 통해 1,2 번 단계의 작업이 얼마나 수행됐는지를 확인할 수 있습니다.
Handler_read_key 상태 값은 1번 단계가 실행된 횟수,
Handler_read_next와 Handler_read_prev는 2번 단계로 읽은 레코드 건수(앞은 정순 뒤는 역순)를 의미합니다.
Handler_read_first와 Handler_read_last는 인덱스의 첫 번째 레코드와 마지막 레코드를 읽은 횟수입니다. 이 둘은 min() max() 와 같이 제일 큰 값 또는 제일 작은 값만 읽는경우 증가하는 상태 값입니다.
인덱스 풀 스캔
인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라고 합니다.
쿼리의 조건절에 사용된 칼럼이, 인덱스의 첫 번째 칼럼이 아닌 경우 사용됩니다.
(인덱스가 a,b,c 칼럼의 순서로 걸려있지만, 쿼리 조건절은 b나 c로 검색하는 경우)
인덱스 풀 스캔은 인덱스에 포함된 칼럼만으로 쿼리를 처리할 수 있는 경우, 테이블의 레코드를 읽을 필요가 없습니다. 세컨더리 인덱스에 포함된 키 값만 가져오면 되기 때문입니다(굳이 PK 인덱스 루트로 갈 필요 없음).
이 방식은 인덱스 레인지 스캔보다는 빠르지 않지만, 테이블 풀 스캔보다는 효율적입니다.
인덱스의 전체 크기는 테이블보다는 작으므로 테이블 전체를 읽는 것 보다는 적은 디스크 I/O가 일어나기 때문입니다.
루스 인덱스 스캔
인덱스 레인지 스캔과 비슷하지만 중간에 필요없는 인덱스 키 값은 무시하고 다음으로 넘어가는 형태입니다.
일반적으로 Group by 또는 집합 함수 가운데 Max() 또는 Min() 함수에 대해 최적화를 하는 경우 사용됩니다.
인덱스 스킵 스캔
만약 한 테이블에 컬럼 두개에 인덱스를 (a,b) 순서대로 건다면,
조건절에서 a,b를 모두 사용한다면 인덱스를 쓰지만, b만 쓰면 인덱스를 사용할 수 없습니다.
이 경우 b부터 사용하는 인덱스를 새로 걸어야만 했죠.
그러나 Mysql 8.0 버전부터는 b만으로도 인덱스 검색이 가능하게 해주는 인덱스 스킵 스캔 최적화 기능이 도입됐습니다.
AlTER TABLE employees ADD INDEX ix_gender_birthdate (gender, birth_date)
인덱스 스킵 스캔은 위와 같이 인덱스가 걸리는 상황에서, gender 없이 birth_date 칼럼만으로도 인덱스 검색이 가능합니다.
select gender, birth_date from employees where birth_date>='1965-02-01'
즉 위와 같은 쿼리를 실행할 때
위 사진에서 gender 컬럼은 두 값만 가지게 되므로,
select gender, birth_date from employees where gender='M' and birth_date>='1965-02-01'
select gender, birth_date from employees where gender='F' and birth_date>='1965-02-01'
옵티마이저가 내부적으로 위 두개의 쿼리를 실행하는 것과 비슷한 형태의 최적화를 합니다.
따라서 위 쿼리는 인덱스가 걸리는 쿼리이므로 검색 속도가 빠르겠죠?
그러나, 위처럼 인덱스의 선행 칼럼의 유니크한 값의 개수가 적고,
쿼리가 인덱스에 존재하는 칼럼만으로 처리 가능한 경우여야 합니다.
select * from employees where birth_date>='1965-02-01'
위와 같이 모든 칼럼을 필요로 하는 경우 인덱스 스킵 스캔을 사용하지 못합니다.
다중 칼럼 인덱스
두 개 이상의 칼럼으로 구성된 인덱스입니다.
그림의 리프 노드를 확인하면, 두 번째 칼럼은 첫 번째 칼럼에 의존해서 정렬돼 있는 것을 확인할 수 있습니다.
따라서 두 번째 칼럼의 정렬은 첫 번째 칼럼이 똑같은 레코드에서만 의미가 있습니다.
따라서 칼럼이 세개인 인덱스가 있다면 3번째 칼럼은 두 번째를 기준으로 정렬될 것입니다.
그러므로, 다중 칼럼 인덱스는 각 칼럼의 순서가 굉장히 중요합니다.
B-Tree 인덱스의 정렬 및 스캔 방향
인덱스의 키 값은 오름차순 혹은 내림차순으로 정렬되는데, 이를 어느 방향으로 읽을지는 옵티마이저의 실행계획에 따라 결정됩니다.
인덱스의 정렬
MySQL 5.7 까지는 정렬 순서를 혼합해서 쓸 수 없었지만, 8.0 부터는 아래와 같은 형태로 정렬 순서를 혼합해 쓸 수 있습니다.(ASC DESC 혼합)
CREATE INDEX ix_teamname_userscore ON employees (team_name ASC, user_score DESC)
인덱스 스캔 방향
옵티마이저는 필요한 인덱스가 존재하는 위치에 따라, 인덱스를 정순으로 읽거나, 역순으로 읽을 수 있습니다.
항상 정순으로 읽는다면 아래에 존재하는 인덱스를 읽을 때 처음부터 모두 읽어야 하므로,
SELECT * FROM employees ORDER BY first_name DESC LIMIT 5
와 같이 테이블에 first_name에 정의된 인덱스를 역순으로 읽으면서 처음 5개만 가져오면 됩니다.
이는 옵티마이저가 최적의 실행계획을 만들어 줍니다.
내림차순 인덱스
만약 2개 이상의 칼럼으로 구성된 복합 인덱스에서, 각각의 칼럼이 내림차순과 오름차순이 혼합된 경우 내림차순 인덱스로만 해결할 수 있습니다.
내림차순 인덱스는 큰 값의 인덱스 키가, B-Tree의 왼쪽으로 정렬된 인덱스입니다.
인덱스 리프 노드에 왼쪽부터 오른쪽으로 스캔하면 정순 스캔, 오른쪽에서 왼쪽으로 스캔하면 역순 스캔입니다.
그러나 인덱스 역순 스캔은 정순 스캔보다 느립니다.
이유는 페이지 잠금이 인덱스 정순 스캔에 적합하고, 페이지 내에서 인덱스 레코드의 연결이 단방향으로 이루어져있기 때문입니다.
B-Tree 인덱스의 가용성과 효율성
어떤 조건에서 인덱스를 사용할 수 있거나, 사용할 수 없을까요?
비교 조건의 종류와 효율성
다중 칼럼 인덱스에서 칼럼의 순서와, 칼럼에 사용된 조건이 동등비교(=) 인지, 크다(>), 작다(<) 비교인지에 따라 인덱스 칼럼의 활용 형태가 다릅니다.
select * from dept_emp where dept_no = 'd002' and emp_no >= 10114;
라는 쿼리를 실행할 때,
(dept_no, emp_no)순으로 인덱스가 걸린 경우 A 와 (emp_no, dept_no)경우 B가 있다고 가정하면,
다음과 같이 A는 먼저 d002이면서 10144 이상인 레코드를 찾은 뒤, 이미 세컨더리 인덱스가 정렬된 상태이므로 밑으로 쭉 읽다가 doo2가 아니면 멈추면 됩니다.
5건을 조회하기 위해 딱 필요한 5건만 읽었습니다.
그러나 B의 경우, 먼저 10144 이상이면서 d002인 레코드를 찾고, 쭉 내려가면서 모든 레코드에 대해 dept_no가 d002인지 확인하는 과정이 필요합니다. 총 7번을 읽었습니다.
A의 emp_no는 비교 작업을 좁히게 해줬지만, B의 dept_no는 비교 작업을 좁히는데 도움을 주지 못했습니다. 그냥 조건 검사용으로만 쓰였죠.
→ 이 부분 조금 더 공부 필요할듯
A의 두 조건처럼 작업 범위를 줄여주는 조건을 “작업 범위 결정 조건”이라 하고
B의 dept_no 처럼 조건 검사 역할만 하는 조건을 “필터링 조건” 혹은 “체크 조건”이라 합니다.
작업 범위 조건이 많으면 쿼리 성능을 높이지만, 체크 조건은 성능을 높이지 못하고 실행을 느리게 할 수도 있습니다.
인덱스의 가용성
B-Tree 인덱스는 왼쪽 값에 기준해서 오른쪽 값이 정렬돼 있습니다.
따라서 왼쪽 값을 기준으로 칼럼을 읽어야 합니다.
따라서 LIKE %something 과 같은 쿼리의 경우 왼쪽부터 비교할수 없으므로, 인덱스 효과를 얻을 수 없습니다.
또 위의 케이스 A처럼 (dept_no, emp_no)순으로 인덱스가 걸린 경우,
select * from dept_emp where emp_no >= 10114;
와 같은 쿼리를 실행했을 때 emp_no 는 dept_no를 기준으로 값이 정렬돼 있어, 인덱스를 효율적으로 사용할 수 없습니다. 조건에 선행 칼럼이 없기 때문입니다.
가용성과 효율성 판단
아래의 경우 인덱스를 사용할 수 없습니다.
- NOT-EQUAL로 비교
- LIKE %something 비교
- 스토어드 함수나 다른 연산자로 인덱스 칼럼 변형 후 비교
- NOT-DETERMINISTIC 속성의 스토어드 함수가 비교 조건에 사용
- 데이터 타입이 서로 다른 비교
- 문자열 데이터 타입이 콜레이션이 다른 경우
index ix_test (column_1, column_2, ..., column_N)
위 다중 칼럼 인덱스에서 아래의 경우는 다중 칼럼 인덱스 사용이 불가능합니다.
- column_1 에 대한 조건 없음
- column_1의 비교 조건의 위의 인덱스 사용 불가 조건 중 하나임
아래의 경우는 사용이 가능합니다
- column_i 칼럼에 대해 다음 연산자 중 하나로 비교
- 동등 비교(=, in)
- 크다 작다 형태(>,<)
- LIKE 좌측 일치
