B-트리·B+트리 높이 계산기
레코드 수와 페이지 크기(또는 차수)에서 B-트리와 B+트리의 높이와 디스크 접근 횟수를 계산합니다. 노드 점유율을 입력으로 노출해 100%로 가정한 계산과 어떻게 갈리는지 보여 줍니다.
디스크에서 한 번에 읽는 단위입니다. InnoDB는 16KB를 씁니다.
페이지 번호를 가리키는 크기입니다. InnoDB는 6바이트입니다.
보조 인덱스면 레코드 포인터 크기, 클러스터드 인덱스면 행 전체 크기입니다.
무작위로 넣고 지우면 약 69%에 정착합니다(ln2). 100%로 두면 높이를 낮게 봅니다.
0으로 두면 점 조회만 봅니다.
B+트리 높이
3단
점 조회에 페이지 3장 · 내부 갈래 807개
사용 방법
- 1레코드 수를 넣습니다.
- 2페이지 크기·키 크기·포인터 크기를 넣으면 한 노드에 몇 갈래가 들어가는지가 나옵니다.
- 3노드 점유율을 정합니다. 기본값 69%는 무작위 삽입·삭제 뒤 정착하는 평균값입니다.
- 4«차수로» 탭에서는 차수 m만 넣어 최소·최대 높이의 범위를 볼 수 있습니다.
자주 묻는 질문
리프 수를 갈래 수로 나눠 1이 될 때까지 올라간 층수입니다. 리프 한 장에 L건이 담기고 내부 노드가 F갈래로 뻗으면 높이 h는 ⌈log_F(⌈N/L⌉)⌉ + 1입니다. 16KB 페이지에 8바이트 키·6바이트 포인터면 갈래가 1,170개라, 점유율 69%를 먹여도 1,000만 건이 3단이면 닿습니다.
⌊(페이지 크기 + 키 크기) ÷ (포인터 크기 + 키 크기)⌋입니다. 자식 포인터 n개와 키 n−1개가 한 페이지에 들어가야 하기 때문입니다. 16KB 페이지에 8바이트 키·6바이트 포인터면 1,170갈래이고, 이것이 InnoDB 인덱스가 3~4단으로 수억 건을 다루는 근거입니다.
B+트리는 데이터가 리프에만 있고 내부 노드는 길잡이 키만 갖습니다. 그래서 같은 페이지에 더 많은 갈래가 들어가 높이가 낮고, 리프끼리 연결되어 범위 검색이 리프만 훑으면 끝납니다. 대신 어떤 값을 찾든 리프까지 내려가야 해서 탐색 비용이 언제나 같습니다 — B-트리처럼 루트에서 바로 끝나는 일이 없습니다.
무작위로 넣고 지우기를 반복하면 점유율이 ln2인 약 69%에 정착하기 때문입니다(Yao, 1978). 노드가 꽉 차면 반으로 쪼개져 절반씩 차므로 평균이 그 사이에 머뭅니다. 100%로 가정하면 갈래 수를 과대평가해 높이를 실제보다 낮게 보게 됩니다.
키가 N개, 차수가 m일 때 최대 높이는 log_t((N+1)/2) + 1이며 t = ⌈m/2⌉입니다. 루트만 키 1개를 허용하고 나머지 노드는 절반이 차 있어야 한다는 규칙에서 최소 키 수 2·t^(h−1) − 1이 나오기 때문입니다. 차수 4에 1,000건이면 꽉 찼을 때 5단, 최소로 찼을 때 9단으로 두 배 가까이 벌어집니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 높이는 «몇 층인가»로 셉니다. 리프만 있는 트리가 1단입니다. 간선 수로 세는 교재(CLRS 등)와는 1만큼 차이가 나니 비교할 때 확인하세요.
- 디스크 접근 횟수는 캐시가 전혀 없을 때의 값입니다. 실제로는 상위 몇 단이 버퍼 풀에 상주하고 루트는 거의 언제나 메모리에 있어 실제 I/O는 이보다 적습니다.
- «차수로» 탭의 최소·최대 높이는 규칙이 허용하는 범위이지 실제 높이가 아닙니다. 실제 트리는 점유율 69% 언저리에서 그 사이에 놓입니다.
- 가변 길이 키를 쓰면 노드마다 갈래 수가 달라져 이 계산이 근사가 됩니다. 접두 압축을 하는 구현에서는 갈래가 더 늘어납니다.
- B-트리 쪽 높이는 내부 노드에도 항목이 들어간다고 보고 낸 추정입니다. 실제 구현마다 내부 노드에 데이터를 얼마나 두는지가 달라 차이가 있을 수 있습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.