[데이터베이스] B- Tree와 인덱스의 이해

이 글은 아래 글을 읽으며 정리한 내용과, 추가로 궁금한 점을 정리한 글입니다.
https://mangkyu.tistory.com/286

[MySQL] B-Tree로 인덱스(Index)에 대해 쉽고 완벽하게 이해하기

 

 

B- Tree는 BinaryTree(자식이 2개인 트리)에서 개념을 확장해 n개의 자식을 가질 수 있도록 한 것이다.

DB에는 페이지라는 개념이 있는데, 페이지란 디스크와 메모리(버퍼풀)에 데이터를 읽고 쓰는 최소 단위이다. 인덱스와 PK, 테이블은 모두 페이지 단위로 관리된다.

페이지: 디스크와 메모리(버퍼풀)에 데이터를 읽고 쓰는 최소 단위

 

그렇기 때문에 페이지에 들어가는 데이터를 최대한 작게 하는 것이 중요하다. 만약 페이지에 저장되는 데이터 크기가 크다면 아래 2가지 문제점이 발생한다.

1. 페이지에 데이터가 조금밖에 못들어가기 때문에 여러 페이지를 읽어와야한다
   =>디스크 I/O 증가
2. 페이지의 크기가 커진다.
   =>메모리에 캐싱할 수 있는 페이지의 수 감소

DB의 성능을 개선하기 위해서는 디스크 I/O 자체를 줄이는 것이 핵심인 경우가 많다.

인덱스

인덱스는 페이지 단위로 저장되며, 인덱스 키를 바탕으로 항상 정렬된 상태를 유지한다. 그리고 그 키들을 따라 리프노드에 도달하면 (인덱스 키, PK) 쌍이 저장되어 있다. 즉 인덱스는 빠르게 인덱스키에 대응하는 PK값을 찾을 수 있도록 돕는 것이다. 이렇게 찾아낸 PK에 대응하는 레코드 값을 읽어오는 것이다. 그런데 인덱스를 통해 찾아낸 PK가 어떤 페이지에 저장되어 있는지는 알 수 없다. (인덱스는 테이블과 독립적으로 저장되어 있기 때문이다.) 그렇기 때문에 이때 랜덤 I/O가 발생한다.

 

즉 인덱스를 통해 데이터를 조회한다는 것은 인덱스를 통해 PK찾기-> 찾은 PK를 통한 레코드 조회를 한다는 것이다. 그렇기 때문에 인덱스를 통해 레코드를 조회하는 것은 하나의 레코드를 조회하는 것 보다 비용이 많이 든다. 그렇기에 읽어야 할 레코드의 건 수가 전체 테이블 레코드의 20~25%를 넘어가면 그냥 읽는 것이 더 효율적이며 이때는 옵티마이저가 인덱스를 안쓰고 처리한다.

DB별 옵티마이저는 이 부분을 어떻게 처리할까?

1. Oracle
Oracle의 옵티마이저는 일반적으로 읽어야 할 레코드가 전체 데이터의 5% 이하일 때 인덱스를 사용합니다. 5% 초과 시, 전체 테이블 스캔이 더 적합하다고 판단할 수 있습니다.

2. SQL Server
SQL Server의 경우, 옵티마이저가 대략 20% 이하의 레코드를 조회해야 할 경우 인덱스를 사용할 가능성이 높습니다. 20%를 초과할 경우, 테이블 스캔을 선택하여 성능을 최적화하는 경향이 있습니다.

3. MySQL
MySQL의 InnoDB 스토리지 엔진은 보통 10% 내외의 레코드를 조회해야 할 때 인덱스를 활용하는 경우가 많습니다.이 비율을 초과하면 MySQL은 전체 테이블 스캔을 선택하는 것이 더 효율적이라 판단할 수 있습니다.

4. PostgreSQL
PostgreSQL의 옵티마이저는 일반적으로 25% 이하의 레코드를 조회해야 할 경우 인덱스를 사용합니다.25%를 초과하면 전체 테이블 스캔으로 전환할 가능성이 높습니다.

5. MariaDB
MariaDB는 MySQL과 유사하기 때문에 대략 10% 내외의 레코드를 조회할 때 인덱스를 사용하는 경향이 있습니다.

