일단 인덱스가 뭘까? 인덱스는 데이터베이스 쿼리의 성능을 언급하면서 빼놓을 수 없는 부분이다. 백엔드 개발자한테 중요한 개념이라고 생각한다. 각 인덱스의 특성과 차이는 상당히 중요하며, 데이터베이스 모델링을 할 때도 중요한 요소다. 이번 글에서는 B-Tree에 대해서 정리하고자 한다.
일단 인덱스에 관련된 설명을 위해서 디스크 읽기 방식에 대해 알아야한다.
디스크 읽기 방식
컴퓨터의 CPU나 메모리처럼 전기적 특성을 띤 장치는 매우 빠르게 발전했지만 데이터를 저장하는 디스크 같은 기계식 장치는 제한적으로 발전했다. 원판에 의존하는 하드 디스크보다 SSD 드라이브가 많이 활용되고 있지만, 여전히 컴퓨터에서 가장 느린 장치이다. 그래서 데이터베이스의 쿼리 성능은 튜닝을 통해 디스크 I/O를 줄이느냐가 관건이다.
컴퓨터에서 주요 장치는 대부분 전자장치지만 하드 디스크는 기계식 장치다. 그래서 데이터베이스에서 디스크는 병목이 된다. 이러한 하드 디스크를 대체하기 위해 전자식 저장 장치인 SSD가 등장했다. 같은 인터페이스를 지원하기 때문에 기존 장치에 그대로 사용할 수 있다. 또한 기존 하드 디스크에서 데이터 저장용 플래터를 제거하고 그 대신 플래시 메모리를 장착하고 있다. 그렇기에 기계적으로 회전시키지 않고 아주 빨리 데이터를 읽을 수 있다. 플래시 메모리는 전원이 공급되지 않아도 데이터가 삭제되지 않는다. 메모리보다는 느리지만 하드 디스크보다는 빠르다.
디스크의 헤더를 움직이지 않고 한 번에 많은 데이터를 순차적으로 읽는 순차 I/O는 SSD와 HDD가 비슷하다. 하지만 SSD는 랜덤 I/O가 훨씬 빠르다. 데이터베이스 서버는 랜덤 I/O를 통해 작은 데이터를 읽고 쓰는 작업이 대부분이다. 그래서 SSD는 DBMS용 스토리지에 최적이라고 볼 수 있다.
랜덤 I/O는 여러 번 쓰기, 읽기를 요청하기 때문에 작업 부하가 크다. 그래서 우리는 쿼리 튜닝을 통해서 랜덤 I/O를 줄이고 꼭 필요한 데이터만 읽도록 쿼리를 개선해야 한다.
인덱스 레인지 스캔 같은 경우, 주로 랜덤 I/O를 사용하고 풀 테이블 스캔은 순차 I/O를 사용한다. 테이블의 레코드를 대부분 읽는 작업에서는 풀 테이블 스캔을 사용하도록 유도할 때도 있다.
인덱스
인덱스는 책 끝에 있는 찾아보기에 많이 비유한다. 그렇다면 데이터 파일은 책의 내용이라고 볼 수 있다. DBMS에서 인덱스를 쓰는 이유는 필요한 데이터를 가져오기 위해 테이블의 모든 데이터를 검색해서 찾는다면 오래 걸린다. 그래서 칼럼의 값과 레코드가 저장된 주소를 key-value로 인덱스를 만들어 두는 것이다. 여기서 중요한 부분은 정렬이다. DBMS의 인덱스도 칼럼의 값을 주어진 순서대로 미리 정렬해서 보관한다.
정렬
자료구조에 SortedList와 ArrayList가 존재한다. DBMS는 SortedList, 데이터 파일은 ArrayList라고 보면 된다. 그래서 인덱스는 항상 정렬된 상태를 유지한다. 데이터 파일은 저장된 순서대로 별도의 정렬 없이 그대로 저장해둔다.
장단점을 살펴보자. 인덱스는 항상 값을 정렬해야 하므로 저장하는 과정이 복잡하고 느리지만, 이미 정렬돼 있어서 원하는 값을 아주 빨리 가져올 수 있다. 인덱스가 많은 테이블은 INSERT, UPDATE, DELETE 문장의 처리는 느려지지만. 정렬된 인덱스를 가지고 있어서 SELECT 문장은 빠른 처리가 가능하다. 결론적으로 읽기 성능을 높이고 나머지 기능의 성능을 희생한다.
테이블의 인덱스를 하나 더 추가할지 말지는 데이터의 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만들어야 하는냐에 따라 결정한다. SELECT 문장의 WHERE 조건절에 사용되는 컬럼이라고 해서 전부 인덱스로 생성하면 저장 성능이 떨어지고 인덱스의 크기만 커져서 역효과를 불러올 수 있다.
인덱스는 테이블을 관리하는 알고리즘과 중복 값의 허용 여부 등에 따라 여러 가지로 나눌 수 있다. 인덱스를 역할별로 구분해 본다면 Primary Key와 Secondary Key로 구분할 수 있다. Primary Key는 레코드를 대표하는 컬럼의 값으로 만들어진 인덱스다. NULL 값과 중복을 허용하지 않는다. Primary Key를 제외한 나머지 모든 인덱스는 세컨더리 인덱스로 분류한다.
데이터의 중복 허용 여부로 분류하면 유니크 인덱스와 유니크하지 않은 인덱스로 구분할 수 있다. 이것은 DBMS의 쿼리를 실행해야하는 옵티마이저에게는 상당히 중요한 문제가 된다. 유니크 인덱스에 대해 동등 조건으로 검색한다는 것은 항상 1건의 레코드만 찾으면 더 찾지 않아도 된다는 것을 옵티마이저에게 알려주는 효과를 낸다. 그뿐만 아니라 유니크 인덱스로 인한 MySQL에 처리 방식의 변화나 차이점이 상당히 많다.
B-Tree 인덱스
B-Tree는 인덱싱 알고리즘 가운데 가장 일반적으로 사용된다. 변형된 알고리즘이 있는데, 일반적으로 DBMS에서 B+-Tree 또는 B*-Tree가 사용된다. B-Tree는 Balanced-Tree라는 것을 주의하자. B-Tree는 칼럼의 원래 값을 변형시키지 않고 인덱스 구조체 내에서는 항상 정렬된 상태를 유지한다.
구조 및 특성
B-Tree는 트리 구조 최상위에 하나의 루트 노드가 존재하고 그 하위에 자식들이 붙어 있는 형태다. 가장 하위에 있는 리프 노드와 중간 노드인 브랜치 노드가 존재한다. 데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다.
인덱스의 키 값은 모두 정렬돼 있지만, 데이터 파일의 레코드는 정렬돼 있지 않다. INSERT된 순서대로 저장되어 있다고 생각하지만, 그것은 아니다. INSERT만 수행했다면 맞는 말이지만 레코드가 삭제되어 빈 공간이 생기면 그 다음 INSERT 동작은 빈 공간을 재활용하도록 DBMS는 설계되어 있기 때문에 항상 INSERT된 순서로 저장되는 것은 아니다.
InnoDB와 MyISAM 두 스토리지 엔진의 인덱스에서 가장 큰 차이점은 세컨더리 인덱스를 통해 데이터 파일의 레코드를 찾아가는 방법에 있다. MyISAM 테이블은 세컨더리 인덱스가 물리적인 주소를 가지는 반면 InnoDB 테이블은 프라이머리 키를 주소처럼 사용하기 때문에 논리적인 주소를 가진다고 볼 수 있다. 그래서 InnoDB 테이블에서 인덱스를 통해 레코드를 읽을 때는 데이터를 바로 찾아가지 못한다. 프라이머리 키 인덱스를 한 번 더 검색한 후, 프라이머리 키 인덱스의 리프 페이지에 저장돼 있는 레코드를 읽는다. 즉, 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해 프라이머리 키를 저장하고 있는 B-Tree를 다시 한 번 검색해야 한다. 성능이 떨어질 것 같지만 두 스토리지 엔진 구조는 장단점을 가지고 있다.
2. 인덱스 키 추가, 삭제, 변경, 검색
테이블의 레코드에 대한 작업을 하는 경우, 인덱스 키 추가나 삭제 작업이 발생한다.
이런 동작 방식을 파악하면 쿼리 개선에 도움이 될 것이기 때문에 함께 살펴보자.
2-1. 인덱스 키 추가
B-tree에 레코드가 추가 되면 새로운 키 값이 B-tree에 추가된다.
일단 B-tree상에서 적절한 위치를 탐색한다.
위치가 결정되면 리프 노드에 레코드 키 값과 레코드 주소 정보를 저장한다.
리프 노드가 꽉 찬 경우 리프 노드가 분리된다.
레코드를 추가하는 작업보다 키를 추가하는 작업에 비용이 더 많이 든다.
그 이유를 간단하게 생각해보면 레코드는 그냥 추가하지만 인덱스는 디스크로부터 페이지를 읽고 써야한다.
그런데 만약 리프 노드가 꽉 찬 경우, 노드의 분리가 필요하다.
연산 범위가 상위 브랜치 노드까지 넓어지기 때문에 인덱스 추가 비용은 많이 든다.
InnoDB 스토리지 엔진은 체인지 버퍼를 활용해 INSERT 작업을 지연 처리할 수 있다.
하지만 기본 키나 유니크 키 같은 경우는 B-Tree에 즉시 처리해야 한다.
2-2. 인덱스 키 삭제
B-tree 인덱스 키 삭제는 간단하다.
해당 키 값이 저장된 리프 노드를 찾아서 삭제 마크만 하면 작업이 끝난다.
InnoDB에서 키 삭제도 지연 처리가 가능하다.
마킹 작업도 디스크 쓰기 작업이라 디스크 I/O가 필요한 작업이다.
2-3. 인덱스 키 변경
인덱스 키 값이 변경되는 경우에 단순히 인덱스 상의 키 값만 변경하는 것은 불가능하다.
B-Tree에서 키 값 변경 작업은 아래와 같이 처리 된다.
- 기존 인덱스 키 값을 삭제한다.
- 새로운 인덱스 키 값을 추가한다.
키를 추가하고 삭제하는 작업이기 때문에 역시 지연 처리가 가능하다.
2-4. 인덱스 키 검색
인덱스 관리에 추가 비용을 감당하면서 구축하는 이유는 바로 빠른 검색때문이다.
B-Tree의 인덱스 검색은 트리 탐색을 통해 이루어진다.
트리 탐색: 루트 노드 -> 브랜치 노드 -> 리프 노드
그리고 SELECT 문장에서만 사용되지 않고 삭제, 변경 작업에도 검색 작업을 한다.
키 검색의 주의사항은 아래와 같다.
- B-Tree 인덱스 검색은 값이 완전히 일치하거나, 값의 앞부분(왼쪽)이 일치할 때만 사용할 수 있다.
- 키 값의 변형이 가해진 후(함수나 연산) 검색하면 빠른 검색 기능을 사용할 수 없다.
B-Tree 인덱스를 사용할 때 영향을 미치는 요소들
1. 키 값의 크기
인덱스를 구성하는 키 값의 크기가 커지면 디스크 I/O가 증가하고, 그만큼 느려진다.
2. B-Tree 깊이
인덱스의 깊이는 중요하지만 직접 제어할 방법은 없다.
키 값의 평균 크기가 늘어나면 페이지가 담을 수 있는 키의 개수가 적어진다.
자연스럽게 깊이가 늘어나고 디스크 I/O는 증가한다.
3. 선택성(기수성)
모든 인덱스 키 값 가운데 유니크한 값의 수를 의미한다.
키 값이 100개인데, 유니크한 값이 10개라면 선택성은 10이다.
유니크한 키가 많으면 검색 대상이 줄어서 쿼리에 효율적이다.
4. 읽어야 하는 레코드 수
DBMS의 옵티마이저에서는 인덱스로 레코드를 읽는 것이 직접 읽는 것보다 4~5배 정도 비용이 비싸다.
그렇기 때문에 읽어야 할 레코드 수가 20~25% 이상이라면 직접 테이블을 읽는 것이 좋다.
3. B-Tree 인덱스를 통한 데이터 읽기
쿼리 튜닝을 하기 위해서는 어떻게 인덱스를 이용해서 실제 레코드를 읽어내는지 알아야 한다.
MySQL이 인덱스를 이용하는 방법들을 살펴보자.
3-1. 인덱스 레인지 스캔
살펴볼 인덱스의 접근 방법 가운데 가장 빠른 방법이다.
아래와 같이 사용한다.
SELECT * FROM employees WHERE last_name BETWEEN 'Kim' AND 'Park';
- 인덱스에서 조건에 만족하는 값이 저장된 위치를 찾는다. (인덱스 탐색 과정)
- 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 읽는다. (인덱스 스캔 과정)
- 2번에서 읽어 들인 키와 레코드 주소를 이용해서 레코드가 저장된 페이지를 가져오고 최종 레코드를 읽어온다.
인덱스 스캔은 어떤 방식으로 스캔하든 상관 없이, 인덱스 자체의 정렬 특성 때문에 정렬된 레코드를 가져온다.
레코드 주소로 데이터 파일의 레코드를 읽어올 때, 각 레코드마다 랜덤 I/O가 일어난다.
인덱스 검색에서 말한 것처럼 20~25% 이상의 레코드를 읽는다면 인덱스 풀 스캔이 더 효율적일 것이다.
3-2. 인덱스 풀 스캔
인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라고 한다.
대표적으로 쿼리의 조건절에 첫 번째 컬럼이 아닌 경우 인덱스 풀 스캔 방식이 사용된다.
인덱스는 (A, B, C) 칼럼의 순서로 만들어져 있다면 쿼리의 조건절은 B나 C로 검색하는 경우다.
테이블의 크기보다 인덱스의 크기가 더 작기 때문에 인덱스 레인지 스캔보다는 느리지만 테이블 풀 스캔보다 효율적이다.
인덱스에 명시된 칼럼으로 처리가 가능하다면 이 방식을 사용한다.
하지만 레코드까지 모두 읽어야 한다면 이 방식으로 처리되지 않는다.
- 인덱스 리프 노드의 제일 앞 또는 뒤로 이동한다.
- 리프 노드를 연결하는 링크를 따라서 처음부터 끝까지 스캔한다.
테이블 전체를 읽는 것보다 적은 디스크 I/O로 처리가 가능하다.
3-3. 루스 인덱스 스캔
앞서 설명한 인덱스 레인지 스캔과 풀 스캔은 타이트 인덱스 스캔이라고 분류할 수 있다.
루스 인덱스 스캔은 느슨하게, 듬성듬성하게 인덱스를 읽는 것을 의미한다.
즉 중간에 필요치 않은 인덱스는 무시하고 넘어간다.
Group By나 집합 합수 가운데 MAX(), MIN() 함수에 대해 최적화를 하는 경우 사용한다.
SELECT dept_no, MIN(emp_no)
FROM dept_emp
WHERE dept_no BETWEEN 'd002' AND 'd004'
GROUP BY dept_no- 인덱스 리프 노드로 이동한다.
- dep_no이 d002와 d004 사이에 있는 그룹별로 첫 번째 레코드의 emp_no만 읽는다.
위 그림 처럼 3개의 레코드만 읽은 것을 확인할 수 있다.
3-4. 인덱스 스킵 스캔
-- gender, birth_date 인덱스 생성
ALTER TABLE employees ADD INDEX ix_gender_birthdate (gender, birth_date);
SELECT * FROM employees WHERE birth_date >= '1965-02-01';
SELECT * FROM employees WHERE gender = 'M' AND birth_date >= '1965-02-01';두 번째 문장은 gender가 M이고 생년월일이 1965-02-01 이후인 employees를 조회한다.
그렇다면 WHERE절에 생년월일 조건만 있는 첫 번째 문장은 어떻게 동작할까 ?
gender는 'M', 'F' 두 가지의 값을 가지는 Enum 타입이기 때문에 첫 번째 문장은 아래와 같은 결과를 가져온다.
SELECT gender, birt_date FROM employees WHERE gender='M' AND birth_date>='1965-02-01';
SELECT gender, birt_date FROM employees WHERE gender='F' AND birth_date>='1965-02-01';하지만 단점도 존재하다
- WHERE 조건 절에 없는 인덱스 칼럼은 유니크한 값의 수가 적어야 한다.
- 쿼리가 인덱스에 존재하는 칼럼만으로 처리가 가능해야 한다. (커버링 인덱스)
조건절에 명시하지 않은 인덱스의 유니크한 값의 수가 많다면 검색하는 작업이 많아지기 때문에 쿼리의 성능 저하가 우려된다.
SELECT * FROM employees WHERE birth_date>='1965-02-01'
기존 문장에서 employees 테이블의 모든 칼럼을 조회하도록 변경했다.
gender, birth_date 이외의 칼럼은 인덱스가 존재하지 않기 때문에 해당 쿼리에 응답하기 위해서 풀 테이블 스캔을 한다.
하지만 이 제약 사항은 MySQL 서버의 옵티마이저가 개선되면 해결될 수 있는 부분이다.
4. 다중 칼럼 인덱스와 인덱스 스캔 방향
4-1. 다중 칼럼 인덱스
두 개 이상의 칼럼으로 구성된 인덱스를 다중 칼럼 인덱스라고 한다.
실제로 데이터 레코드 건수가 적은 경우, 브랜치 노드가 생략될 수 있다.
위 그림에서 인덱스 두 번째 칼람은 첫 번째 칼럼에 의존해서 정렬된다.
다중 칼럼 인덱스에서는 인덱스 내에서 각 칼럼의 위치에 따라 정렬이 달라지기 때문에 중요하다.
4-2. B-Tree 인덱스의 정렬 및 스캔 방향
MySQL 8.0부터는 다음과 같이 정렬을 혼합한 인덱스 생성이 가능하다.
CREATE INDEX ix_teamname_userscore ON employees (team_name ASC, user_score DESC)ix_teamname_userscore는 다중 칼럼 인덱스다.
team_name은 오름차순으로 정렬하고 각 team_name 안에 user_score는 내림차순으로 정렬한다.
SELECT * FROM employees ORDER BY first_name DESC LIMIT 1;first_name 인덱스가 오름차순으로 정렬돼 있지만 인덱스를 최솟값부터 읽으면 오름차순으로 값을 가져온다.
반대로 최댓값부터 거꾸로 읽으면 내림차순으로 값을 가져올 수 있다.
이 사실을 MySQL 옵티마이저는 알고있다.
SELECT * FROM t1 ORDER BY tid ASC LIMIT 12619775,1; -- 4.15 sec
SELECT * FROM t1 ORDER BY tid DESC LIMIT 12619775,1; -- 5.35 sec역순 정렬 쿼리가 정순 정렬 쿼리보다 시간이 더 걸리는 것을 확인할 수 있다.
- 페이지 잠금이 인덱스 정순 스캔에 적합한 구조
- 페이지 내에서 인덱스 레코드가 단방향으로만 연결된다. 즉, 양방향이 아니기 때문에 반대로 읽으면 느리다.
이런 이유때문에 인덱스 역순 스캔이 정순 스캔에 비해 느릴 수밖에 없다.
SELECT * FROM tab WHERE userid=? ORDER BY score DESC LIMIT 10; -- 역순, 소량ORDER BY ... DESC하는 쿼리가 소량의 레코드에 실행되는 경우라면 내림차순 인덱스를 고려할 필요는 없다.
오름차순 인덱스 : INDEX (userid ASC, score ASC)
내림차순 인덱스 : INDEX (userid DESC, score DESC)
하지만 위 쿼리가 많은 레코드를 조회하면서 자주 실행된다면 내림차순 인덱스가 더 효율적이다.
즉, 자주 사용되는 정렬 순서대로 인덱스를 생성하는 것이 잠금 병목 현상을 완화하는데 도움이 된다.
5. B-Tree 인덱스의 가용성과 효율성
5-1. 비교 조건의 종류와 효율성
SELECT * FROM dept_emp
WHERE dept_no='d002' AND emp_no >= 10114;케이스 A : INDEX (dept_no, emp_no)
케이스 B : INDEX (emp_no, dept_no)
두 가지 인덱스 케이스에 대해 쿼리가 어떤 동작을 하는지 확인해보자.
케이스 A 인덱스는 dept_no = 'd002' AND emp_no >= 10114인 레코드를 찾는다.
이후에 dept_no가 'd002'가 아닐 때까지 읽기만 하면 된다.
케이스 B 인덱스는 emp_no >= 10114 AND dept_no = 'd002'인 레코드를 찾는다.
이후 모든 레코드에 대해 dept_no가 'd002'인지 비교하는 과정을 거친다.
인덱스를 통해 읽은 레코드가 나머지 조건에 맞는지 비교하는 작업을 필터링이라고 한다.
케이스 A 인덱스에서의 두 조건과 같이 작업의 범위를 결정하는 조건을 작업 범위 결정 조건이라고 한다.
케이스 B의 dept_no 인덱스는 작업 범위를 줄이지 못하는 조건을 필터링 조건 또는 체크 조건이라고 한다.
작업 범위 결정 조건은 쿼리의 성능을 높이지만 필터링 조건은 많다고 해서 쿼리의 성능을 높이지 못한다.
5-2. 인덱스의 가용성
SELECT * FROM employees WHERE first_name LIKE '%mer';이 쿼리는 레인지 스캔 방식으로 인덱스를 사용할 수 없다.
first_name 칼럼에 저장된 값의 왼쪽부터 한 글자씩 비교하면서 레코드를 찾아야 한다.
B-Tree는 왼쪽 값에 기준해서 오른쪽 값이 정렬돼 있기 때문에 인덱스의 효과를 얻을 수 없다.
SELECT * FROM dept_emp WHERE emp_no>=10144;인덱스가 (dept_no, emp_no) 칼럼 순서대로 있다.
선행 컬럼 dept_no 없이 검색하면 인덱스를 효율적으로 사용할 수 없다.
dept_no 칼럼에 대해 먼저 정렬한 후, emp_no 칼럼값으로 정렬돼 있기 때문이다.
'데이터베이스' 카테고리의 다른 글
| RTR 방식과 Refresh Token을 Redis에 저장하는 이유 (0) | 2024.10.14 |
|---|---|
| [MySQL] Order By, Group By, Distinct (2) | 2024.01.30 |
| [MySQL] 전문 검색, 클러스터링, 유니크 인덱스 (1) | 2024.01.23 |
| [MySQL] 트랜잭션, 잠금, 격리 수준이 뭘까 ? (1) | 2024.01.08 |
