B-tree와 인덱스 (feat. mysql)

B-tree (Balaced tree)

---

 

 

Mysql DB는 인덱스 및 실제 데이터를 B-tree 알고리즘을 통해 관리한다. 

각 노드는 하나의 페이지 형태로 여러 레코드 정보를 갖고 있다.

페이지의 크기가 정해져 있기에 인덱스 키 값의 크기에 따라 저장할 수 있는 레코드 수가 달라진다.

클러스터드 인덱스는 데이터 파일의 물리적 저장 방식을 결정하기에 리프 노드에 모든 칼럼 정보가 저장되며,

세컨더리 인덱스의 경우 데이터의 주소로 클러스터드 인덱스 키값을 사용한다.

따라서 세컨더리 인덱스로 조회하는 경우 클러스터드 인덱스를 한번 더 거쳐 조회되는 특징이 있다.

세컨더리 인덱스 리프 노드에 데이터 주소가 아닌 pk 값을 할당하는 이유?

데이터 주소를 사용하게 되면 데이터 변경, 이관, 분리와 같은 상황에서 이를 사용하는 모든 인덱스에서 리프 노드의 주소를 바꿔줘야하는 추가 작업이 발생한다.
pk 값을 사용하므로써 추가 작업에 대한 오버헤드를 줄이고 단순하게 관리할 수 있다.

 

B-tree 인덱스 키 추가 및 삭제

레코드 변경 작업시 인덱스의 변경 작업도 함께 발생하기에 인덱스가 존재하지 않는 경우보다 성능이 느려진다.

 

1. insert 작업 비용

레코드가 insert 될 때, B-tree 구조에도 노드가 추가되고 B-tree 구조를 유지해야한다.

리프노드가 꽉차서 더는 저장할 수 없을 때 리프노드가 분리되는데 이는 상위 노드의 분리까지 일으키게 된다.

만약, 인덱스로 설정된 키가 유니크 제약 조건을 넣게 되면 중복 체크를 진행하기에 인덱스 레코드 잠금처리를 진행하게 된다.

이는 인덱스 변경을 뒤로 미루고 한번에 일괄처리하는 체인지 버퍼를 사용하지 못하고 즉시 디스크 반영을 요구하기에 유니크하지 않은 키보다 상대적으로 부하가 더 크다.

[참고] 유니크 칼럼을 반드시 UNIQUE INDEX로 생성할 필요는 없다.
UNIQUE INDEX는 변경 작업시 인덱스 페이지의 중복 체크를 진행하기에 부하가 더 크다.
만약, 애플리케이션 수준에서 중복 체크를 진행하기에 DB에서 중복 체크를 진행할 필요가 없다면 일반 세컨더리 인덱스로 생성하는 것이 변경 작업의 부하를 줄일 수 있기에 더욱 좋은 선택일 수 있다.

 

2. delete 작업 비용

삭제의 경우는 비교적 부하가 적다.

리프 노드를 삭제하고 마킹 하는 것으로 끝난다. 

이후 마킹된 리프 노드는 그대로 방치되어 나중에 insert 작업으로 추가되는 노드에 의해 재사용된다.

 

3. update 작업 비용

update작업은 실제 노드 삭제와 노드 추가로 이루어지게된다.

delete와 insert 시에 이뤄지는 작업이 각각 순서대로 수행되는 것이다.

따라서 delete와 insert보다 부하가 큰 작업이다.

 

4. select 작업 비용

인덱스의 주 사용 목적은 읽기 성능이다. 

B-tree 구조를 통해 탐색 횟수를 줄여 읽기 성능을 향상시킨다.

[참고] 인덱스는 동치 비교와 범위 조건, 앞글자 체크에서 사용할 수 있다.
앞글자를 제외하고, 뒷글자나(like ‘%a’), 중간 글자(like ‘%a%’) 조건으로는 사용할 수 없다.
문자열의 경우 사전순 오름차순이나 내림차순으로 정렬 되기 때문이다.

 