결론
옵티마이저가 인덱스를 사용할지 여부는 데이터베이스의 특성과 쿼리의 복잡성에 크게 의존합니다. 전반적으로, 읽어야 할 레코드가 전체 테이블의 5%에서 25% 사이일 때 인덱스 사용이 고려되며, 이 비율을 초과하면 전체 테이블 스캔이 더 효율적일 수 있습니다.하지만 이 비율은 데이터베이스 내 저장된 데이터의 분포, 인덱스의 종류, 쿼리의 구조에 따라서 달라질 수 있으므로, 최적의 성능을 위해서는 실제 환경에서 테스트를 수행하는 것이 중요합니다. 각 DBMS의 통계 정보와 성능을 모니터링하여 필요한 경우 쿼리나 인덱스를 최적화할 수도 있습니다.

 

앞서 인덱스를 사용하는 것은 인덱스를 통한 PK조회 -> PK를 통한 레코드 조회라고 했는데, 인덱스랑 레코드의 주소를 매핑시키면 안되나?하는 의문을 가질수도 있다. 실제로 몇몇 데이터베이스는 이런 방식으로 매핑시킨다. 하지만 MySQL에서는 PK가 레코드의 물리적인 저장 위치를 결정하기 때문에 만일 PK가 바뀌면 데이터의 물리적인 저장 위치가 바뀐다. 그렇기 때문에 인덱스는 PK에 의존하는 것이다.

 

이렇게 인덱스는 PK에 매핑되어 있기 때문에 PK가 클수록 안좋다. PK값이 클수록 한 페이지에 담을 수 있는 인덱스 정보가 줄어들고 메모리도 비효율적으로 사용하게 된다. 페이지의 수가 증가하기 때문에 트리의 깊이도 지나치게 깊어진다.

 

인덱스에는 여러개의 컬럼으로 구성될 수 있는데, 여기에는 PK도 포함될 수 있다. 이를 다중 컬럼 인덱스(Multi Column Index)라고 한다. 만약 A, B, C를 묶어 인덱스를 만들면 B는 A에 의존하여, C는 B에 의존하여 정렬된다.

 

만약 emp_no, dept_no로 인덱스가 존재할 때, emp_no = 150이고 dept_no = D003인 값을 찾는것과, dept_no=D003이고 emp_no=150인 값을 찾는 것은 시간이 다를까?

DB 옵티마이저가 알아서 순서를 바꿔서 수행할 수도 있기는 하다. 그렇지만 순서를 바꿔서 인덱스를 타도록 한다는 보장이 없기 때문에 첫번째처럼 짜서 인덱스를 확실히 타도록 하는 것이 바람직하다.

 

그렇기에 인덱스에서는 컬럼의 순서가 매우 중요하다.

 

추가적으로 카디널리티(고유성)가 높은 컬럼에 인덱스를 거는 것도 중요하다. 하지만 카디널리티가 낮더라도 정렬이나 그루핑 등에 효율적으로 사용되는 경우도 고려해야한다. MySQL에서는 값이 1개만 존재하도록 하기 위해 유니크 인덱스를 만들어야 할 수도 있다. 유니크 인덱스는 무결성을 위한 중복 검사가 필요해 쓰기 성능이 낮아질 수도 있지만 1번만 읽어도 되니 읽기 성능은 올라간다.

 

유니크 인덱스란?

유니크 인덱스는 해당 컬럼이 유니크하다고 마킹해두는 것. 실제로 컬럼에 unique옵션을 걸어도 내부적으로는 unique인덱스를 생성하여 처리한다.

카디널리티가 낮아도 인덱스를 거는 사례는 그루핑, count등에 효율적으로 쓰이기 때문이다. 예를 들어서 SELECT dept_id, COUNT(*) FROM employees GROUP BY dept_id 쿼리에서 dept_id에 인덱스가 설정되어있다면 테이블 풀 스캔을 하는 것이 아니라 인덱스, pk쌍을 저장한 값만 스캔하기 때문에 훨씬 빠르게 스캔할 수 있다.

인덱스의 정렬과 스캔 방향

인덱스를 생성할 때 데이터의 정렬 순서를 설정할 수 있다. 인덱스를 오름차순 정렬하고 역순으로 읽을 수 있고 반대의 경우도 가능하다. 읽는 방법은 그때그때 옵티마이저가 효율적이라고 생각하는 순서로 읽는데, 예를 들어 역순으로 정렬해서 읽는 쿼리가 실행되면 옵티마이저는 역순으로 접근해 레코드를 읽어올 것이다. 인덱스를 읽는 방향에 따라 인덱스 정순 스캔(Index Forward Scan), 인덱스 역순 스캔(Index Backward Scan)으로 나뉜다.

 

