3장. 리프를 잇다 — B+tree와 범위 검색

{/* 삽화 자리 — 서가 맨 아래 칸들이 좌우로 손을 잡아 한 줄로 이어져 있다 */}

1만 건을 범위로 읽으면 페이지를 46번 요청합니다. 같은 1만 건을 하나씩 찾으면 100,042번이에요. 2,175배 중에 리프 체인의 몫이 얼마인지, 이 장에서 갈라봅니다.

면접 실전 질문: ① B-tree와 B+tree는 무엇이 다른가요? ② 왜 데이터를 리프로 다 내렸나요? ③ 범위 조회가 인덱스에서 빠른 이유는 뭔가요?

배경 — 값 하나가 아니라 구간을 물으면

2장 끝에서 실토한 게 있습니다. 우리가 잰 나무는 1970년 논문의 B-tree가 아니라고요. 데이터가 리프에만 있었으니까요.

원래 B-tree는 중간 노드에도 데이터를 둡니다. 그러면 이런 일이 가능해요 — 찾는 값이 운 좋게 루트에 있으면 한 번 만에 끝납니다. 리프까지 안 내려가도 되죠.

값 하나를 찾는 데는 나쁘지 않은 성질입니다. 문제는 우리가 DB에 던지는 질문이 그것만은 아니라는 데 있어요.


SELECT * FROM request_log WHERE create_time BETWEEN ? AND ?;
SELECT * FROM member    WHERE age > 30 ORDER BY age;
SELECT * FROM orders    ORDER BY created_at DESC LIMIT 20;

전부 구간을 묻습니다. 그리고 구간을 정렬된 순서로 읽어야 해요.

중간 노드에 데이터가 흩어져 있는 트리에서 이걸 하려면 중위 순회(작은 값부터 순서대로 꺼내는 순회)를 해야 합니다. 리프를 하나 읽고, 부모로 올라가 거기 있는 값을 읽고, 다시 다른 리프로 내려가고, 또 올라가고. 순서대로 나오게 하려면 트리를 계속 오르내려야 합니다.

메모리 위에서는 포인터를 따라가는 것뿐이라 별일 아닙니다. 디스크 위에서는 그 오르내림이 전부 페이지 요청입니다.

1장에서 정한 단위로 다시 물어보죠. 구간 안의 행이 1만 개면 페이지를 몇 번 만져야 할까요?

스토리 — 두 가지를 바꾸면 순회가 산책이 된다

오늘 우리가 쓰는 인덱스는 원래 B-tree에서 두 가지를 바꾼 변종입니다.

첫째, 데이터를 전부 리프로 내렸습니다. 중간 노드에는 “이 값보다 작으면 왼쪽” 같은 이정표만 남습니다.

이건 손해처럼 보입니다. 운 좋게 중간에서 끝나는 경우가 사라지니까요. 이제 어떤 값을 찾든 항상 리프까지 내려가야 합니다.

그런데 그 대가로 얻는 게 큽니다. 중간 노드에서 데이터를 들어내면 그 자리에 이정표를 더 넣을 수 있어요. 2장에서 클러스터드 중간 노드가 페이지당 907개를 거느린 게 여기서 나온 겁니다 — 행이 통째로 들어 있었다면 63개가 한계였을 테니까요. 리프는 그대로 63행인데 중간 노드만 14배 넓어진 겁니다.

다만 이 이득은 클러스터드 인덱스 쪽 이야기입니다. 세컨더리 인덱스는 원래 중간 노드에 담을 게 키와 포인터뿐이라 이 변경으로 얻는 게 별로 없어요. 이 장의 측정은 전부 둘째 변경 이야기입니다.

둘째, 리프끼리 좌우로 이었습니다. 각 리프 페이지가 왼쪽 이웃과 오른쪽 이웃의 번호를 들고 있습니다.

이 하나로 범위 조회의 성격이 바뀝니다. 구간의 시작점을 찾을 때까지만 트리를 내려가고, 그 뒤로는 트리를 쳐다볼 필요가 없어요. 옆으로 걸어가면 됩니다. 트리 순회가 연결 리스트 순회가 되는 거죠.

정렬도 대체로 따라옵니다. 리프가 이미 키 순서로 놓여 있으니까요. 단 인덱스에 놓인 순서와 정렬 요구가 맞고 옵티마이저가 그 인덱스를 실제로 골랐을 때만입니다. 어긋나면 filesort로 돌아갑니다(9·11장).

