인덱스와 B-Tree, 그리고 스캔 방식

인덱스

인덱스는 추가적인 쓰기 작업과 저장 공간을 들여 테이블의 검색 속도를 높이는 자료 구조다.

• 검색이나 정렬에 자주 쓰이는 컬럼에 건다.
• 값의 분포가 넓은(중복이 적은) 컬럼에 걸어야 효과가 있다. 흔히 조건에 걸리는 행이 전체의 5~10% 이하일 때 효과적이라고 본다.
• 데이터를 수정하면 인덱스도 함께 갱신해야 한다. 수정이 잦은 컬럼에 인덱스를 걸면 쓰기 비용이 커지므로 피하는 것이 좋다.

ORDER BY, GROUP BY와 인덱스

• ORDER BY: 인덱스는 정렬된 상태로 저장되므로, 인덱스 순서대로 읽으면 추가 정렬 연산이 필요 없다.
• GROUP BY: 인덱스가 없으면 테이블을 읽어 그룹을 만들고 정렬하는 과정을 거친다. 인덱스가 있으면 이미 정렬된 키 값을 따라 그룹화하므로 정렬 과정을 생략할 수 있다.

PK, FK와 인덱스

일반적인 DBMS에서 PK를 지정하면 인덱스가 함께 만들어진다.

• PK는 유일성을 보장하지만, 일반 인덱스는 유일성을 보장하지 않는다.
• InnoDB에서는 테이블 자체가 PK 순서로 저장되므로 PK 인덱스를 위한 별도 공간이 없고, 그 외의 인덱스는 따로 저장된다.
• InnoDB에서는 FK를 걸면 해당 컬럼에 인덱스가 자동으로 생성된다.

LIKE 검색

패턴	인덱스 사용
'ABC%'	가능
'%ABC'	불가
'%ABC%'	불가

인덱스는 값의 왼쪽부터 정렬되어 있으므로 앞부분이 고정되지 않은 패턴에는 쓸 수 없다. 이런 검색에는 전문 검색(Full-Text Search)을 사용한다. 전문 검색은 문장에서 단어나 구를 기준으로 색인을 만들어 두는 방식으로, 패턴 매칭인 LIKE와 다르게 동작한다.

1. 대상 컬럼에 Full-Text 인덱스를 생성한다.
2. MATCH(column) AGAINST('search term') 구문으로 검색한다.

MySQL의 전문 검색 인덱스는 Real MySQL 8.0 Ch.8 — R-Tree, 전문 검색, 함수 기반, 멀티 밸류 인덱스에서 다룬다.

B-Tree

• 하나의 노드가 2개보다 많은 자식 노드를 가질 수 있는 트리다.
• 한 노드에 여러 개의 Key를 저장한다. M차 B-Tree라면 한 노드에 최대 M-1개의 Key를 담는다.
• Balanced Tree의 일종으로, 모든 리프 노드가 같은 레벨을 유지한다.

탐색(하향식)

1. 루트 노드에서 시작한다.
2. 찾는 값 K를 노드의 Key들과 비교해, 있으면 종료하고 없으면 알맞은 자식 노드로 내려간다.
3. 리프 노드까지 반복한다. 리프 노드에서도 찾지 못하면 트리에 없는 값이다.

삽입(상향식)

1. 값이 들어갈 리프 노드를 찾는다.
2. 노드의 최대 Key 개수를 넘지 않으면 그대로 넣는다.
3. 넘으면 노드를 분할하고, 그 영향이 부모 노드 쪽으로 올라가며 위치를 재조정한다.

B+Tree

B-Tree에서는 리프 노드를 차례로 읽으려면 매번 루트와 브랜치 노드를 거쳐야 한다. B+Tree는 리프 노드끼리 Linked List로 연결해, 브랜치 노드를 다시 방문하지 않고도 모든 리프 노드를 순서대로 읽을 수 있게 한 구조다.

• 데이터는 리프 노드에만 저장하고, 루트와 브랜치 노드에는 Key와 자식 포인터만 저장한다.
• 내부 노드에 데이터를 두지 않으므로 한 블록에 더 많은 Key를 담을 수 있고, 그만큼 트리의 높이가 낮아진다.