참고할 점은 인덱스는 역순 스캔보다 정순 스캔이 더 빠르다는 것이다. 그 이유는 페이지 잠금이 인덱스 정순 스캔에 적합하고, 페이지 내에서 인덱스 레코드가 단방향으로 연결된 구조이기 때문이다. (카카오 테크에서 자세히 설명)

레코드 추가, 삭제 수정

레코드 추가

레코드 추가의 비용이 1이라면 인덱스 추가비용은 약 1.5이다. 그렇기에 만약 인덱스가 3개라면 레코드 추가 비용은(1+1.5x3)이 된다. 그래서 인덱스 추가 작업을 즉시 처리하지 않고 메모리에 모았다가 한번에 쓰기도 한다.

장점 : 디스크 쓰기 비용 감소, 요청 시 메모리에서 바로 결과 반환하므로 빠르다. 
단점: 유니크 인덱스와 같이 중복 처리가 필요하다면 즉시 반영해야 한다.

유니크 인덱스는 중복 검사 시 읽기 잠금, 쓰기 시 쓰기 잠금을 하기 때문에 이 과정에서 데드락이 빈번하게 발생하여 작업이 지연될 수 있다. 그렇기에 반드시 유일성이 보장되어야 할 때 사용한다. 또한 레코드 추가 시 인덱스의 리프노드 페이지가 가득 차면 리프노드를 분리해야하는데, 이때 상위 노드에 저장된 자식 노드의 값까지 바꿔야한다는 단점이 있다.

 

레코드 삭제

레코드 삭제 시 인덱스도 같이 삭제해야하는데, 이것은 그냥 리프노드에 삭제 마킹 처리만 하면 된다. 이 공간은 또 쓰일수도, 아닐수도 있다. 이때 하는 삭제 마킹은 디스크 쓰기 작업이기 때문에 지연될 수 있다.

특히나 MySQL은 더욱 주의해야하는데, MySQL의 잠금 중 일부 레코드 잠금(넥스트 키락 또는 갭 락)의 경우 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠근다. 그렇기에 UPDATE 또는 DELETE를 할 때 적절히 사용할 인덱스가 없으면 불필요하게 많은 인덱스를 잠근다. 심지어는 모든 레코드를 잠그기도 한다.

 

레코드 수정

레코드 수정은 PK, 인덱스, 일반 값에 따라 나뉜다. 먼저 PK를 수정할 경우 최소 2번의 작업(delete+insert)이 필요하다. 만약 인덱스가 있다면 인덱스에도 추가 작업을 해줘야 한다. 인덱스를 수정할 경우 테이블과 인덱스에 추가 작업을 해야한다. 레코드를 수정한다는 것은 delete+insert이다. 그렇기에 PK와 인덱스를 사용할 수 있다면 사용하게 된다.

 

레코드 검색

PK를 이용한 검색 - 레코드의 실제 위치를 알 수 있기 때문에 가장 빠르다.
인덱스를 이용한 검색 - 인덱스 ->PK -> 실제 위치 이기 때문에 빠르다.
PK와 인덱스 모두 키를 기반으로 "트리 검색"을 통해 값을 빠르게 가져온다. 그런데 만약 유니크 인덱스라면 옵티마이저는 찾아야 할 값이 하나라는 것을 알고있다. 유니크 인덱스때문에 MySQL의 처리방식 변화나 차이점이 많이 있는데 결론적으로는 다른 값보다 수행이 빠르다.

일반 값을 이용한 검색 - 기본적으로 테이블 풀스캔을 하기 때문에 오래 걸린다. B- Tree는 인덱 키 값을 변형하지 않고 정렬된 상태로 저장한다. (물론 Varchar 255를 넘어가면 잘라서 인덱스 를 만든다.) 그래서 =, >등은 인덱스를 사용할 수 있지만 키 값의 뒷부분을 검색하거나 변형된 값으로 쿼리하는 경우에는 인덱스를 활용할 수 없다.

유니크 인덱스로 인해 뭐가 다른지 MySQL의 일부 레코드 잠금이 검색을 수행한 인덱스를 잠그고 그래서 모든 레코드를 잠근다?
유니크인덱스는 중복검사 시 읽기잠금, 쓸 때는 쓰기 잠금을 하기 때문에 데드락 발생할 수 있다.

읽기 방식에 따른 인덱스의 분류

인덱스 레인지 스캔

범위가 결정된 인덱스를 읽는 것이다.

