인덱스: B-Tree

☁️ 인덱스 (index)

인덱스는 책의 맨 끝에 있는 찾아보기라고 많이 설명된다. 특정 데이터를 이 찾아보기(인덱스)를 통해 데이터의 주소로 바로 이동할 수 것이다. 인덱스는 인덱스의 칼럼과 해당 레코드가 저장된 주소를 키와 값 쌍으로 찾아보기 쉽게 정렬하여 저장한다. (InnoDB는 레코드 주소가 아닌 PK를 주소처럼 사용)

 

select 문장의 경우 인덱스를 통해 특정 레코드를 검색하는 것이 인덱스 없이 전체 테이블에서 레코드를 검색하는 방식보다 훨씬 빠를 것이다. 하지만 insert, update, delete 문장은 어떨까? 인덱스는 정렬되어 저장된다고 앞서 말했다. 레코드의 변경이 생기는 insert, update, delete 문장에 의해 인덱스와 연관이 있는 레코드에 변경이 생기는 경우 인덱스 또한 변경되어야 한다. 만약 여기서 인덱스가 아주 많은 테이블의 경우에는 인덱스가 없는 테이블보다 insert, update, delete의 성능이 더욱 나빠질 것이다.

 

따라서 인덱스를 많이 생성한다고 해서 성능이 무조건 좋아지는 것은 아니기에, 얼마나 자주 검색되는지 변경이 잦은지 등을 고려히여 인덱스를 생성해야 한다. MySQL의 InnoDB의 경우에는 레코드 락을 인덱스 기반으로 제공하기에 실제로 인덱스에 락이 걸린다는 것도 고려해야 하고, 인덱스는 버퍼 풀에 저장되기에 인덱스가 많으면 많을수록 버퍼 풀의 주 기능은 캐싱과 버퍼링에 영향을 끼쳐 성능에도 영향을 미칠 수 있음을 고려해야 한다.

 

인덱스는 대표적으로 B-tree 인덱스와 Hash 인덱스로 구분된다.

 

☁️ B-Tree 인덱스

B-Tree(Balanced-Tree, 비 마이너스 트리 아님)는 데이터베이스 인덱싱 알고리즘 가운데 가장 일반적으로 사용된다. 일반적으로 DBMS에서는 B+-Tree(비 플러스 마이너스 트리 아님), B*-Tree가 사용된다고 한다.

 

B-Tree는 바이너리 서치 트리와 유사한 구조를 가지는데, 키의 값이 1개 이상 올 수 있다는 특징이 있다. 여러 개의 키 값을 가지는 부모 노드의 자식 노드는 각각 부모 노드의 가장 왼쪽 키보다 작은 키, 부모 노드 키의 사이 값을 가지는 키, 부모 노드의 가장 오른쪽 키보다 큰 키로 구성된다.

 

https://www.programiz.com/dsa/b-tree

인덱스 키의 추가와 변경 작업은 트리의 구조에 영향을 끼치기에 탐색과 삭제 작업에 비해 상대적으로 비용이 많이 든다. InnoDB에서 인덱스 키가 프라이머리 키 혹은 유니크 키일 경우 추가, 삭제, 변경 작업은 중복 검증 과정을 거쳐야 하기에 바로 인덱스에 적용되지만 그렇지 않은 컬럼의 경우에는 작업을 체인지 버퍼를 통해 지연시켜 나중에 처리할 수 있다.

 

B-Tree 인덱스 사용에 영향을 미치는 요소

B-Tree 인덱스는 인덱스를 구성히는 컬럼의 크기와 레코드 건수, 유니크한 인덱스 키 값의 개수 등에 의해 검색이나 변경 작업의 성능이 영향을 받는다.

 

인덱스 키 값의 크기:

InnoDB 스토리지 엔진의 모든 읽기 쓰기 작업의 최소 단위는 페이지이다. 이는 버퍼 풀에서 데이터를 버퍼링하는 최소 단위이기도 하다. 인덱스도 이 페이지 단위로 관리된다.

 

MySQL의 B-Tree의 자식 노드 개수는 가변적이며 인덱스의 페이지 크기와 키 값의 크기에 따라 결정된다. InnoDB 페이지의 디폴트 값은 16KB(4 ~ 64KB 변경 가능)이다. 그리고 인덱스의 키는 대략 16바이트, 노드 주소는 12바이트라고 가정한다. 인덱스도 페이지 단위로 관리된다고 했다. 그럼 페이지 크기인 16KB에 인덱스의 키와 노드 주소를 담을 수 있는 수가 B-Tree 인덱스의 자식 노드 개수가 될 것이다.