이 변종은 누가 만들었나

깔끔한 답이 없습니다. 바이어와 맥크레이트의 1970년 논문에는 이 변종이 없고, 한 편의 논문이 B+tree를 도입한 것도 아닙니다. 데이터를 리프에만 두자는 아이디어가 여기저기서 변종으로 거론되다가 자리를 잡았어요.

📄 문서 기반 (미검증) — 이 변종들을 정리한 대표 문헌은 더글러스 코머의 1979년 서베이 「The Ubiquitous B-Tree」(ACM Computing Surveys 11권 2호, 121–137쪽)입니다. 제목 그대로 “어디에나 있는”이라는 말이 1979년에 이미 붙었습니다.

이름이 헷갈리는 것도 이 때문입니다. MySQL 문서도 InnoDB 인덱스를 그냥 “B-tree”라고 부르지만, 실제 구현은 데이터가 리프에만 있고 리프가 이어진 B+tree입니다.

그러면 정말 이어져 있는지 보면 됩니다. 2장에서 쓴 방법이 여기서도 통합니다.

핵심 — 파일을 열어 사슬을 따라가 봤습니다

InnoDB 페이지 헤더 맨 앞에는 이웃 페이지 번호가 들어 있습니다.


페이지 시작에서 offset  8 (4바이트)  FIL_PAGE_PREV   왼쪽 이웃. 없으면 0xFFFFFFFF
페이지 시작에서 offset 12 (4바이트)  FIL_PAGE_NEXT   오른쪽 이웃. 없으면 0xFFFFFFFF

잴 인덱스의 INDEX_ID는 서버가 알려줍니다.


SELECT i.NAME, i.INDEX_ID FROM information_schema.INNODB_INDEXES i
  JOIN information_schema.INNODB_TABLES t ON i.TABLE_ID = t.TABLE_ID
 WHERE t.NAME = 'bookdb/scan_demo';

200만 행짜리 세컨더리 인덱스에서 리프(레벨 0)만 골라, 왼쪽 끝에서 FIL_PAGE_NEXT를 따라 끝까지 걸어봤습니다.


$ docker run --rm -v db-index_mysql-data:/d:ro -v "$PWD":/w:ro python:3-alpine \
      python3 /w/ch03/leafchain.py /d/bookdb/scan_demo.ibd 244
리프 페이지 수      : 4247
왼쪽 끝(prev 없음)  : [24645]
오른쪽 끝(next 없음): [36142]
체인을 따라 걸은 수 : 4247
판정                : 전부 한 줄로 이어짐
역방향(prev) 정합   : 맞음
체인 순서 = 파일 순서: 4030/4246 구간이 연속 (94.9%)

✅ 실측 (MySQL 8.0.40 / Docker, 2026-08. 200만 행. 전체 소스: docs/book/code/db-index/ch03/leafchain.py)

머리가 하나, 꼬리가 하나, 그리고 4,247개가 빠짐없이 한 줄로 꿰어집니다. 역방향 포인터도 전부 맞습니다. 이중 연결 리스트예요.

그림으로 그리면 이렇습니다.


                    [루트]
                   /   |   \
              [중간] [중간] [중간]
              /  |     |  \    |  \
        [리프]↔[리프]↔[리프]↔[리프]↔[리프]   ← 4,247개가 이렇게

실제로는 리프뿐 아니라 각 레벨의 형제 페이지도 같은 방식으로 이어져 있습니다. 범위 조회가 쓰는 건 리프 쪽이라 여기서는 리프만 그렸습니다.

두 방법으로 같은 1만 건을 읽어봤습니다

같은 건수를 두 방법으로 읽어 페이지 요청 수를 셌습니다.

범위 조회 — BETWEEN으로 한 번. 리프에 닿은 뒤 옆으로 훑습니다.
개별 조회 — 같은 키를 하나씩 N번. 매번 루트에서 다시 내려갑니다.

둘 다 커버링 조회라 실제 행을 가지러 가는 왕복은 끼지 않았습니다. 개별 조회는 클라이언트 왕복 비용을 빼려고 서버 안 프로시저 루프로 돌렸고요.

읽은 건수	범위 조회 (요청)	개별 조회 (요청)	배수
1	10	18	1.8배
10	9	100	11배
100	11	1,012	92배
1,000	22	10,004	455배
10,000	46	100,042	2,175배