1. 인덱스의 조건을 만족하는 값을 찾는다.
2. 시작 지점부터 필요한 만큼 인덱스를 순서대로 읽는다.
3. 읽어들인 인덱스와 PK를 이용해 최종 레코드를 읽어온다.(랜덤I/O)

인덱스에 PK가 저장되는 것은 MySQL의 InnoDB가 클러스터 테이블이기 때문이며, 다른 DBMS의 경우에는 다를 수 있다.

인덱스 풀 스캔

인덱스를 처음부터 끝까지 스캔하는 것. 인덱스가 A, B, C로 걸려있는데 조건절은 B C에 대해서만 걸려있거나 count(*)와 같은 경우에 사용한다. 그렇지만 일반적으로 이것은 인덱스를 사용한다고 하지 않고, 다만 테이블 풀 스캔보다 디스크 I/O가 적기 때문에 사용할 뿐이다.

루스 인덱스 스캔

인덱스를 듬성듬성 읽는 방식이다. 일반적으로 GroupBy(), MAX(), MIN()등에서 사용한다. 아래 쿼리를 보자.

SELECT dept_no, MIN(emp_no)
FROM dept_emp
WHERE dept_no BETWEEN 'D002' AND 'D004'GROUP BY dept_no;

위 쿼리에서 emp_no는 dept_no에 의존해 정렬되기 때문에 dept_no그룹별로 맨 처음 emp_no를 읽으면 된다. 옵티마이저도 이를 알고 있기 때문에 처음이 아닌 emp_no는 읽지 않는다.

인덱스 스킵 스캔

MySQL 8.0부터 추가된 기능으로, 인덱스의 뒷 컬럼만으로 검색하는 경우에 옵티마이저가 알아서 쿼리를 최적화하여 인덱스를 타도록 하는 방식이다. 예를 들어 gender, birth_date에 인덱스가 있다고 하자.

# 인덱스를 사용하지 못하는 쿼리
SELECTgender, birth_date
FROMemployee
WHEREbirth_date >= '1994-12-26';

위 쿼리를 MySQL이 아래와 같이 수행해준다.

SELECTgender, birth_date
FROMemployee
WHEREgender = 'M'AND birth_date >= '1994-12-26';
SELECTgender, birth_date
FROMemployee
WHEREgender = 'F'AND birth_date >= '1994-12-26';

이와 같은 인덱스 스킵 스캔이 수행되려면 아래 조건들이 만족되어야 한다.

1. 조회되는 컬럼은 인덱스만으로 처리되어야 한다. (커버링 인덱스)
2. 인덱스의 선행 컬럼이 WHERE절에 없다.
3. 인덱스 선행 컬럼의 카디널리티가 낮아야 한다. (유니크한 값이 적어야 한다.)

풀 테이블 스캔(인덱스 사용 X)

일반적으로 전체 테이블의 크기는 인덱스의 크기보다 훨씬 크기 때문에 풀 테이블 스캔은 상당히 많은 디스크 읽기를 필요로 한다. 그래서 MySQL은 연속된 페이지를 읽게 되면 백그라운드 쓰레드를 통해 다음 페이지를 미리 읽어 메모리(버퍼풀)에 넣어둔다. 이를 리드 어헤드(Read Ahead)기능이라고 한다. 보통 4개 혹은 8개의 페이지부터 시작해 최대 64개의 페이지까지 읽어오도록 증가된다. 풀 인덱스 스캔에도 이는 동일하게 적용된다.

인덱스 사용 시의 주의 사항

MySQL에는 갭락, 넥스트 키 락, 자동 증가락 등 많은 락이 있는데 그 중 레코드 락(Record Lock, Record only Lock)이 인덱스와 밀접하게 연관되어있다. 레코드락은 말 그대로 레코드를 잠그기 위한 락인데 MySQL의 경우 실제 레코드가 아니라 인덱스를 잠근다는 점에서 다른 DBMS와 다르다.

 

예시를 보며 이해해보도록 하자. 만약 성, 이름, 전화번호 테이블에서 성에만 인덱스가 걸려있다고 하자. 이때 성이 “김”이고 이름이 “민지”인 컬럼의 전화번호를 수정하려고 할 때 성=“김”이라는 조건으로 조회된 모든 인덱스에 락을 건다. 만일 성에도 인덱스가 없다면 테이블을 풀스캔하며 레코드를 갱신하기 때문에 테이블의 모든 레코드를 잠그게 된다.

레코드락은 클러스터링 인덱스(PK) 또는 유니크 인덱스를 이용해 변경을 하는 경우 사용된다. 그 외에는?