인덱스의 키 값이 커지거나 페이지 크기가 작아지는 경우 더 적은 자식 노드를 저장할 수 있을 것이고, 반대인 경우에는 더 많은 자식 노드를 저장할 수 있을 것이다. 인덱스가 여러 개로 분리되어 있다면 작업에서 여러 인덱스를 읽어야 하는 상황이 빈번하게 발생할 것이다. 또한 인덱스가 커진다면 버퍼 풀의 메모리를 그만큼 차지하기에 성능이 떨어지는 결과를 가져올 것이다.

 

B-Tree의 Depth:

B-Tree 인덱스에서 인덱스 키 값의 크기가 크거나, 페이지 크기가 작아서 인덱스가 여러 노드로 분리되어야 하는 경우 트리의 깊이가 깊어진다. 이는 결국 여러 노드를 탐색해야 한다는 의미이기에 성능에 악영향을 끼칠 수 있다. 따라서 인덱스 키 값의 크기는 작은 것이 좋다.

 

선택도(기수성):

인덱스에서 하나의 키 값이 하나의 레코드를 가리키는 것, 이런 유니크한 인덱스 키가 많은 인덱스를 선택도가 높은 인덱스라고 하고, 반대로 하나의 키 값이 여러 레코드를 가리키는 비율이 높은 인덱스를 선택도가 낮다고 표현한다. (특정 컬럼에 인덱스를 걸었을 때, 인덱스 키가 중복된 레코드를 최소한으로 가리키는 것)

 

선택도가 높다면 단일 SELECT 작업에서 확실히 효율이 좋을 것이다. 하지만 그룹핑이나 정렬 작업을 고려하여 인덱스를 설정하는 경우도 있기에 무조건 선택도가 높은 인덱스가 성능이 좋다고 할 수는 없다. (전체 인덱스 키 값이 100개인데, 그 중 유니크한 값의 수가 10개라면 선택도는 10)

 

위와 같은 테이블이 존재한다고 가정하자. CASE A와 B에서 각각 country 컬럼에 인덱스를 생성했다고 생각해보자. 여기서 만약 아래와 같은 쿼리문이 실행된다면 각 인덱스의 성능은 어떨까? (A케이스 country 인덱스의 유니크 값은 1000개, B케이스는 10개이다.)

// country = 'korea' AND city = 'seoul' 인 레코드는 하나 밖에 없다고 가정한다.
SELECT FROM MEMBER WHERE country = 'korea' AND city = 'seoul';

먼저 A 케이스의 경우에는 country 인덱스를 통해 korea를 가지는 리프 노드의 레코드를 검색한다. 10건이 검색될 것이다. 10건 중 city가 seoul인 레코드를 검색하면 된다. 인덱스를 통한 리프 노드 탐색 후 레코드 검색을 10번 수행하면 원하는 레코드를 검색할 수 있다. 이제 B 케이스의 경우를 살펴보자. 인덱스를 통한 탐색 후 1000건의 레코드에서 city가 seoul인 레코드를 찾아야 한다. 즉, A케이스보다 성능이 떨어질 것이다.

 

이처럼 단일 선택 쿼리의 경우 인덱스의 선택도가 높은 경우가 유리하다.

 

 

읽어야 하는 레코드의 건수:

인덱스를 통해 레코드를 읽는 작업은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 작업보다 더 높은 비용이 든다. 단순하게 생각해서 인덱스를 거치는 작업이 필요하기 때문이다. 만약 테이블의 레코드가 100건이 있는 상황에서 50만건을 읽어오는 쿼리가 존재한다고 가정했을 때, 인덱스를 통해 읽는 것과 아닌 것 어떤 방식이 더 효율적일까?

일반적인 DBMS의 옵티마이저에서는 인덱스를 통해 레코드 1건을 읽는 것이 테이블에서 직접 레코드를 1건 읽는 작업보다 4~5배 정도 비용이 더 많은 드는 작업인 것으로 예측한다. - Real MySQL 8.0 1

 

