2장. B-tree는 왜 이진트리가 아닌가 — 디스크가 정한 모양

{/* 삽화 자리 — 층이 낮고 폭이 넓은 이정표 나무. 한 번 내려가는 값이 비싸서 이 모양이 됐다 */}

이진 탐색 트리로 100만 건을 찾으면 디스크에 스무 번 갔다 옵니다. B-tree는 세 번이면 끝나요. 차이는 알고리즘이 아니라 노드 하나의 크기에서 나옵니다.

면접 실전 질문: ① B-tree는 이진 탐색 트리와 무엇이 다른가요? ② 왜 노드를 굳이 크게 만드나요? ③ 삽입할 자리가 없으면 어떻게 되나요?

배경 — 좋은 알고리즘이 나쁜 답이 되는 자리

1장에서 이 책이 셀 단위를 16KB 페이지로 정했습니다. 그리고 그 페이지를 디스크에서 가져와야 할 때, 청구서는 “몇 번 갔다 오는가”로 나옵니다. 평균 탐색이 600밀리초인 세계에서는 그것만이 말이 되는 계산이었으니까요.

그 자로 이진 탐색 트리를 재봅시다.

이진 탐색 트리는 교과서가 가장 먼저 가르치는 답입니다. 노드마다 키 하나와 자식 둘. 정렬돼 있으니 한 번 내려갈 때마다 후보가 절반으로 줄고, 높이는 log₂(N)입니다. 연산 횟수만 보면 훌륭합니다.

문제는 그 높이가 곧 디스크 왕복 횟수가 된다는 데 있습니다. 노드가 저마다 디스크의 다른 자리에 흩어져 있으면, 한 층 내려갈 때마다 디스크를 한 번 찾아가야 하거든요.

📄 문서 기반 (미검증) — 높이는 log₂(N)을 올림한 값이고, 600밀리초는 1장에서 인용한 IBM 350(1956)의 평균 탐색 시간입니다. 1970년의 IBM 2311은 이보다 훨씬 빨랐으니, 이 환산은 “디스크 왕복이 비싸면 어떻게 되는가”를 보여주는 계산이지 1970년의 실제 응답 시간이 아닙니다. 노드가 전부 다른 페이지에 흩어져 있고 캐시가 없다는 최악의 가정이에요.

한 건 찾는 데 12초. 알고리즘은 나무랄 데가 없는데, 그 결과를 못 씁니다.

여기서 탓할 건 이진 탐색 트리가 아닙니다. “한 번 내려가는 값”이 공짜에 가깝다는 전제예요. 메모리 위에서라면 맞는 전제고, 디스크 위에서는 틀린 전제입니다.

그리고 1장에서 이미 본 게 하나 더 있습니다. 디스크는 어차피 블록 단위로 읽습니다. 키 하나를 읽으려 해도 블록을 통째로 가져와요 — 오늘 InnoDB에서 그 단위가 16KB입니다. 이진 탐색 트리는 그 16KB 중에 키 하나만 쓰고 나머지를 버리는 셈입니다.

낭비가 보이면 답도 보입니다.

스토리 — 어차피 페이지를 통째로 읽는다면

1970년 7월, 보잉의 바이어와 맥크레이트가 낸 답은 이것이었습니다. 노드 하나를 디스크 페이지 하나만큼 키운다.

한 번 갔다 오는 값이 비싸다면, 갔을 때 최대한 많이 들고 오면 됩니다. 페이지 하나에 키를 수백 개 담으면 자식도 수백 개고, 한 층 내려갈 때마다 후보가 절반이 아니라 수백분의 일로 줄어듭니다.

높이가 log₂(N)에서 log_팬아웃(N)으로 바뀝니다. 로그의 밑이 2에서 수백으로 커지는 거예요. 이게 이 장의 전부라고 해도 됩니다.

“B-tree는 이진트리가 아니다”는 말은 정확히 이 뜻입니다. 자식이 둘이 아니라 수백 개입니다. 그리고 그 수백이라는 숫자는 알고리즘이 고른 게 아니라 디스크가 정했습니다 — 페이지 크기가 얼마고 키가 몇 바이트냐가 곧 팬아웃이니까요.

자리가 없으면 쪼갠다

1장 끝에서 남긴 질문이 있었습니다. ISAM은 넘치는 레코드를 오버플로 체인에 매달았는데, B-tree는 삽입할 자리가 없을 때 무엇을 해야 할까?

답은 쪼갠다입니다.

페이지가 꽉 찬 상태에서 키가 하나 더 들어오면, 그 페이지를 절반으로 나눠 새 페이지를 만듭니다. 그리고 가운데 키 하나를 부모에게 올려보냅니다 — 이제 부모는 “이 값보다 작으면 왼쪽, 크면 오른쪽”을 알게 되죠.