✅ 실측 (같은 환경. 값은 Innodb_buffer_pool_read_requests 델타이고, 두 방식 모두 같은 구간을 미리 훑어 워밍업한 뒤 쟀습니다. 1건 10회와 10건 9회의 역전은 오차예요 — 상태 변수를 읽는 쿼리 자체도 요청을 만들어서 해상도가 ±1회쯤 됩니다. 재현: COUNTS="1 10 100 1000 10000" ./ch03/rangevspoint.sh. 전체 소스: docs/book/code/db-index/ch03/rangevspoint.sh)

두 열의 성격이 완전히 다릅니다.

개별 조회는 10건부터 행당 10회에 붙습니다. 1건일 때만 18회로 튀는데, 첫 문장에 뭔가 더 붙는 것 같지만 이 측정으로는 갈라내지 못했습니다. 그 위로는 100건이든 1만 건이든 건당 10회를 그대로 곱해요.

그 10회가 뭔지도 재봤습니다. 프로시저 자체는 공짜입니다 — docs/book/code/db-index/ch03/point_lookups.sql으로 조회를 0건 시키면 요청 델타가 0이에요. 즉 10회는 전부 조회 문장 하나가 쓰는 값입니다. 범위 조회도 1건짜리 구간을 물으면 똑같이 10회가 나오고요.

2장에서 이 인덱스 높이가 3이었으니 그중 3회는 트리를 내려가는 몫으로 보입니다. 나머지 7회가 무엇인지는 이 측정으로 갈라내지 못했습니다. 확실한 건 하나예요 — 조회 문장을 하나 세울 때마다 10회가 새로 붙습니다.

범위 조회는 거의 안 늘어납니다. 2장 끝에서 남긴 질문의 답이 여기 있어요 — 높이는 딱 한 번만 청구됩니다 — 시작점을 찾을 때요. 그 뒤로는 높이가 3이든 4든 범위 조회 비용에 안 들어갑니다. 1건에 10회, 1만 건에 46회. 만 배를 읽었는데 요청은 4.6배만 늘었습니다. 시작점을 찾는 하강을 한 번만 하고, 나머지는 리프를 옆으로 걸었기 때문입니다.

1만 행이면 리프는 22페이지(10,000 ÷ 471)면 되는데 46회가 나왔습니다. 차액 24회가 무엇인지는 여기서도 갈라내지 못했습니다. 확실한 건 이겁니다 — 건수를 100배 늘리는 동안 차액은 10에서 24로, 두 배 남짓만 늘었습니다. 건수에 비례하지 않아요.

2,175배는 무엇의 차이인가

여기서 1장이 미리 못 박아둔 걸 꺼내야 합니다. 요청 수는 “버퍼풀에 페이지를 달라고 한 횟수”이지 서로 다른 페이지의 개수가 아니다. 이 구분이 결정적으로 쓰이는 자리가 여기예요.

두 방법이 만진 서로 다른 페이지 수는 세보지 않아도 계산이 됩니다. 리프 22페이지에 루트와 중간 노드를 더해 스물몇 개고, 개별 조회도 같은 페이지를 오갑니다. 양쪽 다 스물몇 개예요.

그러니까 2,175배는 페이지를 더 읽어서 생긴 값이 아닙니다. 같은 페이지를 1만 번 다시 달라고 해서 나온 값이에요. 루트 페이지 하나만 해도 1만 번 요청했습니다. 다만 그건 10만 회 중 10%고, 나머지 9만 회가 어느 페이지에 몇 번씩 갔는지는 이 측정으로 모릅니다.

그래서 이 격차가 나가는 곳도 디스크가 아닙니다. 전부 버퍼풀에 있는 상태였으니 CPU와 래치에서 나갑니다. 페이지가 메모리에 없다면 이야기가 또 달라지고요 — 그건 8장입니다.

비교가 비대칭이라는 것도 밝혀둡니다. 개별 조회는 문장 1만 개, 범위 조회는 문장 하나입니다. 일부러 그렇게 뒀어요 — 실무의 애플리케이션 루프 안 조회가 진짜로 문장 N개니까요. 다만 값의 출처는 알고 넘어갑시다. 리프 체인이 없애준 건 하강 쪽이고, 문장 비용을 없앤 건 “구간을 한 문장으로 물었다”는 사실입니다.

첫째 변경의 청구서

