MySQL 인덱스 탐색 원리와 LIKE 검색의 인덱스 활용

 

MySQL 인덱스 탐색 원리와 LIKE 검색의 인덱스 활용

대부분의 개발자라면 누구나 “인덱스를 걸면 검색속도가 빨라진다”는 사실은 알고 있다.

하지만 ‘왜 빨라지는지?’ 그리고 특정 상황에서는 인덱스를 걸어도 속도가 빨라지지 않는데, 그 이유를 알기 위해는 인덱스가 어떤 구조로 데이터를 저장하고 탐색하는지 그 원리를 이해해보려고 한다.

 

인덱스가 없다면?

우선 인덱스가 없는 테이블에서 특정 값을 찾으려면 어떻게 해야 할까?

무식하게 테이블의 모든 값을 처음부터 읽으면서 찾으려는 값과 맞는지 비교하면서 찾는 방법밖에 없다.

이 방식을 Full Table Scan이라고 부른다.

 

예를 들어 100만건 이상의 데이터가 저장되어 있는 유저 테이블에 username = ‘seungjun’ 인 행을 찾는다고 해보자. Full Table Scan 으로 찾는 경우 최악의 경우 100만건 모두를 읽어야 하는 상황이 발생한다.

데이터가 증가할 수록 탐색해야 하는 데이터도 비례하여 증가하기 때문에 속도도 당연히 느려진다.

 

이러한 문제를 해결하기 위해 인덱스가 존재한다. 인덱스는 원본 데이터와 별도로, 검색에 최적화된 자료구조에 데이터를 정렬하여 저장한다. 이를 통해 Full Table Scan 없이도 원하는 데이터를 빠르게 찾을 수 있다.

 

인덱스의 자료구조 B+Tree

MySQL InnoDB는 인덱스 구현에 B+Tree 자료구조를 사용한다. B+Tree를 이해하는 것이 인덱스 동작 원리를 이해하는것의 핵심이다.

 

B+Tree는 다음과 같은 특징을 가진 균형 트리이다.

 

https://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/

 

• 모든 실제 데이터는 리프 노드에만 존재한다. 루트 노드와 내부 노드는 탐색을 위한 키 값만 가지고 있다.
• 리프 노드들은 서로 연결되어 있다(Linked List). 이 특성으로 Range Scan을 효율적으로 만든다.
• 모든 키는 정렬된 상태로 유지된다. 이것이 빠른 검색의 핵심이다.
• 트리의 모든 리프 노드는 같은 깊이에 있다. 어떤 데이터를 찾든 동일한 횟수의 노드 접근이 필요하다.

B+Tree의 가장 큰 특징은 "모든 데이터가 정렬된 상태로 저장된다"는 점이다.

 

동작 방식

B+Tree는 책의 목차와 같은 원리로 동작한다.

영영사전에서 Apple을 찾는다고 해보자.

1. 맨 앞이 A인 페이지를 찾는다.
2. 그 페이지에서 p로 시작하는 부분을 찾는다.
3. 그 다음 p ,l 순서로 좁혀가며 찾는다.

영영사전이 알파벳 순서로 정렬되어 있기 때문에 이렇게 찾을 수 있고 이와 동일하게 B+Tree도 키로 정렬되어 있기 때문에 동일한 원리로 검색이 가능하다.

 

Clustered Index와 Secondary Index

InnoDB에서 인덱스는 크게 두 종류로 나뉜다.

 

Clustered Index

실제 데이터를 담은 Clustered Index는 테이블당 단 하나만 존재한다. 실제 테이블 데이터 자체가 이 인덱스의 리프 노드에 저장된다. InnoDB에서는 Primary Key가 Clustered Index가 된다.

그래서 테이블을 Full Scan 한다는 것은 곧 Clustered Index의 리프 노드를 순차적으로 읽는다는 의미이다.

 

Secondary Index

Primary Key가 아닌 다른 컬럼에 생성하는 인덱스가 Secondary Index다. 예를 들어 username 컬럼에 인덱스를 생성하면 이것이 Secondary Index다.

Secondary Index의 리프 노드에는 인덱스 키 값 + 해당 행의 Primary Key 값이 저장된다.

 

인덱스 탐색 방식

B+Tree 인덱스에서 데이터를 찾는 방식은 크게 세 가지로 분류할 수 있다.

 

Index Unique Scan

Primary Key나 Unique Index로 단일 값을 검색할 때 발생한다.

SELECT * FROM users WHERE id = 100;

B+Tree를 루트에서 리프까지 내려가며 정확히 하나의 행만 찾기 때문에 가장 효율적인 탐색 방식이다.

 

Index Range Scan

특정 범위의 값을 검색할 때 발생한다.

SELECT * FROM users WHERE username >= 'kim' AND username < 'lee';

검색 과정