이건 B-tree의 원칙이고, 실제 엔진은 여기에 잔꾀를 하나 더 부립니다. InnoDB는 키가 계속 증가하는 중이면 가운데가 아니라 오른쪽 끝에서 쪼개요. 뒤에 나올 표에서 클러스터드 리프가 페이지당 63행 — 거의 꽉 찬 채로 나오는 게 그 증거입니다. 가운데서 쪼갰다면 절반이 빈 페이지가 잔뜩 남았을 테니까요. 왜 이 잔꾀가 성능을 가르는지는 13·14장입니다.

부모도 꽉 차 있으면 부모가 또 쪼개지고, 그 위로 올라갑니다. 루트까지 올라가서 루트마저 꽉 차 있으면 루트가 쪼개지고 그 위에 새 루트가 생깁니다. 트리가 한 층 자라는 건 이때뿐이에요.

트리는 루트에서만 자란다 — 이 한 문장에 ISAM이 못 풀던 게 전부 들어 있습니다.

• 성장이 루트에서만 일어나므로 모든 리프의 깊이가 항상 같습니다. 한쪽만 깊어지는 일이 구조적으로 생기지 않아요. 균형을 따로 맞출 필요가 없습니다.
• 오버플로 체인이 없습니다. 넘친 레코드를 딴 데 매달지 않고 구조 안에서 흡수하니까요.
• 그래서 밤마다 파일을 다시 세울 이유가 사라집니다. ISAM이 운영 절차로 메우던 결함을 자료구조가 스스로 처리합니다.

논문이 자기 답을 어느 정도로 자신했는지도 숫자로 남아 있습니다.

📄 문서 기반 (미검증) — 논문 초록에 따르면, IBM 360/44와 2311 디스크에서 엔트리 15,000개짜리 인덱스를 초당 평균 9건의 트랜잭션으로 유지할 수 있었습니다(10만 개짜리에서는 최소 4건). 재구성 없이요.

쪼개기는 공짜가 아닙니다

여기서 이 책이 나중에 갚을 빚이 하나 생깁니다.

쪼개기는 조회를 위해 삽입이 치르는 값입니다. 페이지를 반으로 나눠 절반을 옮겨야 하고, 그 과정에서 페이지들이 반만 찬 채로 남기도 해요. 읽기를 위해 쓰기가 값을 무는 구조입니다.

이 값이 얼마인지는 4부에서 잽니다. 특히 키가 어떤 순서로 들어오느냐에 따라 쪼개기가 거의 안 일어나기도, 매번 일어나기도 하는데 — 그게 13·14장의 주제입니다.

지금은 이 장의 질문으로 돌아갑시다. 팬아웃이 정말 수백인가, 그래서 높이가 정말 낮은가. 세어보면 됩니다.

핵심 — 높이를 직접 세봤습니다

높이를 알려주는 컬럼이 MySQL에는 없습니다. information_schema를 다 뒤져도 없고, INNODB_BUFFER_PAGE에도 PAGE_LEVEL 같은 건 없어요.

그래서 테이블 파일을 직접 열었습니다.

InnoDB 페이지 하나는 16KB 고정이고, 헤더 앞쪽에 이 페이지가 트리의 몇 층인지가 적혀 있습니다. 리프가 0이고 위로 갈수록 1씩 오릅니다. 그러니 루트의 레벨 + 1이 곧 높이예요.

페이지 시작에서 offset 24 (2바이트)  FIL_PAGE_TYPE   인덱스 페이지면 17855
페이지 시작에서 offset 54 (2바이트)  PAGE_N_RECS     이 페이지가 담은 레코드 수
페이지 시작에서 offset 64 (2바이트)  PAGE_LEVEL      리프가 0
페이지 시작에서 offset 66 (8바이트)  PAGE_INDEX_ID   어느 인덱스 소속인지

전부 빅엔디언입니다. 루트가 몇 번 페이지인지는 서버가 알려줍니다.

SELECT i.NAME, i.PAGE_NO 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배 늘려도 한 층

transaction_no에 세컨더리 인덱스를 걸고, 행 수를 200배 늘려가며 레벨별 페이지 수를 셌습니다.

$ ./ch02/height.sh          # 세컨더리만 발췌
rows      index      level  pages   fanout  height
2000000   idx_txno   2      1       11      3
2000000   idx_txno   1      11      386     3
2000000   idx_txno   0      4247    -       3