select 조회시 성능에 영향을 미치는 요소

---

1. 인덱스 키 값의 크기

B-tree의 각 노드는 페이지 형태로 이루어져있고 루트 노드와 브랜치 노드는 인덱스 키와 자식 노드 주소로 이루어져 있다.

페이지의 크기는 4KB~64KB로 시스템 변수를 통해 선택 가능한 값이며 기본값은 16KB이다.

이는 페이지에 저장시킬 수 있는 값이 한정적이라는 것을 의미한다.

인덱스 키 값이 크면 페이지에 저장할 수 있는 레코드 수가 줄어들 수 밖에 없으며 이는 B-tree 구조를 더욱 깊고 넓게 만들어 탐색 횟수를 늘릴 수 있다.

(참고, 아무리 데이터가 많아도 B-tree의 깊이가 최대 5를 넘는 경우는 흔치 않다고 한다.)

 

2. 선택도

선택도는 모든 값들 중 유니크한 값의 수를 의미한다.
예시를 들며 선택도에 따른 인덱스 성능을 비교하겠다.

인데스 키 값에 저장된 값이 1000개이고 유니크한 값이 10개인 것과 100개인 것이 있고 고르게 분포되어있다고 하자.

유니크 값이 10개인 경우,

하나의 값으로 조건 검색시 필터링 된 결과는 1000/10 = 100 으로 100 건이 조회될 것이다.

유니크한 값이 100개인 경우에는 

1000/100 = 10 으로 10건이 조회될 것이다.

유니크한 값이 많을수로 검색 대상이 줄어들어 빠르게 처리된다.

 

3. 손익 분기점

인덱스의 리프노드에는 pk 값이 저장되어있고 pk 기반 B-tree 탐색을 한번 더 수행한다.

1건의 읽기를 비교할 때, 인덱스를 통한 읽기가 테이블에 직접 접근하여 읽는 것보다 4~5배 정도 비용이 많이 든다.

즉, 인덱스 사용이 항상 읽기 성능 향상을 보장하는 것이 아니며 인덱스 조건을 통해 읽어들이는 결과가 4~5 배 절감되야 성능 개선을 할 수 있다는 것이다.

따라서 우리는 인덱스를 선택할 때, 값의 분포도가 최소 20~25% 미만인 값을 선택하도록 고려해야한다.

 

인덱스의 스캔 방식

---

 1. 인덱스 레인지 스캔

인덱스를 사용한 스캔 방식 중 가장 빠르며 우리가 가장 잘 알고 있는 대표적인 방식이다.

읽어야할 인덱스 키의 시작 위치를 찾아가 종료위치까지 순차적으로 읽어나가는 방식이다.

동치 비교의 경우 시작위치와 종료위치가 같기에 1번 읽고 끝난다.

스캔 이후 반환된 레코드 주소(pk 값)을 통해 다시 한번 pk 기반 탐색을 수행하게 된다.

 

2. 인덱스 풀 스캔

인덱스 풀 스캔은 인덱스의 첫번째 칼럼을 사용하지 못하여 인덱스를 활용하지 못하는 방식이다.

인덱스 페이지를 풀스캔하며 탐색하는 방식이다.

인덱스 페이지가 테이블 보다 크기가 작기 때문에 테이블 풀스캔에 비하면 빠르다.

만약, 인덱스 키만 조회한다면 테이블 탐색을 추가로 조회하지 않기에 성능이 빠를 수 있지만,

인덱스 키 외에 다른 칼럼을 조회한다면 테이블 탐색을 추가로 진행해야하기에 굉장히 비효율적이다.

 

3. 루스 인덱스 스캔

루스 인덱스 스캔은 인덱스 레인지 스캔과 비슷하지만 불필요한 레코드 읽기는 건너 뛰는 방식이다.