구분	B-Tree	B+Tree
데이터 저장	모든 노드	리프 노드
높이	상대적으로 높음	낮음(노드당 Key가 많다)
전체 순회	모든 노드를 탐색	리프 노드만 순서대로 탐색
키 중복	없음	있음(내부 노드의 Key가 리프에도 존재)
단건 검색	찾는 Key가 루트에 가까운 노드에 있으면 리프까지 가지 않아도 된다	항상 리프 노드까지 내려간다

정리하면 단건 검색은 운이 좋을 때 B-Tree가 빠를 수 있지만, 범위 검색과 순차 접근은 B+Tree가 훨씬 유리하다. 데이터베이스 인덱스가 주로 B+Tree 형태를 쓰는 이유다.

자주 나오는 질문

해시가 아닌 B-Tree를 쓰는 이유

해시 함수는 등호(=) 연산에만 특화되어 있다. 데이터베이스 검색에는 부등호(<, >)를 이용한 범위 검색이 자주 쓰이는데, 해시 테이블은 값의 순서를 보존하지 않아 이를 처리할 수 없다.

Red-Black Tree가 아닌 B-Tree를 쓰는 이유

• Red-Black Tree는 메모리 안에서 데이터를 관리하는 데 적합하고, B-Tree는 디스크 I/O를 줄이는 데 맞춰진 구조다.
• B-Tree의 노드 크기는 디스크의 블록 또는 페이지 크기와 일치한다. 노드 하나를 읽는 것이 디스크 I/O 한 번이고, 노드당 Key가 많아 트리가 낮으므로 I/O 횟수가 적다.
• B+Tree는 리프 노드가 연결 리스트로 이어져 있어 순차 접근에도 효율적이다.

오름차순 인덱스를 역순으로 읽으면

B+Tree의 리프 노드는 양방향으로 연결되어 있어 역순으로도 따라갈 수 있다. 다만 MySQL InnoDB에서는 역순 스캔(Backward index scan)이 정순 스캔(Forward index scan)보다 느리다.

1. 페이지 잠금이 정순 스캔에 적합한 구조다.
2. 페이지 안에서 인덱스 레코드는 단방향으로만 연결되어 있다.

자세한 내용은 Real MySQL 8.0 Ch.8 — B-Tree 인덱스의 스캔 방향 부분에 정리했다.

스캔 방식

Table Full Scan

테이블에 속한 블록 전체를 읽어 원하는 데이터를 찾는다.

• 순차 접근이며, 한 번의 I/O로 여러 블록을 읽는다(Multi Block I/O).
• 캐시에서 찾지 못하면 한 번의 I/O에 여러 블록을 메모리로 가져온다.

Index Range Scan

인덱스에서 필요한 범위만 스캔하고, 거기서 얻은 레코드 주소로 테이블의 데이터를 찾는다.

• 큰 테이블에서 소량의 데이터를 찾을 때는 반드시 인덱스를 사용해야 한다.
• 랜덤 접근이며, 한 번의 I/O로 한 블록을 읽는다(Single Block I/O).
• 캐시에 없으면 레코드 하나를 읽을 때마다 I/O가 필요하다. 그래서 많은 데이터를 읽을 때는 오히려 Full Scan이 유리하다.

Index Full Scan

인덱스의 선두 컬럼이 조건절에 없으면 Index Range Scan을 할 수 없다. 이때 옵티마이저는 Table Full Scan을 고려하지만, 테이블이 매우 크다면 인덱스 전체를 읽는 쪽이 낫다.

• 인덱스는 테이블보다 훨씬 작다.
• 인덱스 스캔 단계에서 대부분의 레코드를 걸러내고 아주 일부만 테이블에 접근하는 상황이라면 Table Full Scan보다 유리하다.

인덱스가 있는데도 Table Full Scan으로 동작하는 이유

옵티마이저는 쿼리 결과에 포함될 행의 비율을 예측해 접근 방법을 정한다.

• 조건에 해당하는 행의 비율이 높으면, 레코드마다 랜덤 I/O를 하는 인덱스 스캔보다 순차적으로 읽는 Full Scan이 빠르다.
• 테이블이 아주 작을 때도 인덱스를 거치는 것보다 그냥 읽는 편이 빠르다.
• 읽어야 할 양이 일정 수준을 넘는데도 인덱스를 타고 있다면, 힌트로 Full Scan을 유도하는 것도 방법이다.