✅ 실측 (MySQL 8.0.40 / Docker / Apple M1 / macOS, 2026-08. .ibd 파일의 페이지 헤더를 직접 파싱했습니다 — mysql 이미지에는 파이썬이 없어서 python:3-alpine 컨테이너에 볼륨을 읽기 전용으로 붙여 돌립니다. 가장 작은 케이스(1만 행)는 마지막 페이지가 덜 차서 페이지당 엔트리가 조금 낮게 나옵니다. 전체 소스: docs/book/code/db-index/ch02/height.sh · docs/book/code/db-index/ch02/pagelevels.py)

행이 200배로 늘어나는 동안 높이는 2에서 3으로, 딱 하나 늘었습니다. 같은 구간에서 이진 탐색 트리라면 14에서 21로 갑니다.

레벨별 페이지 수를 같이 실었으니 팬아웃을 직접 확인할 수 있습니다. 200만 행 세컨더리에서 리프가 4,247페이지고 그 위 레벨이 11페이지니까, 중간 노드 하나가 리프를 386개씩 거느립니다. 클러스터드는 31,747 ÷ 35 = 907이고요.

34바이트가 팬아웃을 정합니다

표의 “페이지당 엔트리” 열이 이 장의 답입니다. 세컨더리 인덱스는 페이지 하나에 471개가 들어갔습니다.

왜 하필 471인지 세어보죠. 인덱스 엔트리 하나는 이렇게 구성됩니다.

transaction_no  CHAR(20)   20 바이트 + 길이 1 바이트   ← utf8mb4 에서 CHAR 는 가변길이로 저장된다
그 행을 가리킬 PK  BIGINT      8 바이트
레코드 헤더                    5 바이트
                            ──────────
                              34 바이트

계산이 맞는지는 페이지를 열어보면 됩니다. 레코드 힙이 120바이트에서 시작해 16,134바이트까지 차 있었으니 (16,134 − 120) ÷ 471 = 정확히 34.0바이트. 계산과 측정이 소수점까지 맞습니다.

이 페이지들은 사실상 꽉 차 있다는 뜻입니다. 리프 페이지의 남은 공간을 세어보니 평균 8바이트였어요. 페이지 디렉터리 슬롯과 FIL 트레일러까지 뺀 진짜 여유가 그렇습니다. 16,384바이트 중 8바이트니 0.05%예요 — 34바이트짜리 엔트리 하나도 못 들어갑니다.

✅ 실측 (여유 = 16,384 − PAGE_HEAP_TOP − 8(FIL 트레일러) − 2 × PAGE_N_DIR_SLOTS + PAGE_GARBAGE. 200만 행 세컨더리 리프 4,247페이지의 평균)

정렬된 값을 한 번에 부어 만들었으니 당연한 결과예요. 키가 아무 순서로나 들어오면 이 숫자가 어떻게 무너지는지가 13·14장입니다.

클러스터드 인덱스는 리프에 행 전체가 들어 있어서 페이지당 63행뿐입니다. 1장에서 25만 행이 4,006페이지였죠 — 나누면 62.4행입니다. 같은 숫자예요(4,006에는 중간 노드도 섞여 있어 리프만 세면 63에 더 붙습니다). 그래서 같은 행 수인데도 리프 페이지가 7배 많습니다(2,124 대 15,874).

높이 하나가 감당하는 양

측정한 팬아웃(200만 행 기준 세컨더리 386, 클러스터드 907)과 리프 용량(471, 63)을 넣으면 각 높이가 담는 행 수가 나옵니다.

이 표가 위 실측과 어긋나지 않습니다. 특히 높이가 뒤집히는 지점을 맞혀요. 세컨더리는 18만을 넘는 순간 높이 3이 되어야 하는데 10만은 높이 2, 100만은 높이 3이었습니다. 클러스터드는 5만 7천이 경계라 10만에서 이미 높이 3이었고요.

높이 3으로 5천만 행 안팎을 덮습니다. 실무에서 만나는 테이블 상당수가 여기 들어가요. 그래서 “인덱스를 타면 몇 번 만에 찾느냐”는 질문의 답이 대체로 3인 겁니다. 단 이건 인덱스 하나를 내려가는 횟수예요. 세컨더리로 찾은 뒤 실제 행까지 가야 하면 그만큼 더 붙습니다(7장).

단, 이 숫자는 정렬된 값으로 거의 꽉 채웠을 때의 값이라 사실상 상한에 가깝습니다. 이 실험은 정렬된 순서로 한 번에 채웠으니까요. 난수 키가 섞여 페이지가 70%쯤만 차면 같은 높이가 감당하는 행 수는 절반 이하로 내려갑니다 — 그 값이 얼마인지가 13·14장입니다.

재는 동안 두 번 속았습니다

이 표를 얻기까지 측정이 두 번 틀렸습니다. 둘 다 남겨둘 만합니다.