group by, min, max 시에 사용되는 방식이다.

select dept_no, MIN(emp_no) FROM dept_emp where dept_no BETWEEN ‘d002’ and ‘d004’ GROUP BY dept_no;

 

위 쿼리는 부서별 사원번호가 최소인 값을 출력하는 쿼리이다.

이 테이블이 (dept_no, emp_no)의 인덱스가 설정되어있다면

인덱스 페이지는 인덱스 키에 대해 순차적으로 정렬 되어 있으므로,

dept_no의 첫번째 레코드만 조회하면 사원번호 최소값을 읽어올 수 있기에 중간의 레코드들은 건너 뛰고

dept_no가 d002, d003, d004인 값의 첫번째값만 읽어들이는 방식으로 읽기 성능을 향상 시킬 수 있다.

 

4. 인덱스 스킵 스캔 (8.0 부터 지원)

인덱스 스킵 스캔은 인덱스 선행 칼럼을 조건절에서 사용하지 않는 인덱스 풀 스캔 상황이 발생했을 때, 내부적으로 선행칼럼 조건을 만들어서 쿼리를 수행해주는 방식이다.

 

예를 들어 (gener, birthdate)가 인덱스로 설정된 테이블에서 아래와 같이 선행 칼럼 조건을 제외한 쿼리를 수행할 때,

SELECT gener, birthdate FROM employees WHERE birthdate >= ‘1965-02-01’

 

아래와 같이 선행 칼럼 조건을 포함한 쿼리로 변경하여 수행하는 방식이다.

SELECT gener, birthdate FROM employees WHERE gender = ‘F’ and birthdate >= ‘1965-02-01’
SELECT gener, birthdate FROM employees WHERE gender = ‘M’ and birthdate >= ‘1965-02-01’

 

 

다만 이 방식은 선행 칼럼의 유니크 값이 적은 경우에만 성능 향상을 이룰 수 있다.

선행 칼럼의 유니크 값이 많다면 내부적으로 수행해야할 쿼리가 많아지기 때문에 오히려 느려질 수 있다.

 

[참고] 인덱스 키 외에 칼럼 값을 조회하게 되면 인덱스 풀스캔으로 조회하게 되는데 이부분은 옵티마이저의 개선으로 해결될 것으로 예상되는 부분이다.

 

인덱스 정렬

---

인덱스는 기본적으로 오름차순으로 정렬되지만, 내림차순 정렬 또한 사용 가능하며 mysql 8.0 부터는 다중 칼럼 인덱스에 대해 각각 정렬 순서를 달리하여 생성할 수 있다.

인덱스 생성시 정렬을 결정하지만 정렬 순서대로 읽는 것은 아니다. 

옵티마이저가 역순으로 읽는 것이 빠르다고 판단하면 역순으로 읽어나가며, 정순으로 읽는 것이 빠르다고 판단되면 정순으로 읽어나간다.

참고로 정렬 조건 없이 인덱스를 통해 검색하면 인덱스 정렬 조건으로 조회된다.

 

인덱스 정렬을 설명하는 이유는 내림차순 인덱스와 오름차순 인덱스의 성능이 다르다는 것을 말하기 위함이다.

인덱스 페이지 내 레코드들을 실제 순차적으로 저장되어있지 않다.

인덱스 페이지는 힙과 같은 공간으로 임의의 공간에 레코드를 배치하고 레코드는 오름차순으로 다음 레코드 주소를 참조하는 방식으로 연결되어 있다.

따라서 인덱스 페이지 내의 레코드들의 연결이 오름차순에 최적화되어있기에 오름차순 인덱스가 내림차순 인덱스에 비해 성능이 좋다.

가급적이면 오름차순 인덱스를 사용하는 것이 좋다.

 

내림차순 인덱스를 사용하는 것은 인덱스 키 값의 앞부분이 아닌 뒤부분만 읽어들이는 경우에는 유리할 수 있다.