데이터를 리프로 다 내린 대가는 여기서 보이지 않습니다. 위 측정은 전부 커버링 조회였거든요 — 인덱스 안에 있는 값만 물었습니다.

SELECT *로 실제 행을 달라고 하면 이야기가 달라집니다. 세컨더리 인덱스 리프에 있는 건 행이 아니라 PK 값이니까요. 행에 닿으려면 클러스터드 인덱스를 처음부터 다시 내려가야 합니다.

그 왕복이 얼마인지가 7장입니다. 그리고 그 왕복을 아예 없애는 방법이 16장이고요.

이 이득이 없어지는 자리

표 첫 줄이 스스로 말하고 있습니다. 1건짜리 구간에서는 1.8배뿐이에요. 구간이 작으면 리프를 옆으로 걸 일이 거의 없으니 당연합니다. 범위 조회의 이득은 구간이 커야 나옵니다.

그리고 앞에서 본 94.9%가 두 번째 조건입니다. 리프가 논리적으로 이어져 있어도 파일 위에서 흩어져 있으면, 옆으로 걷는 게 순차 읽기가 아니라 랜덤 점프가 됩니다. 이 실험은 정렬된 값을 한 번에 부어 만들어 5%만 어긋났지만, 삽입과 삭제가 섞인 운영 테이블은 그렇지 않습니다.

정리

원래 B-tree는 중간 노드에도 데이터를 둡니다. 값 하나를 찾을 땐 괜찮지만, 구간을 정렬된 순서로 읽으려면 트리를 계속 오르내려야 합니다. 디스크에서는 그 오르내림이 전부 페이지 요청입니다.
오늘의 인덱스는 두 가지를 바꾼 변종입니다. 데이터를 전부 리프로 내리고, 리프끼리 좌우로 이었습니다.
첫째 변경의 이득은 팬아웃입니다. 중간 노드에서 행을 들어냈기 때문에 2장의 클러스터드 팬아웃 907이 나왔습니다(행이 들어 있었다면 63). 대가는 항상 리프까지 내려가야 한다는 것이고, 세컨더리 인덱스에는 애초에 해당이 없습니다.
둘째 변경의 이득은 범위 조회입니다. 시작점만 트리로 찾고 그 뒤로는 옆으로 걷습니다. 인덱스 순서와 정렬 요구가 맞으면 ORDER BY도 따라옵니다(어긋나면 filesort — 9·11장).
실측: 파일에서 리프 4,247개가 머리 하나 꼬리 하나로 빠짐없이 이어져 있었고, 1만 건 읽기에서 범위 46회 대 개별 100,042회 — 2,175배였습니다. 단 이 격차는 읽은 페이지 수가 아니라 같은 페이지를 다시 요청한 횟수의 차이입니다.
이득이 없어지는 조건도 둘 봤습니다. 구간이 작으면(1건에서 1.8배) 의미가 없고, 체인이 파일 위에서 흩어지면(이 실험에서도 5%) 옆으로 걷기가 랜덤 점프가 됩니다.
이 변종을 도입한 단일 논문은 없습니다. 코머의 1979년 서베이가 정리했고, 제목이 이미 「어디에나 있는 B-tree」였습니다.

생각해볼 질문

범위 조회가 싼 건 리프가 키 순서로 이어져 있기 때문입니다. 그렇다면 WHERE age > 30 ORDER BY name처럼 걸러내는 컬럼과 정렬하는 컬럼이 다르면 이 이득이 그대로 남을까요? (9·11장)
이 장의 측정은 전부 커버링 조회였습니다. SELECT *였다면 어느 열의 숫자가 얼마나 커졌을까요? (7장)
리프가 이중 연결 리스트라면 ORDER BY ... DESC는 어떻게 처리될까요? 오름차순과 값이 같을까요? (11장)

여기까지가 “인덱스를 타면 왜 싼가”입니다. 그런데 표를 다시 보면 불편한 게 하나 있어요. 1건에서는 1.8배, 1만 건에서는 2,175배 — 같은 인덱스인데 구간 크기에 따라 값이 세 자릿수로 달라집니다.

그럼 이 쿼리가 어느 쪽인지는 누가, 실행하기 전에, 무엇을 보고 판단할까요. 그게 4장입니다.

▶ 4장. 누가 고를 것인가 — System R과 비용 기반 옵티마이저

Last updated on August 22, 2026

Overview