이는 읽어야 하는 레코드가 전체 레코드의 20~25%를 넘어선다면 인덱스를 거치지 않는 풀 스캔이 효율적이라는 의미이다. 즉, 100만 건 중 50만 건을 읽어야 하는 작업에는 인덱스를 사용하지 않는 것이 효율적이다. 예외적으로읽어야 하는 레코드가 인덱스의 키 값 만으로 만족할 수 있다면 인덱스를 사용하는 경우도 존재한다.(인덱스 풀 스캔)

 

B-Tree 인덱스를 통한 데이터 읽기

우리가 인덱스를 선언했다고 해서 쿼리 실행 시 무조건 인덱스를 사용하는 것이 아니다. 모든 것은 옵티마이저의 판단아래 어떤 인덱스를 사용할 것인지, 사용하지 않고 풀 스캔할 것인지 결정된다. MySQL은 어떻게 인덱스를 사용하는지에 대한 대표적인 방법을 정리하고 넘어가려 한다.

 

인덱스 레인지 스캔:

인덱스 레인지 스캔은 데이터를 한 건 혹은 한 건 이상 읽는 경우, 검색해야 할 인덱스의 범위가 결정된 상황에 사용하는 방식이다. ~BETWEEN ~ AND ~ 과 같은 쿼리가 동작하는 경우 인덱스를 통해 범위의 시작 인덱스부터 B+-Tree의 특성에 따라 범위의 마지막 인덱스까지 순차 탐색한다.

 

사용자의 요청이 인덱스 키에 포함되어 있는 정보로만 만족할 수 있다면 좋겠지만(이러한 경우를 커버링 인덱스라고 한다), 인덱스 키에 포함되지 않는 레코드의 컬럼까지 검색해야 하는 경우 데이터 파일까지 진입하여 레코드를 읽어와야 한다. 인덱스 레인지 스캔은 인덱스가 정렬되어 저장된다는 특성 덕분에 빠른 작업이 가능하다.

 

유의해야 할 점은 인덱스에 포함되어 있지 않은 컬럼이 조건절에 들어가 있는 경우이다. 이러한 경우에는 인덱스를 통한 레인지 스캔이 불가능하다. 데이터 파일까지 진입하여 레코드를 읽어야 하는 작업이 추가적으로 존재하기에 이러한 경우 풀스캔을 하는 것이 더 효율적일 수 있다.

 

인덱스 풀 스캔:

인덱스 레인지 스캔과 동일한 상황에 인덱스의 처음부터 끝까지 모두 읽는 방식이다. 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우 인덱스 풀 스캔이 사용된다. 사용자의 데이터 요청이 인덱스의 키 값만으로 만족하는 경우에 해당 방식을 사용한다.

 

루스 인덱스 스캔:

인덱스를 통해 레코드를 듬성듬성 읽을 때 사용하는 방식이다. 일반적으로 GROUP BY 절 또는 집합 함수 중 MAX, MIN 처럼 최적화 하는 경우에 사용된다.

 

인덱스 스킵 스캔:

인덱스의 키가 여러 값을 가지는 경우에 인덱스는 메인 키를 기준으로 정렬 된 후 서브 키를 통해 정렬한다. 따라서 쿼리의 WHERE 절에 서브 키만 존재하는 경우 인덱스를 사용하기 힘들다. 하지만 MySQL 8.0 이후에는 인덱스 스킵 스캔이 도입되면서 위와 같은 상황에서도 인덱스를 사용할 수 있게 되었다.

메인 키를 기준으로 분류한 뒤 조건에 맞는 레코드를 검색하는 방식인데 해당 방식을 사용하기 위해서는 두 조건을 만족해야 한다. 커버링 인덱스일 것, WHERE절에 없는 메인 키 값의 유니크 수가 적을 것(메인 키 개수가 많지 않을 것).

 

다중 컬럼 인덱스 (Multi-column index)

두 개 이상의 컬럼을 통해 인덱스를 생성된 인덱스를 다중 컬럼 인덱스 혹은 Concatenated Index라고 한다. 다중 컬럼 인덱스는 첫 번째 키에 의해 먼저 정렬되고 두 번째 키는 첫 번째 키에 의존하여 정렬된다. 키가 많아져도 각 키는 자신보다 먼저 선언되어있는 키에 의존하여 정렬된다. 즉, 두 번째 키의 정렬은 첫 번째 키에 의해 분류된 레코드들 안에서만 유효하다는 것이다.

 

B-Tree 인덱스의 정렬과 스캔 방향

MySQL 8.0 이후 부터는 아래와 같이 인덱스의 정렬 방향을 지정해줄 수 있다.

