InnoDB가 인덱스를 어떻게 저장하고 탐색하는지, 개발자 입장에서 알아야 할 B-Tree 구조를 정리했다.
Balanced Tree의 약자다. 모든 리프 노드가 같은 깊이에 위치해서 어떤 키를 검색해도 탐색 비용이 일정하다.
데이터베이스 인덱스에 B-Tree(정확히는 B+Tree)를 쓰는 이유는 두 가지다.
BETWEEN, >, < 같은 범위 조건에 효율적이다MySQL InnoDB는 정확히는 B+Tree를 쓴다. B-Tree와 달리 내부 노드에는 키만 있고, 실제 데이터(또는 포인터)는 리프 노드에만 있다. 그래서 리프 노드끼리 연결 리스트로 이어진다.
[ 루트 노드 ]
/ \
[ 내부 노드 ] [ 내부 노드 ]
/ \ / \
[리프] [리프] [리프] [리프]
↔ ↔
(리프 노드끼리 양방향 연결)
노드 하나 = InnoDB 페이지 1개 = 기본 16KB
InnoDB의 가장 중요한 특징이다. Primary Key 자체가 테이블 데이터의 저장 구조다.
PK 인덱스 리프 노드에 실제 행 데이터 전체가 들어있다
리프 노드: [PK=1 | name="kim" | age=30 | ...]
[PK=2 | name="lee" | age=25 | ...]
[PK=3 | name="park"| age=40 | ...]
PK 순서로 데이터가 물리적으로 정렬되어 저장된다. 그래서 PK 범위 조건 조회는 디스크 순차 읽기가 된다.
Auto Increment PK를 권장하는 이유: 새 레코드를 항상 마지막에 추가할 수 있어서 페이지 분할이 거의 없다. UUID나 랜덤 값을 PK로 쓰면 중간 삽입이 빈번히 발생해서 페이지 분할이 잦고 인덱스가 단편화된다.
PK가 아닌 컬럼에 생성한 인덱스.
세컨더리 인덱스 리프 노드: [인덱스 키 | PK 값]
name 인덱스:
리프 노드: ["kim" | PK=1]
["lee" | PK=2]
["park"| PK=3]
세컨더리 인덱스 리프에는 실제 데이터가 아닌 PK 값이 들어있다. 세컨더리 인덱스로 조회하면:
이 2번 과정을 테이블 액세스(또는 북마크 룩업) 라고 한다. 세컨더리 인덱스 조회는 내부적으로 인덱스를 두 번 탄다.
세컨더리 인덱스만으로 쿼리를 완전히 처리할 수 있는 경우. 테이블 액세스가 발생하지 않아서 빠르다.
-- name, age 복합 인덱스가 있을 때
SELECT age FROM users WHERE name = 'kim';
-- name으로 인덱스 탐색, age도 인덱스 리프에 있음 → 테이블 액세스 불필요
EXPLAIN 결과에서 Extra: Using index가 보이면 커버링 인덱스가 적용된 것이다.
인덱스를 범위로 읽는 방식. =, <, >, BETWEEN, LIKE 'prefix%'
SELECT * FROM users WHERE age BETWEEN 20 AND 30;
-- 인덱스에서 age=20 위치 찾기 → 리프 연결 리스트 따라 age=30까지 순서대로 읽기
인덱스 전체를 처음부터 끝까지 읽는 방식. 테이블 풀스캔보다는 가볍지만 비효율적이다.
-- 1. 컬럼 가공
WHERE YEAR(created_at) = 2024 -- ❌ 함수 적용
WHERE created_at + 0 = ... -- ❌ 연산
-- 올바른 방법
WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31' -- ✅
-- 2. 묵시적 형변환
WHERE user_id = '123' -- user_id가 INT인데 문자열 비교 -- ❌ (경우에 따라)
-- 3. LIKE 앞 와일드카드
WHERE name LIKE '%kim' -- ❌ 인덱스 못 탐 (B-Tree는 앞에서부터 정렬)
WHERE name LIKE 'kim%' -- ✅
-- 4. OR 조건 (인덱스가 각각 있어도 하나만 타는 경우)
WHERE name = 'kim' OR age = 30
(a, b, c) 복합 인덱스가 있을 때:
WHERE a = 1 -- ✅ a 인덱스 사용
WHERE a = 1 AND b = 2 -- ✅ a, b 인덱스 사용
WHERE a = 1 AND b = 2 AND c=3 -- ✅ a, b, c 인덱스 사용
WHERE b = 2 -- ❌ a 없이 b만으로 시작 불가
WHERE a = 1 AND c = 3 -- ✅ a는 사용, c는 스킵 (b를 건너뜀)
인덱스는 왼쪽부터 순서대로 사용된다. 중간 컬럼이 빠지면 거기서 인덱스 사용이 끊긴다.
선택도(Cardinality)가 높은 컬럼을 앞에 두는 것이 원칙이지만, 실제 쿼리 패턴에 따라 달라진다. = 조건 컬럼을 앞에, 범위 조건 컬럼을 뒤에 두는 것이 일반적이다.
B-Tree 노드(페이지)가 꽉 차면 두 개로 나뉜다. 이 과정이 페이지 분할이다.
[1][2][3][4] ← 꽉 참
↓ 5 삽입
[1][2] [3][4][5] ← 분할 발생
페이지 분할이 자주 일어나면:
OPTIMIZE TABLE로 단편화를 해소할 수 있지만 테이블 잠금이 발생한다.