관계형 DB 인덱스의 사실상 표준 자료구조. 넓고 얕은 트리다.
왜 이진 탐색 트리가 아닌가 — 디스크 때문이다
메모리 자료구조라면 이진 탐색 트리로 충분하다. 그런데 인덱스는 디스크에 있고, 디스크는 1바이트가 아니라 페이지 단위(보통 8KB·16KB)로 읽는다. 한 번 다녀오는 비용이 비싸므로, 한 번 읽을 때 최대한 많은 키를 가져오는 게 이득이다.
- 100만 행을 찾을 때 디스크 접근 횟수
이진 트리 한 노드에 키 1개 → 높이 약 20 → 디스크 20번
B+Tree 한 노드에 키 수백 → 높이 3~4 → 디스크 3~4번
한 노드가 가지는 자식 수를 fan-out이라 한다. fan-out이 크면 같은 행 수를 더 낮은 높이로 덮으므로, 높이 = 디스크 왕복 횟수가 줄어든다. 인덱스 설계에서 "페이지에 키를 몇 개나 담느냐"가 곧 성능인 이유다.
B-Tree와 갈리는 결정적 한 가지
- B-Tree — 내부 노드에도 데이터가 있다
- B+Tree — 데이터(또는 행 포인터)는 리프에만 있고,
- 리프끼리 연결 리스트로 이어져 있다
이 차이가 범위 검색을 만든다. BETWEEN·>·ORDER BY는 시작점을 찾은 뒤 리프를 옆으로 쭉 훑기만 하면 된다. 트리를 오르내릴 필요가 없다.
-- 시작점 하나만 트리로 찾고, 나머지는 리프 스캔
SELECT * FROM orders WHERE created_at BETWEEN '2026-01-01' AND '2026-03-31';
-- 인덱스 순서와 정렬이 맞으면 별도 정렬 연산 자체가 사라진다
SELECT * FROM orders ORDER BY created_at LIMIT 20;
즉 B+Tree는 등치 검색뿐 아니라 범위와 정렬에도 강하다. 해시 인덱스가 등치만 되는 것과 대비된다.
그래서 무엇이 안 되나
트리가 키 앞부터 정렬돼 있다는 성질에서 한계가 나온다.
WHERE name LIKE 'kim%' -- ✅ 앞을 아니까 시작점을 찾을 수 있다
WHERE name LIKE '%kim' -- ❌ 앞을 모르면 어디서 시작할지 알 수 없다
면접 함정
- ❌ "인덱스는 O(1)" → O(log n)이다. 해시 인덱스가 O(1)에 가깝지만 범위·정렬을 못 쓴다.
- ❌ "B-Tree와 B+Tree는 같은 말" → 리프 연결 유무가 범위 검색 성능을 가른다.
높이를 눈으로 확인하기
-- PostgreSQL: pageinspect 확장으로 인덱스 메타 정보를 본다
CREATE EXTENSION IF NOT EXISTS pageinspect;
SELECT level, type FROM bt_page_stats('idx_member_email', 1);
-- level 0 = 리프. 루트 level 이 3이면 높이 4단
-- MySQL: 인덱스 크기와 통계
SELECT index_name, stat_value AS pages
FROM mysql.innodb_index_stats
WHERE table_name = 'member' AND stat_name = 'size';
100만 행이든 1억 행이든 높이는 보통 3~5단에 머문다. fan-out이 수백이라 한 단이 늘 때마다 담을 수 있는 행이 수백 배씩 늘기 때문이다. "데이터가 10배 늘면 조회가 10배 느려지지 않는다" 는 감각이 여기서 나온다.
키 크기가 fan-out을 결정한다
- 페이지 16KB, 키 하나가 8바이트(BIGINT) — → 한 페이지에 약 1,000개 → fan-out 1,000 페이지 16KB, 키 하나가 200바이트(긴 문자열) → 한 페이지에 약 60개 → fan-out 60
fan-out이 작아지면 같은 행 수를 덮는 데 트리 높이가 늘고 디스크 왕복이 는다. 긴 문자열 칼럼을 인덱스 앞쪽에 두면 안 되는 이유이고, InnoDB에서 PK를 작게 유지하라는 조언의 근거이기도 하다.