1. B+Tree에서 범위의 시작점('kim')을 찾아 리프 노드까지 내려간다.
2. 리프 노드에서 조건을 만족하는 동안 연결된 다음 리프 노드로 순차 이동
3. 조건을 벗어나면('lee' 찾음) 검색 종료

B+Tree의 리프 노드가 연결 리스트로 이어져 있기 때문에 범위 탐색이 효율적이다.

 

Full Index Scan

인덱스의 전체 리프 노드를 읽는 경우다. Full Table Scan보다는 효율적일 수 있지만, 여전히 비효율적인 접근이다.

 

LIKE 검색의 인덱스 활용 분석

B+Tree의 구조와 탐색 원리를 이해했으니, LIKE 검색에서 와일드카드 위치에 따라 인덱스 활용이 어떻게 달라지는지 이해할 수 있다.

 

username 컬럼에 인덱스가 있고, 데이터가 알파벳 순으로 정렬되어 있다고 가정하자.

 

인덱스 리프 노드는 아래와 같이 정렬되어 있다.

[abraham] → [anakim] → [bob] → [charlie] → [kim] → [kimchi] → [park] → [takim]

 

후위 와일드카드(전위 일치) LIKE 'kim%'

SELECT * FROM users WHERE username LIKE 'kim%';

이 쿼리는 'kim'으로 시작하는 모든 값을 찾기 때문에 인덱스를 완벽하게 활용한다.(Index Range Scan)

 

동작 원리

1. B+Tree는 문자열을 왼쪽부터 정렬한다.
2. kim 로 시작하는 첫 번째 레코드는 정렬된 리스트의 특정 위치에 모여 있음이 보장된다.
3. kim보다 크거나 같은 첫 번째 위치를 찾아, kim이 아닐 때까지 쭉 읽는다.

 

전위 와일드카드(후위 일치) LIKE '%kim'

SELECT * FROM users WHERE username LIKE '%kim';

이 쿼리는 'kim'으로 끝나는 모든 값을 찾는다. 이 경우 인덱스를 활용할 수 없다. (Full Table Scan 또는 Full Index Scan)

 

이 쿼리가 인덱스를 활용할 수 없는 이유는 정렬 순서와 검색 조건의 불일치 하기 때문이다.

인덱스는 문자열의 첫 글자부터 정렬되어 있다.

 

인덱스의 정렬 순서는 아래와 같다.

[abraham] → [anakim] → [bob] → [charlie] → [kim] → [kimchi] → [park] → [takim]

 

'kim'으로 끝나는 값들을 살펴보자 anakim, kim, takim

이 값들은 인덱스에서 연속되어 있지 않다. 첫 글자가 각각 'a', 'k', 't'로 다르기 때문에 인덱스 전체에 흩어져 있다.

 

범위 검색이 불가능한 이유

Index Range Scan은 정렬된 데이터에서 연속된 구간을 읽는 것이다.

'kim'으로 끝나는 값들은 인덱스에서 연속된 구간이 없기 때문에, 시작점과 종료점을 알수 없다.

즉, 시작 지점을 찾을 수 없으므로, 결국 처음부터 끝까지 다 읽어봐야 한다.

 

결과적으로 전체 테이블(또는 인덱스)을 스캔하면서 모든 행에 대해 LIKE '%kim' 조건을 개별적으로 비교해야 한다.

 

양쪽 와일드카드(양쪽 일치) LIKE '%kim%'

SELECT * FROM users WHERE username LIKE '%kim%';

이 쿼리는 'kim'을 포함하는 모든 값을 찾는다. 후위 일치와 같은 이유로 인덱스를 활용할 수 없다.

앞부분이 정해지지 않았기 때문에, 검색을 시작할 위치를 결정할 수 없다.

 

범위 검색이 가능하려면 "인덱스 키의 prefix가 고정되어야" 한다는 것이 핵심 원리다. LIKE '%kim%' 에서는 prefix가 고정되어 있지 않다.

 

인덱스를 아예 안 쓰는 걸까?

후위 일치(또는 양쪽 일치) 검색을 할 때 Full Index Scan으로 검색하는지 Full Table Scan을 하는지는 상황에 따라 다르다.

 

1. 커버링 인덱스일 경우

• 쿼리에서 요구하는 칼럼이 모두 인덱스에 포함되어 있다면, 데이터 파일까지 가지 않고 인덱스만 처음부터 끝까지 읽는다.(Index Full Scan)
• 테이블 전체를 읽는 것보단 빠르지만, 여전히 효율적인 Range Scan은 아니다.

2. 일반적인 경우

• 인덱스에 없는 칼럼까지 조회해야 한다면, 옵티마이저는 "어차피 인덱스 다 뒤지고 다시 테이블도 가야 하니, 그냥 테이블을 처음부터 읽자"고 판단하여 Full Table Scan을 수행한다.