•
인덱싱 알고리즘 가운데 가장 일반적으로 사용되고 가장 먼저 도입된 알고리즘으로 현재도 가장 범용적으로 사용되어지고 있는 인덱스 알고리즘이다.
•
여러가지 변형된 형태가 존재하는데 DBMS에서는 주로 B+Tree, B*Tree 등이 사용된다.
1. 구조 및 특성
•
트리 구조의 최상위에 하나의 루트 노드가 존재하고 그 하위에 자식 노드가 붙어 있는 형태, 트리 구조의 가장 하위에 있는 노드를 리프 노드, 루트 노드도 리프 노드도 아닌 중간 노드를 브랜치 노드라 한다.
•
데이터 베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다.
•
인덱스는 테이블의 키 칼럼만 가지고 있으므로 나머지 칼럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 함, 이를 위해 리프 노드는 데이터 파일에 저장된 레코드의 주소를 가진다.
•
InnoDB 테이블에서 인덱스를 통해 레코드를 읽을 때는 인덱스에 저장돼 있는 프라이머리 키 값을 이용해 프라이머리 키 인덱스를 한 번 더 검색한 후, 프라이머리 키 인덱스의 리프 페이지에 저장돼 있는 레코드를 읽는다.
2. B-Tree 인덱스 키 추가 및 삭제
1.
인덱스 키 추가
•
새로운 키 값이 B-Tree에 저장될 때, 테이블의 스토리지 엔진에 따라 새로운 키 값이 인덱스에 저장될 수도 안 될 수도 있음
•
리프노드가 꽉 찰 경우, 상위 브랜치 노드에 대한 재배치가 일어나야하기 때문에 INSERT나 UPDATE문장이 큰 영향이 있을 수 있음
•
InnoDB 엔진의 경우, 프라이머리 키나 유니크 인덱스의 경우 중복 체크가 필요하므로 즉시 인덱스에 추가됨, 나머지는 지연 처리
2.
인덱스 키 삭제
•
상당히 간단한데, 해당 키 값이 저장된 리프 노드를 찾아 그냥 삭제만 하면 작업이 완료된다.
•
InnoDB 엔진의 경우, 지연 처리된다.
3.
인덱스 키 변경
•
인덱스 상 키 값만 변경하는 것은 불가능, 먼저 키 값을 삭제한 후, 새로운 키 값을 추가하는 형태로 변경된다.
•
InnoDB 엔진의 경우, 체인지 버퍼를 활용해 이 작업들을 지연 처리한다.
4.
인덱스 키 검색
•
100% 일치하는 값이나 앞부분만 일치하는 경우에 사용할 수 있다.
•
키 값을 변경한 후, 조회하는 경우, 인덱스가 사용되지 않으므로 주의할 것
3. B-Tree 인덱스 사용에 영향을 미치는 요소
1.
인덱스 키 값의 크기
•
InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 기본 단위를 페이지 또는 블록으로 규정, 디스크의 모든 읽기 및 쓰기 작업의 최소 단위
•
일반적으로 B-Tree의 자식 노드의 개수는 가변적인 구조로 2개로 제한되어 있지 않다.
•
즉 키 값의 길이가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고 그만큼 느려진다는 것을 염두에 두어야 함
2.
B-Tree 깊이
•
깊이는 매우 중요한 요소지만 직접 제어할 수 있는 방법이 없다.
•
가능한 작게 만드는 것이 좋으며 아무리 대용량 데이터베이스라 하더라도 깊이가 5단계 이상 깊어지는 경우는 흔하지 않음
3.
선택도
: 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미, 전체 인덱스 키 값이 100일 때 유니크한 값이 10이면 기수성은 10
: 중복된 값이 많아지면 많아질 수록 선택도와 기수성이 낮아진다. 인덱스는 선택도가 높을수록 검색 대상이 줄어드므로 그만큼 빠르게 처리됨
: 유니크한 인덱스 값의 개수는 인덱스나 쿼리의 효율성에 큰 영향을 미침
4.
읽어야 하는 레코드의 건수
: 인덱스를 통해 테이블의 레코드를 읽는 것은 일반적으로 바로 테이블의 레코드를 읽는 것보다 높은 비용이 드는 작업
4. B-Tree 인덱스를 통한 데이터 읽기
•
어떤 경우에 인덱스를 사용하게 유도할지, 또는 사용하지 못하게 할지 판단하려면 MySQL이 어떻게 인덱스를 이용해서 실제 레코드를 읽는지 알아야 한다.
1.
인덱스 레인지 스캔
•
인덱스를 통해 레코드를 한 건만 읽는 경우와 한 건 이상을 읽는 경우를 각각 다른 이름으로 구분하지만 여기선 묶어서 인덱스 레인지 스캔으로 표현
•
인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정되었을 때 사용하는 방식, 루트와 브랜치 노드를 통해 스캔을 시작할 지점을 찾고 리프 노드에서 연속 스캔
•
이때 리프 노드에 저장된 레코드 주소로 데이터 파일의 레코드를 읽어오므로 3건의 데이터가 검색 조건에 일치할 경우, 랜덤 I/O가 3번 발생한다는 것
1.
인덱스에서 조건이 만족하는 값이 저장된 위치를 찾는다.
2.
1번에서 탐색된 위치부터 필요한 만큼 인덱스를 쭉 읽는다.
3.
2번에서 읽어 들인 인덱스 키와 레코드 주소를 이용해 레코드가 저장된 페이지를 가져오고 최종 레코드를 읽어 옴
2.
인덱스 풀 스캔
•
인덱스를 사용하지만 인덱스 레인지 스캔과는 다르게 인덱스의 처음부터 끝까지 모두 읽는 방식이다.
◦
대표적으로 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 번째 칼럼이 아닌 경우가 있다.
•
리프 노드의 제일 앞 또는 뒤로 이동한 후, 인덱스의 리프 노드간 연결되는 링크드 리스트를 따라서 처음부터 끝까지 스캔하는 방식이다.
•
이는 인덱스 레인지 스캔보단 빠르지 않지만 테이블 풀 스캔보단 효율적이다.
3.
루스 인덱스 스캔
•
오라클과 같은 DBMS의 인덱스 스킵 스캔이라고 하는 기능과 작동 방식이 비슷한 스캔, 앞에서 소개한 인덱스 스캔 방식을 타이트 인덱스 스캔으로 분류하기도 한다.
•
인덱스 레인지 스캔과 비슷하게 작동하지만 중간에 필요치 않은 인덱스 키 값은 무시하고 다음으로 넘어가는 형태로 처리, 일반적으로 GROUP BY 또는 MAX(), MIN()에 대해 최적화를 하는 경우에 사용한다.
SELECT dept_no, MIN(emp_no)
FROM dept_emp
WHERE dep_no BETWEEN 'd002' AND 'd004'
GROUP BY dept_no;
SQL
복사
⇒ dept_no와 emp_no에 인덱스가 생성되어 있을 때, MIN으로 인해 굳이 dep_no 인덱스를 모두 읽을 필요 없이 하나만 읽으면 된다.
4.
인덱스 스킵 스캔
•
인덱스의 핵심은 값이 정렬되어 있다는 것이며 이로 인해 인덱스를 구성하는 칼럼의 순서가 매우 중요하다.
ALTER TABLE employees
ADD INDEX ix_gender_birthdate (gender, birth_date);
SQL
복사
•
이 인덱스를 사용하려면 WHERE 조건절에 gender 칼럼에 대한 비교 조건이 필수다.
-- // 인덱스를 사용하지 못하는 쿼리
SELECT * FROM employees WHERE birth_date >= '1965-02-01';
-- // 인덱스를 사용할 수 있는 쿼리
SELECT * FROM employees WHERE gender='M' AND birth_date >= '1965-02-01';
SQL
복사
•
복합 인덱스가 걸려있으므로 gender 칼럼과 birth_date 칼럼의 조건을 모두 가진 두 번째 쿼리는 인덱스를 효율적으로 사용하지만 gender 칼럼에 대한 비교 조건이 없는 첫 번째 쿼리는 인덱스를 사용할 수가 없으므로, 첫 번째 쿼리가 인덱스를 타게하려면 birth_date에 대한 인덱스를 생성해야 한다.
•
8.0부터는 gender 칼럼을 건너뛰어서 birth_date 칼럼만으로도 인덱스 검색이 가능하게 해주는 인덱스 스킵 스캔 최적화 기능이 도입되었다.
EXPLAIN
SELECT gender, birth_date
FROM employees
WHERE birth_date >= '1965-02-01';
SQL
복사
•
인덱스 스킵 스캔 기능을 비활성화했을 때, 실행계획
id | table | type | key | Extra |
1 | employees | index | ix_gender_birthdate | Using where; Using index |
◦
위의 쿼리는 WHERE 조건절에 gender 칼럼에 대한 조건 없이 birth_date 칼럼의 비교 조건만 가지고 있으므로 효율적으로 ix_gender_birthdate 인덱스를 사용할 수 없음
◦
type 칼럼이 index로 표시된 것은 인덱스를 처음부터 모두 읽었다는 의미로 인덱스를 비효율적으로 사용한 것
•
인덱스 스킵 스캔 기능을 활성화했을 때, 실행계획
id | table | type | key | Extra |
1 | employees | range | ix_gender_birthdate | Using where; Using index for skip scan |
◦
type 칼럼이 range로 표시됐는데, 이는 인덱스에서 꼭 필요한 부분만 읽었다는 것을 의미, 또한 Extra 칼럼에는 Using index for skip scan이라는 문구가 표시된다.
⇒ 이는 ix_gender_birthdate 인덱스에 대해 인덱스 스킵 스캔을 활용해 데이터를 조회했다는 것을 뜻한다.
◦
MySQL 옵티마이저는 우선 gender 칼럼에서 유니크한 값을 모두 조회해서 주어진 쿼리에 gender 칼럼의 조건을 추가하여 쿼리를 다시 실행하는 형태로 처리한다.
5. 다중 칼럼 인덱스
•
2개 이상의 칼럼을 포함하는 인덱스로 다중 칼럼 인덱스 또는 복합 칼럼 인덱스라고 한다.
•
인덱스의 두 번째 칼럼은 첫 번째 칼럼에 의존하여 정렬되어 있음, 즉 두 번째 칼럼의 정렬은 첫 번째 칼럼이 똑같은 레코드에서만 의미가 있다는 것
6. B-Tree 인덱스의 정렬 및 스캔 방향
•
인덱스는 오름차순 또는 내림차순으로 정렬되어 저장, 오름차순으로 저장되면 거꾸로 읽으면 내림차순으로 읽을 수 있음 이는 옵티마이저가 실시간으로 실행 계획을 세울 때 스캔 방향을 결정한다.
a.
인덱스의 정렬
•
일반 상용 DBMS에선 인덱스를 생성하는 시점에 칼럼의 정렬 방법을 설정하나 8.0부터는 정렬 순서를 혼합한 인덱스도 생성할 수 있게 되었음
⇒ mysql> CREATE INDEX ix_teamname_userscore ON employees (team_name ASC, user_score DESC);
i.
인덱스 스캔 방향
SELECT *
FROM employees
ORDER BY first_name DESC
LIMIT 1;
SQL
복사
•
이 쿼리의 경우, 인덱스의 스캔은 역순으로 접근해 첫 번째 레코드만 가져온다.
⇒ 옵티마이저는 인덱스가 오름차순으로 정렬되어 있다면 최솟값부터 읽으면 오름차순으로, 최댓값부터 읽으면 내림차순으로 가져올 수 있다는 것을 알고 있다.
•
즉 인덱스 생성 시점에 오름차순 또는 내림차순으로 정렬이 결저되지만 쿼리가 그 인덱스를 사용하는 시점에 인덱스를 읽는 방향에 따라 오름차순 또는 내림차순 정렬효과를 얻을 수 있다.
ii.
내림차순 인덱스
•
2개 이상의 칼럼으로 구성된 복합 인덱스에서 각각의 칼럼이 내림차순과 오름차순이 혼합된 경우 MySQL 8.0의 내림차순 인덱스로만 해결할 수 있다.
CREATE INDEX ix_firstname_asc ON employees (frist_name ASC );
CREATE INDEX ix_firstname_desc ON employees (frist_name DESC);
SQL
복사
7. B-Tree 인덱스의 가용성과 효율성
1.
비교 조건의 종류와 효율성
•
다중 칼럼 인덱스에서 비교 연산에 따라 인덱스 칼럼의 활용 형태가 달라지고 효율도 달라짐, 칼럼의 순서만 달라도, 처리되는 과정이 달라진다. 무엇을 먼저 비교하냐에 따라 효율이 변경된다.
•
필터링 인덱스를 통해 읽은 레코드가 나머지 조건에 맞는지 비교하면서 취사선택하는 것이다.
•
작업 범위를 결정하는 조건은 많으면 많을 수록 쿼리의 성능을 높인다.
2.
인덱스의 가용성
•
왼쪽값에 기준해서 오른쪽 값이 정렬되는게 특징으로 다중 칼럼 인덱스의 칼럼에 대해서도 함께 적용
3.
가용성과 효율성 판단
•
사용할 수 없는 조건에 대한 설명이다.
•
경우에 따라 체크 조건으로 인덱스를 사용할 수 있다.
•
NULL 값도 인덱스에 저장되기 떄문에, Where 조건도 작업범위 결정 조건으로 인덱스를 사용한다.
◦
다중 칼럼 작업 범위 결정 조건
▪
작업 범위 결정 조건으로 인덱스를 사용하지 못하는 경우
▪
작업 범위 결정 조건으로 인덱스를 사용하는 경우