첫째, 시드가 만든 테이블이 텅 비어 있었습니다. 처음엔 데이터를 배로 늘려 목표를 넘긴 뒤 초과분을 지웠는데, 1만 행을 만들려고 13만 행을 만들었다 지우니 페이지당 4.8행짜리 테이블이 됐습니다(정상은 62.5행).

InnoDB는 DELETE로 파일을 줄이지 않습니다. 통째로 빈 페이지는 테이블스페이스의 free list로 돌아가지만 파일에는 그대로 남고, 페이지 수에도 계속 잡혀요.

산수를 맞춰보면 이렇습니다. 13만 행이면 63행씩 담아 약 2,080페이지가 만들어집니다. 여기서 12만 행을 지워도 페이지는 2,080개 그대로니까 10,000 ÷ 2,080 = 4.8. 살아남은 160페이지는 여전히 63행씩 꽉 차 있고, 텅 빈 페이지 1,900여 개가 뒤에 딸려 있었던 겁니다. (충전율이 절반 아래로 내려간 페이지는 이웃과 병합을 시도하지만, 꼬리를 통째로 지운 이 경우엔 병합할 짝이 애초에 없습니다.)

목표를 아예 넘기지 않도록 시드를 고쳐 해결했고, 이 성질은 20장 보관정책에서 다시 나옵니다.

둘째, 루트가 두 개로 보였습니다. 파일을 통째로 훑었더니 최상위 레벨에 페이지가 2개 나왔어요. 한 인덱스에 루트가 둘일 수는 없죠. 레코드 수까지 똑같은 복사본이었습니다. 인덱스를 만드는 과정에서 남은 페이지로 보이는데, 원인까지 확인하지는 못했고 서버가 선언한 루트(INNODB_INDEXES.PAGE_NO)만 인정하도록 고쳐서 넘어갔습니다.

두 번째 건은 검산이 잡아줬습니다. 루트 페이지의 레코드 수(11)와 그 아래 레벨의 페이지 수(11)가 같아야 하는데, 유령을 세면 안 맞았거든요. 파일을 직접 읽을 때는 서버가 말하는 값과 교차 확인해야 합니다.

그런데 방금 잰 건 B-tree가 아닙니다

엄밀히 말하면, 위에서 잰 나무는 1970년 논문의 B-tree가 아닙니다.

클러스터드 중간 노드가 페이지당 900개 가까이 거느린 게 그 증거입니다 — 행이 통째로 들어 있었다면 63개가 한계였을 테니까요. 중간 노드에는 키만 있다는 뜻이고, 그걸 눈치챘다면 이미 본 겁니다 — 데이터가 리프에만 있어요. 원래 B-tree는 중간 노드에도 데이터를 둡니다.

이 한 가지를 바꾸면 무엇이 달라지는지가 3장입니다. 그리고 그 답은 값 하나를 찾을 때가 아니라 범위를 훑을 때 드러납니다.

정리

• 디스크 위에서는 트리 높이가 곧 왕복 횟수입니다. 이진 탐색 트리는 연산 횟수가 훌륭해도 100만 건에서 높이 20이라 못 씁니다.
• B-tree가 택한 건 알고리즘 개선이 아니라 노드 크기입니다. 노드를 페이지 하나만큼 키워 자식을 수백 개로 만들었고, 로그의 밑이 2에서 수백으로 바뀌었습니다.
• 팬아웃은 디스크가 정합니다. 엔트리가 34바이트고 페이지가 16KB니 페이지당 471개였습니다(실측). 남은 공간은 1.5%뿐이라 사실상 만충입니다.
• 삽입할 자리가 없으면 페이지를 쪼개고 가운데 키를 위로 올립니다. 트리는 루트에서만 자라므로 모든 리프의 깊이가 늘 같고, ISAM의 야간 재구성이 필요 없어집니다.
• 실측: 행이 200배 늘 동안 높이는 2 → 3. 높이 3으로 5천만 행 안팎을 덮습니다 — 단 페이지가 꽉 찼을 때의 상한입니다.

생각해볼 질문

1. 클러스터드 인덱스는 리프에 행 전체를 담아 페이지당 63행이고, 세컨더리는 471개였습니다. 그렇다면 세컨더리 인덱스로 찾은 다음 실제 행을 보려면 무슨 일이 더 일어나야 할까요? (7장에서 그 왕복을 잽니다)
2. 이 장의 페이지들은 정렬된 값을 한 번에 부어 만들어 거의 꽉 찼습니다(여유 8바이트). 그럼 반대로 UUID처럼 난수 키가 들어오면 이 471개는 얼마까지 내려갈까요? (13·14장)
3. 이 장은 값 하나를 찾는 비용만 봤습니다. BETWEEN처럼 범위를 훑어야 하면 높이가 낮은 게 여전히 도움이 될까요?

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