B-TreeB 트리 · B-Tree
키를 정렬 순서로 담은 노드가 여러 자식을 가리키고, 분할 · 병합으로 모든 잎을 같은 깊이에 두는 균형 탐색 트리다. 노드 하나를 디스크 페이지 하나에 맞춰 검색 · 삽입 · 삭제를 높이만큼의 페이지 읽기로 끝낸다.
1요약
- B-Tree 는 1970년 Boeing 연구소의 Bayer · McCreight 가 디스크 위 대형 색인용으로 낸 균형 다진 탐색 트리로, PostgreSQL 의 기본 색인 방식
btree를 비롯해 관계형 DBMS 색인이 그 위에서 돈다(Comer 1979 = 「데이터베이스 색인의 사실상 표준」). - 디스크는 한 번 읽을 때마다 긴 대기 시간이 들어, 키 하나짜리 노드의 이진 트리는 키 100만 개에서 20번을 읽지만 노드에 키 200개를 담는 B-Tree 는 높이 3, 곧 페이지 3장 읽기로 끝난다(Bayer · McCreight 식 3.1).
- 「색인이 있는데 느리다」는 트리를 타는가, 트리가 부풀었는가로 가른다 — 실행 계획에 Index Scan 이 없으면 조건이 정렬 순서의 앞부분을 못 쓰는 것이고, 타는데 느리면 잎 밀도 · 높이가 원인이다.
2등장 배경
1960년대 말 큰 파일의 색인은 주기억에 다 들어가지 않아 디스크 · 드럼에 두어야 했고, 레코드가 계속 들어오고 빠지는 파일은 찾기뿐 아니라 키 삽입 · 삭제도 싸게 해야 했다(Bayer · McCreight 1970 1절). 노드 하나를 읽을 때마다 디스크를 한 번 읽으므로 키 하나짜리 노드의 이진 트리는 깊이만큼 읽고, 균형이 깨지면 그 경로가 더 길어진다(Comer 1979 1절).
1970년 7월 Boeing Scientific Research Laboratories 의 R. Bayer · E. McCreight 가 페이지마다 키 k ~ 2k 개를 두고 넘치면 나누는 B-tree 를 발표해, IBM 360/44 · 2311 디스크에서 키 15,000개 색인을 초당 평균 9건의 검색 · 삽입 · 삭제로 유지했다(같은 논문 초록 · Acta Informatica 1972 에 다시 실음). 1973년 Knuth 는 노드를 2/3 이상 채우는 B*-tree 와, 키를 잎에만 두는 이름 없는 변종을 함께 냈고 Comer 가 뒤의 것을 B+-tree 라 불렀다(Comer 1979 3절).
1981년 Lehman · Yao 가 페이지마다 오른쪽 형제 링크를 더해 동시 접근 때 잠금을 줄였고, 지금 PostgreSQL nbtree 가 이 방식을 쓴다(nbtree README). PostgreSQL 의 CREATE INDEX 는 방식을 적지 않으면 btree 를 만든다(CREATE INDEX).
3쉽게 이해하기 — 번호 상자를 쌓는 물류 창고
물류 창고 관리인이 번호 붙은 상자를 선반에 번호 순서로 놓는다. 선반 한 칸에는 상자가 4개까지 들어가고, 입구와 통로마다 「90 이상은 오른쪽」 같은 안내판이 서 있다. 130번 상자를 찾는 직원은 입구 안내판 · 통로 안내판 · 선반 셋만 보고 상자를 꺼낸다. 선반에 다섯째 상자가 오면 관리인은 선반을 둘로 나누고 가운데 번호를 위 안내판에 적으며, 안내판까지 넘치면 그 위에 새 입구 안내판을 세운다.
그림 1 · 직원은 입구 안내판 · 통로 안내판 · 선반 세 곳만 보고 130번 상자를 찾고, 선반이 넘치면 둘로 나눈 뒤 가운데 번호를 위 안내판에 적는다.
그림 2 · 넘침은 선반에서 시작해 안내판으로 올라가고, 입구 안내판이 나뉠 때만 창고 전체가 한 단계 깊어진다 — 그래서 모든 선반까지의 거리가 늘 같다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 창고 전체 | B-Tree | 키와 행 위치를 정렬 순서로 담는다 |
| 입구 안내판 | 루트 노드 | 모든 검색 · 삽입이 여기서 출발한다 |
| 통로 안내판의 번호 | 내부 노드 · 분리 키 | 키 범위를 나눠 내려갈 자식을 정한다 |
| 선반 한 칸 | 잎 노드 · 디스크 페이지 | 키를 k ~ 2k 개 담고 한 번에 읽힌다 |
| 상자 번호 | 키 | 주문 번호 · 날짜처럼 정렬 순서가 있는 값 |
| 선반 나누기 | 분할 | 키가 2k + 1 개가 되면 가운데 키를 부모로 올린다 |
| 선반 합치기 · 상자 빌리기 | 병합 · 재분배 | 키가 k 개 아래로 줄면 형제와 합치거나 형제 키를 빌린다 |
| 거치는 안내판 수 | 높이 | 찾을 때 읽는 페이지 수 |
⚠ 비유가 맞지 않는 곳: 원래 B-Tree 는 안내판에 적힌 번호도 실제 키와 행 위치라 내부 노드에서 검색이 끝나기도 한다. 안내판에는 번호만 두고 상자는 선반에만 두는 쪽이 B+Tree 다.
4구조 — 노드와 균형 규칙
Bayer · McCreight 의 정의는 세 조건이다 — 루트에서 모든 잎까지 경로 길이가 같은 h 이고, 루트 · 잎을 뺀 노드는 자식이 k + 1 개 이상, 모든 노드는 자식이 2k + 1 개 이하다(정의 2.1). 그래서 페이지 하나는 키 k ~ 2k 개(루트는 1 ~ 2k 개)를 담는다(3절).
그림 3 · 노드 한 장은 키와 포인터를 번갈아 담은 디스크 페이지이고, 루트 · 내부 · 잎 세 종류가 키 수 규칙을 지켜 모든 잎이 같은 깊이에 놓인다.
| 요소 | 크기 | 역할 | 값 · 근거 |
|---|---|---|---|
| 분리 키 | 노드당 k ~ 2k 개 | 자식 사이 범위 경계 | 노드 안에서 정렬 순서로 저장(Bayer · McCreight 3절) |
| 자식 포인터 | 키 수 + 1 | 다음 노드의 페이지 번호 | Pi 아래 키는 Ki 와 Ki+1 사이(3절) |
| 행 위치 | 키마다 1 | 표의 행을 가리킴 | PostgreSQL = 잎 튜플이 가리키는 표 행(65.1.4.1) |
| 루트 노드 | 1개 | 모든 검색의 출발점 | 키 1 ~ 2k · 나뉘면 새 루트(4절) |
| 잎 노드 | 노드 대부분 | 맨 아래 노드 | PostgreSQL 페이지의 99% 이상(65.1.4.1) |
| 균형 규칙 | — | 모든 잎을 같은 깊이에 | 높이는 루트가 나뉠 때만 1 늘어남(1절) |
| 페이지 | 노드 1개 | 디스크에서 한 번에 읽는 단위 | PostgreSQL 기본 8 kB · 항목 하나는 페이지 약 1/3 이하(66.6 · 65.1.1절) |
⚠ 「차수(order)」는 문헌마다 다르다. Bayer · McCreight 의 k 와 Comer 의 d 는 노드의 최소 키 수이고 Knuth 1973 은 다른 기준을 쓰므로(Comer 1979 2절), 답안에는 「노드당 키 k ~ 2k」처럼 정의를 함께 적는다.
🔑 B-Tree 는 잎에서 넘치고 루트에서만 자란다 — 높이가 루트 분할로만 늘기 때문에 모든 잎의 깊이가 늘 같다.
5동작 — 키 17개로 높이 3이 되는 삽입과 삭제
Python 3.14.0 으로 Bayer · McCreight 의 삽입 · 삭제 규칙(4 · 6절)을 직접 구현해 실행한 사례다. k = 2(노드당 키 2 ~ 4개 · 루트 1 ~ 4개)이고 키 10 ~ 170 · 45 는 설명용 가정 값이다.
- 빈 트리에 10 · 20 · 30 · 40 을 넣는다 — 루트 하나가 잎이면서 키 4개(2k)로 꽉 찬다.
- 50 을 넣으면 키가 5개(2k + 1)가 되어 [10 · 20] · 30 · [40 · 50] 으로 나뉘고, 30 이 새 루트가 된다 — 높이 2.
- 60 ~ 160 을 차례로 넣는 동안 맨 오른쪽 잎이 80 · 110 · 140 에서 세 번 나뉘고, 올라간 키로 루트가 [30 · 60 · 90 · 120] 으로 꽉 찬다.
- 170 이 들어오기 직전 맨 오른쪽 잎은 [130 · 140 · 150 · 160] 이다.
- 170 을 넣으면 잎이 나뉘어 150 이 루트로 올라가고, 키 5개가 된 루트도 나뉘어 90 이 새 루트가 된다 — 높이 3 · 잎 6개 모두 키 2개(k)로 정확히 절반만 찬다.
- 130 을 찾으면 [90] → [120 · 150] → [130 · 140] 세 페이지를 읽고 끝난다 — 읽은 수 = 높이.
- 45 를 넣은 뒤 20 을 지우면 잎 [10] 이 k 아래로 줄고, 오른쪽 형제 [40 · 45 · 50] 이 키를 빌려 준다 — 분리 키 30 이 내려오고 40 이 올라가 [10 · 30] · 40 · [45 · 50] 이 된다(재분배).
- 140 을 지우면 잎 [130] 의 두 형제가 모두 k 개라 빌릴 수 없어 [100 · 110 · 120 · 130] 으로 합쳐지고(병합), 부모 [150] 도 k 아래로 줄어 [40 · 60 · 90 · 150] 으로 합쳐진다 — 빈 루트가 사라져 높이 2.
그림 4 · 170 하나를 넣자 분할이 잎에서 루트까지 올라가 새 루트 90 이 생겼고, 모든 잎이 함께 한 단계 깊어져 130 검색은 세 페이지를 읽는다.
그림 5 · 노드 하나에 키를 수백 개 담으면 키 10억 개도 높이 4 ~ 5에서 끝나, 검색 때 읽는 페이지가 이진 트리 30장의 1/6 수준으로 준다.
🔑 B-Tree 의 비용은 키 개수가 아니라 높이가 정하고, 높이는 노드 하나에 담는 키 수가 정한다 — 노드를 디스크 페이지 크기로 키우는 까닭이다.
⚠ 사례 5단계처럼 키를 오름차순으로 넣으면 원래 규칙에서는 잎이 절반만 찬다. PostgreSQL 은 맨 오른쪽에 가장 큰 키를 이어 넣을 때 잎을 fillfactor 기본값 90% 까지 채운다(CREATE INDEX).
6비교 — B+Tree · B*Tree · 해시 색인 · LSM 트리
| 기준 | B-Tree | B+Tree | B*Tree | 해시 색인 | LSM 트리 |
|---|---|---|---|---|---|
| 키 · 행 위치 | 모든 노드 | 잎에만 · 위는 분리 키 · 잎끼리 연결(Comer 3절) | B-Tree 와 같음 | 키의 4바이트 해시값만(PostgreSQL 65.6.1) | 메모리 요소 + 디스크 요소 여럿(O'Neil 1996) |
| 최소 채움 | 1/2 | 1/2 | 2/3(Comer 3절) | 버킷 · 줄이려면 REINDEX(65.6.1) | 병합 때 다시 씀 |
| 범위 · 정렬 검색 | 됨 · 다음 키에 여러 노드 | 잎 연결로 다음 키 1회 접근 | 됨 | 안 됨 · = 만(11.2.2절) | 됨 · 요소 여러 개를 함께 봄 |
| 넘칠 때 | 1개 → 2개 분할 | 1개 → 2개 분할 | 형제에 먼저 넘기고 둘 다 차면 2개 → 3개 | 버킷 분할(앞단에서 실행) | 메모리 요소를 디스크로 병합 |
| 쓰기 비용 | 키마다 경로 페이지 갱신 | B-Tree 와 같음 | 분할이 적음 | 버킷 하나 갱신 | 모아서 순차 기록 |
| 검색 비용 | 높이 이하(내부에서 끝날 수 있음) | 늘 높이만큼 | 높이(더 낮음) | 대개 버킷 하나 · 치우치면 늘어남(65.6.1) | 요소 수만큼 늘 수 있음 |
분석범위 · 정렬 조건이 섞이는 일반 업무 표는 B+Tree, = 만 쓰는 긴 키(UUID · URL)는 해시 색인, 쓰기가 읽기보다 훨씬 많은 이력 · 로그 표는 LSM 트리가 맞다. 근거는 표의 「범위 · 정렬 검색」 · 「쓰기 비용」 행이고, O'Neil 1996 초록은 빠르게 커지는 이력 표에 실시간 B-tree 색인을 두면 트랜잭션 I/O 비용이 두 배가 된다고 적었다.
7실무 진단 — 색인을 두고도 느린 질의 가르기
분석PostgreSQL 에서는 EXPLAIN 으로 트리를 타는지부터 보고, 탄다면 pgstatindex 로 트리 모양을 본다. 트리를 타지 않는 문제는 조건이 정렬 순서의 앞부분을 쓰는가(11.2.1 · 11.3절)로, 타는데 느린 문제는 잎 밀도 · 높이(F.33.1)로 끝까지 갈린다.
| # | 증상 | 의심 원인 | 구분 | 확인 명령 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | LIKE '%kim' · 둘째 열만 쓴 조건이 전체 스캔 | 조건이 정렬 순서의 앞부분을 못 씀 | 트리 진입 | EXPLAIN SELECT … | Seq Scan · 앞이 고정된 LIKE 'kim%' 과 선행 열 같음 조건만 범위를 줄임(11.2.1 · 11.3절) |
| 2 | 행 수는 그대로인데 색인 크기만 커짐 | 지우고 갱신한 항목이 남아 잎이 성김 | 잎 노드 | SELECT * FROM pgstatindex('idx') | avg_ |
| 3 | 범위 스캔이 갈수록 느려짐 | 분할로 잎의 키 순서와 디스크 순서가 어긋남 | 잎 노드 | pgstatindex('idx') | leaf_ |
| 4 | 쓰기가 몰릴 때 지연이 튐 | fillfactor 100 으로 빌드해 갱신마다 분할 | 분할 | SELECT reloptions FROM pg_class WHERE relname = 'idx' | fillfactor=100 = 분할 폭주 위험 · 쓰기 많은 표는 50 ~ 90(CREATE INDEX) |
같은 검색이 느려도 트리를 타지 않으면 색인을 손볼 것이 아니라 질의 조건이나 열 순서를 바꿔야 하므로 EXPLAIN 이 먼저다. 트리를 타는데 느리면 tree_level(루트의 레벨 · 잎 = 0)과 avg_leaf_density 를 함께 보고, 밀도가 낮으면 트리가 부푼 것이다.
8시험 대비
www.q-net.or.kr시험에서는 B-Tree 의 장단점과 B+Tree · B*Tree 와의 차이를 묻는 정의 · 특징형 · 비교형, 키를 몇 개 주고 삽입 분할 · 삭제 병합을 그리게 하는 동작 · 절차 설명형이 나올 수 있다. 다른 답안과 차이는 높이 식으로 키 100만 개 · k = 100 의 높이 3 을 직접 계산해 그림 5 처럼 보이는 데서 난다.
- 개요 — 정의 · Bayer · McCreight(1970 · 1972) · 노드 = 디스크 페이지 · 다진 균형 탐색 트리
- 구조 — 그림 3 노드 배치(키 · 포인터 번갈아)와 루트 · 내부 · 잎 + 정의 세 조건(자식 k + 1 ~ 2k + 1 · 잎 깊이 같음)
- 삽입 · 삭제 — 그림 4 분할 전파 · 루트 분할로 높이 + 1 + 재분배 · 병합 규칙(k = 2 키 17개 사례)
- 성능 — 그림 5 높이 막대(키 100만 개 = 이진 20 · B-Tree 3) + 높이 식 log(2k+1)(N+1) ≤ h ≤ 1 + log(k+1)((N+1)/2)
- 변종 비교 — 비교표(B-Tree · B+Tree · B*Tree · 해시 · LSM × 키 위치 · 최소 채움 · 범위 검색 · 쓰기 비용)
- 장단점 · 적용 — 범위 · 정렬 검색과 낮은 높이 / 쓰기 많은 부하는 LSM · PostgreSQL fillfactor 90 · 빈 페이지만 삭제
꼭 쓸 키워드
균형 트리차수분리 키노드 분할병합재분배높이디스크 페이지B+TreeB*Tree
9오해와 사실
- 오해B-Tree 의 B 는 이진(Binary)을 뜻한다.사실지은이들은 B 의 뜻을 밝힌 적이 없고(Comer 1979 1절), 노드가 자식을 최대 2k + 1 개 가져 이진 트리와 달리 넓고 낮게 자란다(Bayer · McCreight 정의 2.1).
- 오해B*Tree 는 잎끼리 연결해 순차 읽기를 빠르게 한 B-Tree 다.사실그 구조는 B+Tree 이고, Knuth 의 B*Tree 는 형제 둘이 다 찰 때까지 분할을 미뤄 노드를 2/3 이상 채우는 변종이다(Comer 1979 3절).
- 오해DB 색인은 키를 지우면 반쯤 빈 페이지를 곧바로 옆 페이지와 합친다.사실PostgreSQL nbtree 는 반쯤 빈 페이지를 합치지 않고 항목이 하나도 없는 페이지만 트리에서 지운다(nbtree README).
10핵심 정리
| 구분 | 맡는 일 | 키 수(k 기준) | 바뀌는 때 | 높이 영향 | PostgreSQL nbtree |
|---|---|---|---|---|---|
| 루트 노드 | 검색 출발 | 1 ~ 2k | 나뉘면 새 루트 | 루트 분할 + 1 | 메타페이지가 루트 위치를 가짐 |
| 내부 노드 | 키 범위를 나눔 | k ~ 2k · 자식 k+1 ~ 2k+1 | 자식 분할 · 병합 | 없음 | 아래 레벨로 가는 링크만 |
| 잎 노드 | 행 위치 보관 | k ~ 2k | 삽입 · 삭제 | 없음 | 페이지의 99% 이상 · 형제 링크 |
| 분할 | 넘침 해소 | 2k+1 → k · 1 · k | 꽉 찬 노드에 삽입 | 루트에서 + 1 | 바이트 기준으로 나눔 |
| 재분배 | 부족 해소 | 형제에서 1개 빌림 | 형제가 k 개 초과 | 없음 | 하지 않음 |
| 병합 | 부족 해소 | 두 노드 + 분리 키 → 1개 | 형제도 k 개 | 루트가 비면 − 1 | 빈 페이지만 삭제 |
| 높이 | 검색 때 읽는 수 | log 식(식 3.1) | 루트 분할 · 축소 | — | pgstatindex tree_ |
11참고 문헌
- 먼저 볼 문헌
- ★ Organization and Maintenance of Large Ordered Indices (Proc. 1970 ACM SIGFIDET Workshop pp. 107-141) — B-tree 의 정의 세 조건 · 분할 · 병합 규칙과 높이 식을 원문으로 볼 때
- ★ The Ubiquitous B-Tree (ACM Computing Surveys 11(2) pp. 121-137) — B+-tree · B*-tree 의 차이와 이름이 섞여 쓰인 사정을 볼 때
- ★ PostgreSQL 18 Documentation 65.1 B-Tree Indexes — 실제 DBMS 의 잎 · 내부 페이지 구조와 분할 · 중복 제거를 볼 때
- ★ The Log-Structured Merge-Tree (LSM-Tree) (Acta Informatica 33(4) pp. 351-385) — 쓰기가 많은 부하에서 B-tree 대신 LSM 트리를 쓰는 까닭을 볼 때
- ★ F.33 pgstattuple — obtain tuple-level statistics (pgstatindex) — 색인의 높이 · 잎 밀도 · 조각남을 숫자로 확인할 때
- 본문 근거
- Organization and Maintenance of Large Ordered Indexes (Acta Informatica 1(3) pp. 173-189) — R. Bayer · E. McCreight · 1972-09 ·
doi.org/10.1007/BF00288683· 확인 2026-11-04 - Efficient Locking for Concurrent Operations on B-Trees (ACM TODS 6(4) pp. 650-670) — Philip L. Lehman · S. Bing Yao · 1981-12 ·
doi.org/10.1145/319628.319663· 확인 2026-11-04 - PostgreSQL source src/backend/access/nbtree/README — PostgreSQL Global Development Group · 2026-11 ·
github.com/postgres/postgres/blob/master/src/backend/access/nbtree/README· 확인 2026-11-04 - PostgreSQL 18 Documentation 11.2 Index Types — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/indexes-types.html· 확인 2026-11-04 - PostgreSQL 18 Documentation 11.3 Multicolumn Indexes — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/indexes-multicolumn.html· 확인 2026-11-04 - PostgreSQL 18 Documentation CREATE INDEX (fillfactor · deduplicate_items) — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/sql-createindex.html· 확인 2026-11-04 - PostgreSQL 18 Documentation 65.6 Hash Indexes — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/hash-index.html· 확인 2026-11-04 - PostgreSQL 18 Documentation 66.6 Database Page Layout — PostgreSQL Global Development Group · 2026-11 ·
www.postgresql.org/docs/current/storage-page-layout.html· 확인 2026-11-04 - Python 3.14 Documentation — Python Software Foundation · 2026-11 ·
docs.python.org/3.14/· 확인 2026-11-04