CREATE INDEX ix_teamname_userscore ON employees (team_name ASC, user_score DESC);

물론 이렇게 방향을 지정해 주어도 옵티마이저가 판단하에 오름차순 혹은 내림차순으로 사용할지 결정된다.

사실 이렇게 방향을 선언해주지 않아도 오름차순 정렬된 인덱스를 처음부터 읽으면 오름차순, 마지막부터 읽으면 내림차순으로 정렬된 레코드를 읽을 수 있다. 이렇게 생각해보면 정렬된 인덱스에서 가장 큰 값과 가장 작은 값을 읽는 작업은 거의 동일한 성능으로 동작할 것 같지만 그렇지는 않다.

 

버퍼 풀에서 페이지 간의 연결은 양방향으로 이루어져 있다. 하지만 페이지 내에서의 레코드들은 단방향으로 연결되어 있다. 즉 오름차순으로 정렬된 인덱스를 역순으로 읽을 때, 페이지에 접근하는 것은 빠르지만 페이지 내부에 존재하는 레코드를 읽을 때는 시간이 조금 더 걸린다는 의미이다.

 

인덱스 사용 시 유의사항 (가용성과 효율성)

앞서 정리했던 내용을 다시 짚어 보며 어떤 상황에서 인덱스가 효율적으로 쓰일 수 있는지 정리해보려 한다.

 

커버링 인덱스:

일단 where 절의 조건이 인덱스에 포함되어 있고, 데이터 요청이 인덱스의 키 값만으로 커버되는 커버링 인덱스가 가장 이상적인 인덱스 사용방식이라고 생각한다. (데이터 파일에 접근하지 않고 데이터를 반환해줄 수 있기 때문)

 

내부 구조에 따른 오름차순, 내림차순 성능 차이:

앞서 설명했듯 페이지 간의 연결은 양방향이지만 페이지 내의 인덱스는 단방향으로 연결되어 있기에 오름차순 정렬된 인덱스를 역순으로 탐색하는 경우 성능에 차이가 발생할 수 있다. 내림차순으로 정렬하는 쿼리가 더 빈번하게 발생하는 테이블이라면 내림차순으로 인덱스를 선언하는 것이 효율적이다.

 

인덱스 키와 비교 조건의 관계:

SELECT * FROM dept_emp WHERE dept_no='d002' AND emp_no >= 10114;

// CASE A : INDEX(dept_no, emp_no)
// CASE B : INDEX(emp_no, depth_no)

위와 같은 상황에서 케이스 A와 B중 어떤 인덱스가 더 효울적일까? A케이스가 효율적일 것이다. dept_no='d002' AND emp_no = 10114를 찾고 dept_no ≠ 002 일 때까지 순차적으로 탐색하면 되기 때문이다. 반대로 B 케이스는 emp_no 기준 값을 찾고 순차적으로 탐색하며 dept_no가 일치한지 비교한 뒤 일치하지 않으면 버리는 작업을 추가적으로 수행해야 하기 때문이다.

비교 조건:

문자열 키에 대해 아래와 같이 왼쪽 값이 고정되지 않은 작업은 인덱스를 활용할 수 없다.

SELECT * FROM employees WHERE first_name LIKE '%mer';

아래의 상황도 마찬가지이다.

SELECT * FROM dept_emp WHERE emp_no >= 10114;

// INDEX(dept_no, emp_no)

NOT-EQUAL로 비교된 경우("<>", "NOT IN", "NOT BETWEEN", "IS NOT NULL")에도 인덱스를 효율적으로 사용하지 못한다.

만약 아래와 같은 인덱스가 존재하는 경우

INDEX ix_test ( column_1, column_2, column_3, .., column_n )

작업 범위 결정 조건으로 인덱스를 사용하지 못하는 경우

• column_1 칼럼에 대한 조건이 없는 경우
• column_1 칼럼의 비교 조건이 위의 인덱스 사용 불가 조건 중 하나인 경우

작업 범위 결정 조건으로 인덱스를 사용하는 경우(i는 2보다 크고 n보다 작은 임의의 값을 의미)

• column_1 ~ column_(i-1) 칼럼까지 동등 비교 형태("=" 또는 "IN")로 비교
• column_i 칼럼에 대해 다음 연산자 중 하나로 비교
  • 동등 비교("=" 또는 "IN")
  • 크다 작다 형태(">" 또는 "<")
  • LIKE로 좌측 일치 패턴(LIKE '승환%')