한 줄 정의
B-Tree는 자식 노드 수가 2개 이상인 균형 트리 로, 모든 리프 노드가 같은 깊이에 위치해 어떤 키를 찾더라도 거의 같은 비용으로 접근할 수 있는 DB 인덱스의 표준 자료구조입니다.
쉽게 말하면
B-Tree는 전화번호부의 계층적 색인 과 같습니다.
- 1단계: “ㄱ-ㅁ / ㅂ-ㅅ / ㅇ-ㅎ” 같은 큰 분류 (루트 노드)
- 2단계: 각 분류 안에 “가-나 / 다-라 / …” 같은 세부 분류 (브랜치 노드)
- 3단계: 실제 이름과 전화번호 (리프 노드)
“김철수”를 찾을 때 1단계 → 2단계 → 3단계 순으로 내려가면, 전체를 다 뒤지지 않고도 몇 번의 비교로 도착할 수 있습니다.
핵심 내용
B-Tree의 구조
flowchart TD subgraph Root["루트 노드 (Root)"] R["[M, T]"] end subgraph Branch["브랜치 노드 (Branch)"] B1["[D, H]"] B2["[P, R]"] B3["[V, Y]"] end subgraph Leaf["리프 노드 (Leaf) — 실제 인덱스 키 + 데이터 주소"] L1["A B C → 주소"] L2["D E G → 주소"] L3["H J L → 주소"] L4["M N O → 주소"] L5["P Q → 주소"] L6["R S → 주소"] L7["T U → 주소"] L8["V X → 주소"] L9["Y Z → 주소"] end R --> B1 R --> B2 R --> B3 B1 --> L1 B1 --> L2 B1 --> L3 B2 --> L4 B2 --> L5 B2 --> L6 B3 --> L7 B3 --> L8 B3 --> L9
- 루트 노드 : 트리의 시작점 (1개)
- 브랜치 노드 : 중간 경로 (여러 레벨)
- 리프 노드 : 실제 인덱스 키 값과 레코드의 주소 를 가짐
리프 노드가 가리키는 것
| 스토리지 엔진 | 리프 노드의 주소 | 의미 |
|---|---|---|
| MyISAM | ROWID (물리적 주소) | 디스크의 위치로 바로 접근 |
| InnoDB | 프라이머리 키 값 (논리적 주소) | PK로 다시 B-Tree 탐색 필요 |
이 차이는 매우 중요합니다. InnoDB에서는 세컨더리 인덱스로 레코드를 찾으려면, 먼저 세컨더리 B-Tree를 타고 내려가서 PK를 얻은 뒤, 다시 PK B-Tree(클러스터링 인덱스)를 타고 내려가야 데이터에 도달합니다. 이를 흔히 인덱스 왕복(back-ref) 이라고 부릅니다.
B-Tree 인덱스 키 추가/삭제
키 추가
INSERT 시 인덱스는 다음 순서로 갱신됩니다.
flowchart LR IN["INSERT 실행"] --> FIND["키가 들어갈 리프 페이지 탐색"] FIND --> FIT{페이지에 빈 공간?} FIT -->|Yes| ADD["정렬된 위치에 추가"] FIT -->|No| SPLIT["페이지 분리(split)"] SPLIT --> ADD2["키 추가 + 브랜치 노드 갱신"]
- 페이지 분리가 일어나면 비용이 큰 작업 이 됩니다 (디스크 쓰기 + 상위 노드 갱신)
- 인덱스가 많을수록 INSERT는 선형적으로 느려집니다
키 삭제
- 실제로 데이터를 지우지 않고 “삭제 마크” 만 합니다
- 공간 회수는 나중에 퍼지(purge) 스레드 가 비동기로 처리합니다
- 이 구조 덕분에 DELETE는 빠르지만, 오래된 트랜잭션이 있으면 퍼지가 지연되어 공간이 재사용되지 못할 수 있습니다
인덱스 키 값의 크기
MySQL의 페이지는 기본 16KB 입니다. 이 페이지 안에 최대한 많은 키를 담아야 B-Tree가 더 낮은 높이 를 유지할 수 있습니다.
| 키 크기 | 한 페이지에 담기는 키 수 | 트리 높이 |
|---|---|---|
| 16 바이트 | ~500개 | 낮음 (빠름) |
| 100 바이트 | ~80개 | 높아짐 (느려짐) |
키 값이 크면 생기는 일
- 페이지당 키 수가 줄어듭니다
- 트리 높이가 높아져 디스크 I/O 횟수 증가
- 버퍼 풀에 담을 수 있는 페이지 수가 줄어 캐시 효율 저하
따라서 PK는 최대한 작게, 세컨더리 인덱스에 포함되는 칼럼도 가급적 짧게 설계해야 합니다.
B-Tree 인덱스의 깊이
트리 높이는 검색 시 읽어야 하는 페이지 수 와 직결됩니다.
1000만 건 레코드 기준
- 페이지당 500키 → 높이 ≈ 3 (1000만 < 500³ = 1억 2500만)
- 페이지당 100키 → 높이 ≈ 4
MySQL의 일반적인 B-Tree 깊이는 3~4 수준 입니다. 즉, 1천만 건 이상의 테이블에서도 3~4번의 페이지 읽기 로 원하는 레코드를 찾을 수 있습니다. 인덱스가 강력한 이유입니다.
선택도(Cardinality)와 인덱스 효율
선택도 = 인덱스 칼럼의 유니크한 값 수 / 전체 레코드 수
| 칼럼 | 선택도 | 평가 |
|---|---|---|
| ≈ 1 | 매우 높음 (거의 유니크) | |
| city | ≈ 0.001 | 낮음 |
| gender | ≈ 0.0000001 (2/전체) | 매우 낮음 |
선택도가 낮은 칼럼은 인덱스를 만들어도 많은 레코드를 읽어야 하므로 효율이 떨어집니다. 옵티마이저가 풀 스캔을 선택하는 이유입니다.
실무 기준
- 읽어야 할 레코드가 전체의 20~25% 이하 일 때만 인덱스가 유리합니다
- 20~25%를 넘으면 풀 스캔(순차 I/O)이 더 빠릅니다
인덱스 스캔의 종류
1. 인덱스 풀 스캔 (Index Full Scan)
인덱스의 리프 페이지를 처음부터 끝까지 모두 읽는 방식입니다.
- 데이터 파일보다는 인덱스가 작으므로 테이블 풀 스캔보다는 효율적
SELECT col FROM tab ORDER BY col같은 쿼리에서 사용됨
2. 인덱스 레인지 스캔 (Index Range Scan)
가장 일반적이고 효율적 인 스캔 방식입니다.
flowchart LR START["시작 조건 탐색<br/>(예: WHERE emp_no >= 10000)"] --> ROOT["루트부터 내려가서<br/>시작 리프 위치 찾기"] ROOT --> SCAN["리프 페이지 순차 스캔<br/>(연결 리스트 이용)"] SCAN --> STOP["종료 조건까지<br/>(예: emp_no < 20000)"]
- 리프 페이지는 좌우로 연결된 이중 연결 리스트 구조
- 시작점만 찾으면 그 이후는 순차 I/O 로 빠르게 스캔 가능
3. 루스 인덱스 스캔 (Loose Index Scan)
인덱스 키 일부만 이용해 띄엄띄엄 스캔하는 방식입니다.
SELECT dept_no, MIN(emp_no) FROM dept_emp GROUP BY dept_no;dept_no별로 첫 레코드만 읽으면 되므로, 각dept_no그룹의 첫 값만 스킵해가며 읽습니다- GROUP BY 최적화의 핵심 메커니즘
4. 인덱스 스킵 스캔 (Index Skip Scan) — MySQL 8.0+
복합 인덱스의 선행 칼럼 조건이 없어도 인덱스를 활용할 수 있는 기능입니다.
-- 인덱스: (gender, birth_date)
SELECT * FROM employees WHERE birth_date >= '1965-02-01';- 기존에는
gender조건이 없으면 이 인덱스를 쓸 수 없었음 - MySQL 8.0은
gender의 유니크 값(M/F)마다 내부적으로 for loop 를 돌려 인덱스를 활용함 - 선행 칼럼의 유니크 값이 적을수록 효과적 (많으면 풀 스캔과 다름없음)
커버링 인덱스 (Covering Index)
쿼리가 인덱스에 포함된 칼럼만 요구 할 때, 데이터 파일을 아예 읽지 않고 인덱스만으로 응답하는 최적화입니다.
-- 인덱스: (first_name, last_name)
SELECT first_name, last_name FROM employees WHERE first_name = 'Georgi';이 쿼리는 인덱스만 읽으면 끝납니다. 인덱스 왕복(세컨더리 → PK → 데이터)이 사라집니다.
InnoDB의 숨은 이점
InnoDB 세컨더리 인덱스의 리프에는 PK가 자동으로 포함 되어 있습니다. 따라서 SELECT pk, indexed_col 같은 쿼리는 자동으로 커버링 인덱스 가 됩니다.
-- 인덱스: (first_name)
-- PK: emp_no
SELECT emp_no, first_name FROM employees WHERE first_name = 'Georgi';
-- → 자동 커버링복합 인덱스 칼럼 순서
복합 인덱스 (A, B, C) 는 다음 순서로 좌측부터 사용 됩니다.
| WHERE 조건 | 인덱스 사용 |
|---|---|
| A = ? | 사용 (A 부분) |
| A = ? AND B = ? | 사용 (A, B 부분) |
| A = ? AND B = ? AND C = ? | 완전 사용 |
| B = ? | 사용 불가 (MySQL 8.0 이전) / 스킵 스캔 가능 |
| A = ? AND C = ? | A만 사용, C는 필터링 |
칼럼 순서 설계 원칙
- 등가 조건(=) 칼럼을 앞에 배치
- 선택도 높은 칼럼을 앞에 배치
- 범위 조건 칼럼은 뒤에 배치 (범위 이후 칼럼은 인덱스 정렬 활용 불가)
인덱스 정렬
인덱스는 정렬된 상태 로 저장되므로, ORDER BY가 공짜 일 수 있습니다.
-- 인덱스: (first_name) 오름차순
SELECT * FROM employees ORDER BY first_name; -- 추가 정렬 불필요
SELECT * FROM employees ORDER BY first_name DESC; -- 역순 읽기MySQL 8.0부터는 내림차순 인덱스 도 지원합니다 (CREATE INDEX ix ON t (a DESC, b ASC)).
해시 인덱스와의 차이
| 기준 | B-Tree | Hash |
|---|---|---|
| 정렬 | 유지 | 없음 |
| 등가 검색 | O(log N) | O(1) |
| 범위 검색 | 가능 | 불가 |
| 정렬 결과 | 공짜 | 별도 정렬 필요 |
일반 테이블 인덱스는 범위 검색과 정렬 이 필요하므로 B-Tree가 기본입니다. InnoDB의 어댑티브 해시 인덱스는 B-Tree 위에 자주 접근되는 키에 대해 자동 생성 되는 보조 역할입니다.
정리
인덱스 스캔 종류 비교
| 스캔 종류 | 사용 시점 | 효율 |
|---|---|---|
| Index Full Scan | WHERE 없음, SELECT·ORDER BY가 모두 인덱스 칼럼 | 중간 |
| Index Range Scan | WHERE에 범위/등가 조건 | 높음 (가장 일반적) |
| Loose Index Scan | GROUP BY 최적화 | 매우 높음 |
| Index Skip Scan (8.0+) | 복합 인덱스 선행 칼럼 조건 없음 | 선행 칼럼 카디널리티 낮을 때만 |
| Covering Index | 쿼리 칼럼이 모두 인덱스에 포함 | 매우 높음 |
복합 인덱스 설계 체크리스트
| 체크 항목 | 판단 기준 |
|---|---|
| 등가 조건 칼럼 앞 | = 조건 칼럼을 선행에 |
| 범위 조건 칼럼 뒤 | >, <, BETWEEN은 후행에 |
| 선택도 순 | 높은 것부터 앞에 |
| 정렬 고려 | ORDER BY 칼럼이 뒤쪽에 포함되면 무정렬 가능 |
내 생각
-
복합 인덱스 설계는 “WHERE → ORDER BY → SELECT” 순으로 분석하면 간단합니다. WHERE의 등가 조건을 먼저 배치하고, ORDER BY 칼럼을 다음에, 마지막으로 SELECT 칼럼까지 포함하면 커버링 인덱스가 됩니다.
-
인덱스 스킵 스캔은 MySQL 8.0에서 추가됐지만, 만능이 아닙니다. 선행 칼럼의 유니크 값이 적을 때만 효율적이고, 일반적으로는 “복합 인덱스의 선행 칼럼은 반드시 WHERE에 포함시키자” 는 원칙이 여전히 유효합니다.
-
커버링 인덱스는 “필요한 칼럼만 SELECT하라” 와 연결됩니다.
SELECT *는 커버링 인덱스 기회를 없애는 가장 흔한 실수입니다. 특히 대용량 테이블에서는 명시적으로 칼럼을 나열하는 습관이 중요합니다. -
B-Tree 깊이 3~4 라는 사실을 기억하면 “인덱스를 타면 왜 이렇게 빠른가?”가 직관적으로 이해됩니다. 반대로 풀 스캔은 수백만 페이지를 읽어야 하므로 차이가 수천 배 납니다.
관련 개념
- Ch08-1 디스크 읽기 방식 — I/O와 페이지 크기
- Ch08-8 클러스터링 인덱스 — InnoDB 세컨더리 인덱스의 리프 = PK
- Ch05-3 InnoDB 스토리지 엔진 잠금 — 인덱스와 잠금 범위
- Ch04-2 InnoDB 스토리지 엔진 — 버퍼 풀, 어댑티브 해시 인덱스
출처
- Real MySQL 8.0 (1권), 8.3 B-Tree 인덱스