데이터베이스를 운영하다 보면, 속도가 점점 느려진다고 느껴질 때가 있다. 데이터가 수만, 수백만 건으로 늘어나면 단순히 WHERE 조건으로 조회하는 것만으로도 시간이 오래 걸리게 된다.
이럴 때 필요한 것이 바로 인덱스(Index)이다. 인덱스는 데이터를 빠르게 찾게 해주는 핵심 도구이며, MySQL에서는 보통 B-Tree (혹은 B+Tree) 구조를 사용한다.
인덱스란 무엇인가
인덱스는 책의 색인과 같은 역할을 한다. 테이블 전체를 처음부터 끝까지 훑는 대신, 색인을 따라가 원하는 데이터를 빠르게 찾을 수 있다.
DBMS에서는 보통 B-Tree 구조로 인덱스를 구현한다.
인덱스 유무에 따른 시간 복잡도
인덱스가 없으면 테이블 전체를 순차적으로 읽는 풀스캔(full scan)이 발생한다. 이는 O(N)이다. 인덱스가 있으면 B-Tree 탐색을 사용한다.
B-Tree는 균형 잡힌 트리 구조이므로 탐색 비용은 O(log N)이다. 즉, 데이터가 많아져도 검색 속도는 크게 느려지지 않는다.
이진 탐색 트리와 log₂ N
이진 탐색 트리에서는 탐색 횟수가 log₂ N (올림)이다.
데이터가 7개일 때는 log₂ 7 ≈ 2.8이므로 최악의 경우 3번 비교가 필요하다.
[4]
/ \
[2] [6]
/ \ / \
[1] [3] [5] [7]데이터 7개를 관리하는 이진 탐색 트리에서는 최대 3단계 탐색으로 원하는 값을 찾을 수 있다.
B-Tree의 구조
이진 트리는 자식이 최대 두 개뿐이지만, B-Tree는 더 많은 키와 자식을 가진다. 차수 M은 한 노드가 가질 수 있는 최대 자식 수를 의미한다.
따라서 한 노드가 가질 수 있는 최대 키의 수는 M-1이다.
M=3일 때
한 노드에 최대 2개의 키가 들어간다.
데이터가 7개일 때 가능한 B-Tree 구조는 다음과 같다.
[3 | 5]
/ | \
[1 | 2] [4] [6 | 7]최대 깊이는 2이므로 탐색은 2단계면 충분하다.
M=4일 때
한 노드에 최대 3개의 키가 들어간다.
데이터 1~10을 순서대로 넣으면 다음과 같은 구조가 된다.
[2 | 4 | 7]
/ | | \
[1] [3] [5 | 6] [8 | 9 | 10]깊이는 여전히 2이다. 이진 탐색 트리였다면 깊이가 4가 되었을 것이다.
B+Tree와 MySQL 인덱스
MySQL의 InnoDB 엔진은 B+Tree라는 자료구조를 사용해 인덱스를 관리한다. B+Tree는 일반적인 B-Tree를 변형한 구조인데, 가장 큰 특징은 실제 데이터가 리프 노드에만 저장된다는 점이다.
부모 노드는 단순히 검색 경로를 안내하는 색인 역할만 담당한다. 즉, 루트에서 출발해 리프 노드까지 내려가면 그곳에서 비로소 실제 데이터를 찾을 수 있다.
B+Tree의 또 다른 특징은 리프 노드들이 서로 연결 리스트로 이어져 있다는 것이다. 이 구조 덕분에 범위 검색이 매우 빠르다.
예를 들어 WHERE age BETWEEN 20 AND 30 같은 조건이 들어오면, 먼저 20이 위치한 리프 노드를 찾은 뒤 그 옆으로 이어진 노드들을 순차적으로 따라가면서 30까지 읽으면 된다. 리프들이 이미 정렬된 상태이기 때문에 범위 조회가 효율적이다.
트리의 높이는 매우 낮다는 점도 중요한 특징이다. 인덱스 트리의 각 노드는 디스크 페이지(보통 16KB) 단위로 관리되며, 한 페이지 안에는 수백에서 수천 개의 키가 저장된다.
이 때문에 branching factor(한 노드가 가질 수 있는 자식 수)가 커지고, 깊이 1이면 수백 건을 커버할 수 있고, 깊이 2면 수십만 건, 깊이 3이면 수억 건, 깊이 4면 수천억 건까지 커버가 가능하다.
즉 실제 서비스 환경에서 인덱스를 이용하면 보통 3~4단계 탐색만으로 원하는 데이터를 찾을 수 있다.
모든 WHERE 조건에 인덱스를 걸면 될까?
WHERE 조건이라고 해서 모두 인덱스를 걸면 좋은 것은 아니다. 인덱스는 데이터를 빠르게 찾게 해주지만, 생성과 유지에도 비용이 든다.
INSERT, UPDATE, DELETE 작업 시 인덱스도 함께 갱신되어야 하므로 쓰기 성능이 떨어진다.
또한 선택도가 낮은 컬럼, 예를 들어 성별(gender='M')처럼 전체의 절반 이상을 차지하는 조건에서는 인덱스를 타도 결국 많은 데이터를 읽어야 하므로 풀스캔이 더 빠를 수 있다.
따라서 인덱스는 자주 조회되는 조건, 조인에 사용되는 컬럼, 범위 검색이나 정렬에 자주 쓰이는 컬럼, 그리고 선택도가 높은 컬럼에 거는 것이 바람직하다.
MySQL에서 인덱스 관리
-- 일반 인덱스 생성
CREATE INDEX idx_member_id
ON member (member_id);
-- 유니크 인덱스 생성
CREATE UNIQUE INDEX idx_email
ON member (email);
-- 복합 인덱스 생성
CREATE INDEX idx_name_age
ON member (name, age);
-- 프라이머리 키 지정
ALTER TABLE member
ADD PRIMARY KEY (member_id);
-- 인덱스 삭제
DROP INDEX idx_member_id ON member;
-- 인덱스 확인
SHOW INDEX FROM member;데이터가 많아질수록 풀스캔의 비용은 기하급수적으로 커지지만, 인덱스를 이용하면 트리의 높이가 낮게 유지되므로 수억 건 데이터도 단 몇 단계 안에 조회가 가능하다.
그러나 인덱스는 만능이 아니다. 인덱스는 조회를 빠르게 하지만, 동시에 삽입과 수정, 삭제 시에는 반드시 갱신해야 하므로 쓰기 성능에 부담을 준다. 또한 무분별하게 인덱스를 만들면 저장 공간이 낭비되고, 옵티마이저가 올바른 인덱스를 선택하지 못해 오히려 성능이 떨어질 수도 있다.
따라서 인덱스는 읽기와 쓰기의 균형을 고려해 설계해야 한다. 자주 조회되는 컬럼, 조인에 활용되는 컬럼, 범위 검색이나 정렬이 필요한 컬럼, 그리고 선택도가 높은 컬럼에만 전략적으로 인덱스를 거는 것이 가장 효율적이다.
